格密码学进阶之六：ABE属性加密（BGG+14）

Original 东泽安比技术社区 2020-10-13 12:30

收录于合集

本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。

Lattice ABE的大致结构

上一期我们看到了【AFV11】的内积ABE的构造。在AFV11中，密文中带有向量，而解密者拥有向量。如果，那么解密者就可以成功的用他的密钥解开密文。

在上期最后，我们给出了基于格的ABE属性加密的大致结构。我们一共需要三个部分：

首先，我们需要把要加密的原文使用一组随机选择生成的One-Time Pad 覆盖住：

这里的是公开的，而与都是加密方自己随机生成的。

随后，解密的目的就在于计算出近似的值，然后就可以从中移除这个OTP，进而还原出。我们目前先把这个密文放在一边，来构造属性密文。我们想要把加密方选择的属性输入变相的encode在密文当中。假设属性输入为一系列的二进制向量，我们根据每一个输入构建一个对应的密文：

其中是事先公开生成的，而与都是加密方选择的，其中的值需要和之前的一致。

我们观察发现，如果解密方可以在一系列的密文上直接同态计算一个属性函数，那么就可以得到一个带有的功能信息的密文：

这个时候就和我们上期观察到的一样，只要，那么带有信息的部分就从这个密文中消失了，整个密文就变成了一个描述函数的encoding：

因为只需要知道公共参数和就可以计算出来了，所以我们就可以实现计算出并且使用MP12 Trapdoor生成对应的密钥：

当解密者拥有了，成功的在密文上同态计算了，并且恰巧的时候，他就可以直接把得到的结果乘以密钥而得到一个近似于的值！

这样一来，解密方就可以从原本的密文中移除这个OTP，再进行一些thresholding过滤掉噪音，就可以还原原本的密文啦。

AFV11回顾

在上期的结尾也提到过，如果用这个视角看【AFV11】的话，其实AFV11就是实现了所有线性组合的下的ABE。这也就是说，我们可以通过同态计算来得到属性与约束的内积：

此时，如果内积恰好是0，并且解密方拥有对应的密钥的话，那就可以通过我们上述提到的ABE框架来进行解密了。

【BGG+14】扩展至所有functionality

因为在AFV11中，解密方已知了向量的值，所以在进行同态计算的时候，等于只需要进行加法计算而已，并不需要乘法。

熟悉FHE体系（比如GSW）的话，就会知道如果我们想要支持所有的functionality的话，那我们需要同时支持对于密文的加法与乘法。我们在这里一样，虽然说属性本身是公开的，并不是密文的主体（我们的目的不在于隐藏属性），但是我们是用一种与GSW非常相似的encoding把属性嵌入进密文中的。所以说，我们也需要支持对于属性encoding的加法与乘法。

属性相加

我们先来看看在之前已经实现过的属性相加。为了方便描述，我们再次定义一下问题：

给定一个属性，我们使用矩阵来encode这个属性：

假如我们拥有属性的encoding ，与属性的encoding ，我们能否结合这两个encoding，并且获得的encoding呢？

这个问题的答案非常的trivial，我们只需要相加即可：

注意我们这里把两边的噪声项合并成了一个新的噪声项，为了方便表述。这并不影响正确性。

还有一点很重要的observation是：当我们合并了两个encoding之后，里面的矩阵也变成了新的构造。如果是相加的话，那么新的矩阵就是之前的两者相加。

属性相乘

真正麻烦的在于相乘。假如我们拥有同样的encoding ，我们能否获得的encoding 呢？

我们先写出我们想要得到的encoding 的构造：

乍一看，如果我们就拥有与的话，我们似乎没有办法相加或者相乘来得到我们想要的encoding的样子。这似乎有点像GSW FHE的同态乘法计算，如果我们强行把两个encoding相乘的话，最后我们得到的结果会带来很大的噪音和多余项。

【BGG+14】中一个非常重要的发现在于：虽然我们在这里在做类似GSW的同态计算，但是其实我们的要求和FHE完全不同！在FHE中，我们的要求在于隐藏密文中的值，然而在这里ABE的应用当中，属性输入是可以完全公开的。这也就是说，解密方可以让加密方额外的提供一份向量，和密文一起发送过来，然后基于的值来进行encoding的合并计算。这一点优势是FHE中不存在的。

接下来，我们来看看，如果拥有了明文的，我们如何计算相乘：

这里的就是我们在GSW FHE中提到的binary decomposition（二进制分解）函数，满足了：

