这一篇是我的 2019 年科研“属性加密”系列番外篇，记录一些关于（特殊）分段安全性的故事。这一篇的风格相较主系列更轻松活泼（肯定有人要吐槽我对“轻松活泼”的定义），比如去掉了繁复的导航按钮，减少了公式。另外这一篇也加上了“数学”的标签，大概是因为很多这里考虑的问题的密码学价值不大，更像是线性代数的游戏？
内容回顾
“属性加密”系列到目前为止用五篇文章介绍了：
- 属性加密和 1-ABE 的概念
- 算术密钥乱码化方案即 AKGS 的概念，以及针对算术公式的构造
- 用内积加密和 AKGS 构造 1-ABE 的方法
- （特殊）分段安全性的概念，以及如何用分段安全性和泛函保密性证明 1-ABE 适应性安全
这篇文章里我想单独讨论（特殊）分段安全性，所以这一篇和 ABE 没太大关系，不了解背景的读者只需要了解 AKGS 语法、语义、模拟安全性 以及（特殊）分段安全性 即可看懂这篇文章。
算术分支程序
在发现算术公式 AKGS 具有分段安全性之后，导师提示我：“既然现在性质里根本没有和‘深度’有关的概念，你可以看看 ABP 是否也有这个性质。”然后我就验算了一番，果然有此性质！
算术分支程序简称 ABP，是 BG99 提出的一种计算模型。已知算术公式可以转换为同等规模的算术分支程序，而 IW14 中构造了适用于算术分支程序的部分乱码化方案，经过检验可以发现符合 AKGS 的语法，且具有分段安全性。
这也是为什么 LL20 里面没有记录算术公式的 AKGS 的原因：ABP 的 AKGS 把它吞并了。不过我还是觉得算术公式更直观，而且历史上也是从算术公式的递归模拟一步一步启发得到的分段安全性，所以主系列文章还是用算术公式来写。
我觉得这段故事最有价值的部分不是把策略的范围从算术公式提升到 ABP，而是逐渐学习科研的模式和方法，如果是我自己，大概不会意识到“去掉‘深度’概念之后这个性质是否可以推广到更大的函数类”是值得思考的问题。
特殊分段安全性真的特殊吗？
显然，特殊分段安全的 AKGS 也是分段安全的，一个自然的问题是：特殊分段安全性真的“特殊”吗？答案是否定的：
定理 LL20 若某函数类具有分段安全的 AKGS，则它也具有特殊分段安全的 AKGS，且后者可由前者对 所用的随机数施加一个线性自同构得到。该自同构可从 高效计算且和 无关。
这是一道简单的线性代数习题。实际上，证明过程表明特殊分段安全完全由分段安全的第二个性质（标签边际随机）蕴含。
这个定理表明，分段安全性是特殊分段安全性的内蕴版本，而特殊分段安全性是分段安全性（在一组合适的基下）的标准形，和很多线性代数里的概念类似。在 LL20 中，所有用到的 AKGS 都显然具有特殊分段安全性，而 1-ABE 的证明只用到分段安全性，这让我想起一段名言：
We share a philosophy about linear algebra: we think basis-free, we write basis-free, but when the chips are down we close the office door and compute with matrices like fury.
分段安全 AKGS 乱码化规模
任一函数最小规模分段安全 AKGS 的规模是这个函数本身的性质（和计算性假设无关）。很多随机化编码的规模和一个函数在某种计算模型下的最小表示规模有关，例如：
定理 KW93 对任意单调布尔函数和任意域，该函数在该域上的最小规模单调线性组合性程序的规模，等于它在该域上最小规模线性秘密共享方案的规模。
这里随机化编码是指“线性秘密共享”，计算模型是指“单调线性组合性程序”，这里的关联是紧的——即两者相等。（关于 monotone span program 的翻译 见此。）现在自然要问：一个函数的分段安全 AKGS 乱码化规模和它在什么模型下最小表示的规模紧密关联？
首先值得注意的是任何（模拟安全的）AKGS 都可以先把输入二进制化，然后再通过简单的线性秘密共享手段转换为 LSS，故若一个函数具有多项式规模的分段安全 AKGS，则它必然有多项式规模的 LSS，这表示这个函数很容易用线性代数里的概念表示（因为 LSS 等同于 MSP，后者的计算完全就是线性代数）。联想到 IK02 里对 ABP 的刻画——它等于一类特殊 Hessenberg 矩阵 的行列式——再联想到（特殊）分段安全里随机化子“一个接一个不再出现”的要求，很容易猜想：对任意函数，最小规模分段安全 AKGS 的乱码化规模和最小规模 ABP 表示的规模应该有关系。
如果尝试证明这个猜想，会发现有一点点小问题，尝试过程中可以发现稍微修改一下就很容易证明了：
定理 若 具有乱码化规模为 的分段安全 AKGS，则存在恒不为零的函数 使 和 都可由规模 的 ABP 计算。这里 ABP 的规模指的是对应图的节点数。
这个定理的证明目前没有收录在任何文献中，不过它也只是一道简单习题，捣鼓捣鼓一些已知结论就出来了。
证明提示
- 不妨设 AKGS 特殊分段安全，从特殊分段安全的角度来看，恒非零的函数只有一个自然选择。
- 从 ABP AKGS 标签函数的形式角度看，有一种最显然的方式来定义一个规模为 的 ABP。
- 利用 IW14 里化 ABP 矩阵为标准形的思路。
- 利用 AKGS 正确性和 ABP 的行列式刻画 IK02 得出所构造的 ABP 计算的函数，这便会是所要的结论。
限界 因 恒不为零，就 ABE 的目的来说 和 没区别，所以目前主系列博文即 LL20 所用的方法构造的 ABE 只能支持可用多项式规模的 ABP 表达的策略。目前基于标准假设的适应性安全 ABE 所支持最大的函数类便是 ABP 了，要想在适应性安全性上有所突破，势必要有新思路。顺便一提，多项式规模 ABP 的表达能力大约相当于 即 LL20 标题所言 “… and Towards NL”。
问题
现在我们对分段安全 AKGS 已经有了一些认识：分段安全等价于特殊分段安全，等价于 ABP（差一个非零因子）。此外，显然不是所有 AKGS 都分段安全——比如我可以加一个没有意义的恒为零的标签函数，那它就不符合分段安全的要求。
分段安全的 AKGS 总是可以通过“设置 为随机再反解 来模拟。从追求性质刻画简洁性的角度，自然会问：若 AKGS 有这种模拟策略，是否表明它一定分段安全？
另一个对密码学更有意思的自然问题：是否可以稍微放松分段安全性的要求，使它可以被更大的函数类的 AKGS 所满足，且仍然能证明 1-ABE 的适应性安全性？
请启用 JavaScript 来查看由 Disqus 驱动的评论。