因为二进制分解态的与属性都只包含了0或者1这两个值，所以它们和原本的encoding中的噪声项相乘所得到的额外噪声是可以忽略不计的，所以我们把它们通通都合并到了中。

我们在这里再次仔细观察一下新的矩阵的构造：

这一结构与GSW中的同态乘法计算方法完全一样！非常的神奇，我们在这里的矩阵虽然就是一个随机生成的矩阵，并不是一个密文，但是我们进行属性相乘计算的时候，多个矩阵会按照GSW的模式巧妙的结合在一起。

基于属性计算任意功能f

现在，当我们掌握了加法与乘法之后，我们就可以通过任意组合这两种方法，来计算任何功能了。给定一个想要计算的，我们要做的就是把功能的计算分解为一个个加法与乘法的组合。随后，只要我们拥有所有属性的encoding 以及属性向量，我们就可以通过上面描述的方法来计算的encoding了！

生成对应密钥

当我们可以计算对于属性的encoding的任意加法与乘法之后，我们也就真正实现了开头所描述的表达式：

在这里，可以是任何复杂度的函数。我们只需要对应着的复杂度选取模组与噪音的参数大小即可。

由于我们在这里的目标是ABE，所以我们需要生成一个密钥，使得当的时候，拥有这个密钥的解密者可以成功的解开密文。

根据要求，我们来看看当的时候，整个属性的encoding是什么样子的：

我们发现，和之前AFV11一样，整个encoding中失去了所有对于属性的信息！唯一剩下的就是矩阵，我们来看看它的构造是怎么样的。

之前我们观察到了在加法与乘法中，矩阵的变化：

观察可以发现，矩阵一路的变化，和我们evaluate的functionality 是直接挂钩的。这个矩阵的值就等于是蕴含了我们对于属性计算所做的这个functionality的所有信息。这也就是说，已知了我们要计算的，就算不知道的值，我们也可以实现通过GSW的Eval规则计算出一个恒定的出来！

矩阵只依靠与而独立于属性这一特点，恰巧就是生成ABE密钥的绝佳选择。假如我们想要生成关于某个验证函数的密钥，那我们只需要根据这个函数的构造计算出对应的来，然后使用我们之前预留好的Trapdoor来生成一个短向量使得：

这里的就是在AFV11中也使用过的一个带有Trapdoor的随机分布矩阵了。因为是纯随机（没有后门的），它存在的作用就是让管理员可以根据MSK（即Trapdoor）生成密钥。

解开ABE密文

解开密文的方法非常简单，当我们成功的组合出一个类似于一样的结构之后，我们就可以把它乘以我们的密钥，就可以得到了。接下来，就只需要从密文中移除这个OTP，原文就出来了。

BGG+14 ABE的具体结构

当我们了解了【BGG+14】的主要思路之后，为了完整性，我们列出整个ABE的结构。

公共参数生成

首先，我们需要使用MP12的方法生成一个随机平均分布的矩阵与对应的Trapdoor 。然后我们根据属性输入向量的长度，生成个随机分布的矩阵，注意这里的矩阵是直接随机sample的，没有Trapdoor。最后，我们选择一个随机的向量，作为SIS问题。

随后，我们公开整个系统的MPK为，MSK为。

密钥生成

拥有MSK的ABE系统管理员可以生成对应任何属性函数的密钥。要做的事情和我们之前表述的一样，基于使用类似于GSW的方法“同态”计算，最后得到对应的矩阵。

当我们得到对应了的矩阵之后，我们使用Trapdoor 生成密钥使得：

随后，管理员可以把发给Alice，作为她的属性函数密钥。

属性加密

当Bob想要加密一个密文的时候，他可以自己选择一个属性向量，作为解密方属性验证函数的输入。Bob使用如下的方法把的每一个bit嵌入在类似于GSW的密文中：

其中是Bob自己选择的随机向量（blinding factor），也是随机生成的符合噪声分布的噪声向量。

为了使得Alice的密钥在满足属性函数验证的时候可以成功解密，Bob还需要输出一个带有blinding factor的矩阵：

最后，Bob使用作为OTP来加密他真正的密文：

Bob输出这四项作为密文。

属性验证解密

当Alice看到Bob的密文这四项的时候，她先使用最后的两项来同态计算：

这里的函数就和我们之前表述的计算方法一样，把拆分成一个个的加法与乘法运算，然后依次的选择对应的encoding ，根据需求计算或者。在计算encoding的乘法的时候，注意还需要用到的值，不过在这里Bob也给我们了。

当我们组成了之后，Alice就可以把它与拼接起来，组成最终形态：

得到这个形态之后，Alice可以直接乘上她的密钥。根据密钥生成的定义，我们可知：

最后，Alice把得到的结果从密文中减去，还原出最终的消息：

这就是【BGG+14】ABE的全貌了。

BGG+14 ABE的安全论证

了解完BGG+14的correctness之后，下面来看一下security。

我们在之前的文章中已经做了IBE系统的security proof，这里ABE的安全论证其实也非常相似，一共分为三个阶段：

首先Adversary需要选择他的一个特有的attribute ，并且发送给Challenger。Challenger生成ABE的公共参数，把参数发回给Adversary。
随后，Adversary可以开始进行一系列的Key Queries。在ABE的场景中，Adversary可以向我们发送多个属性函数，唯一的要求在于这些函数都不能验证通过Adversary本身的属性。我们需要计算对应的密钥并且返还给Adversary。这些输出的密钥都必须要满足BGG+14 ABE的correctness要求。
最后，Adversary选择两条消息发送给我们。我们需要随机的选择一个bit ，并且根据结果使用属性来加密并且发送一系列的密文给Adversary。如果Adversary可以辨别密文中究竟是还是，那么我们就可以用这个Adversary来破解Lattice中公认困难的问题。

乍一看，整体的流程和之前IBE差不多，但是我们发现这里对于Challenger的要求就更高了。我们需要在不知道MSK（即矩阵的Trapdoor），以及不知道对应的密钥的情况下可以成功的回答Key Queries。并且我们需要能够在最后的challenge中嵌入一个格中的难题（SIS/LWE），以便确保Adversary无法破解密文。

接下来，我们来仔细看一看每个部分是如何完成的。

公共参数生成

作为Challenger，我们在生成公共参数的时候就已经知道了Adversary选择的属性。我们需要做的和之前的ABB10结构大致相同，需要想办法把“嵌入”在公共参数中，使得我们在的时候拥有Trapdoor，可以生成任意的ABE密钥。

由于我们不能拥有真正的MSK，所以我们只能选择一个平均随机分布的没有Trapdoor的矩阵。但是我们对于加密属性用的矩阵的定义稍作改变：

其中是一个随机选择的短矩阵。因为Leftover Hash Lemma，我们知道也是平均随机分布的，这也就是说simulation的公共参数和实际ABE的transcript分布是statistically close的！

Key Queries

首先，我们看一看如何回答Key Queries。当我们想要给一个无法验证的functionality 签发密钥的话，我们可以和正常的密钥签发一样，在上同态计算。根据同态的性质，我们最后得到的表达式也会和的构造类似：

随后，我们需要通过某个Trapdoor，找到一个短向量使得能够满足原本的SIS等式：

并且我们要确保只有当的时候，这个Trapdoor才能存在。

这一点很简单，我们重新回顾一下MP12的构造。在MP12中，我们需要一个平均随机分布的矩阵，和一个高斯分布的短矩阵。我们设定，就可以构造如下的矩阵结构：

这和之前介绍的Lattice Trapdoor稍微不同的地方在于多了这一项，并且相减的顺序变了。但是这些细节并不影响我们找到Trapdoor，唯一的要求在于需要在模组中可逆。

当我们可以把转换到之后，MP12 Trapdoor已经构建完成了。之后我们可以把所有对应的SIS/LWE问题转换到下轻松解决，我们也就可以生成所需要的了。

Challenge Ciphertext

最后，我们来看一下Challenge Ciphertext是如何构造的。

基于我们当前的矩阵构造，当我们生成基于属性的密文的时候，密文中的部分的构造如下：

这样一来，就失去了所有带有的部分，变成了一个纯LWE的结构。因为Adversary不知道Trapdoor ，也不知道，所以如果可以通过这个密文成功的构造出并且成功解密的话，那么就等于Adversary需要从这些LWE sample中提取出的信息出来。如果Adversary能够有non-negligible advantage可以做到这一点，那么这就代表Adversary可以解开LWE难题了。

Q.E.D.

写在最后

在BGG+14 ABE中，我们发现有两种方式可以“同态”的计算“密文”。

一种方式是对于属性的encoding ，我们可以在已知的情况下同态的计算任何functionality ，得到。