关于多权威属性加密论文阅读

来源于2007年Multi-authority Attribute Based Encryption

从单权威机构到多权威机构的意义是什么呢？

基础方案（单权威方案SW）支持数据持有者对数据进行加密使用指定的属性集合并且指定一个数值d。当一个用户需要使用该数据时，需要满足至少拥有该属性集合中d个属性时，才能解密成功拿到原数据。文中举了一个例子如下：发件人对消息进行加密，当用于如下三个属性（罗德岛州驾驶执照、罗德岛州选民登记或布朗大学的学生证）里面两个属性的用户拥有解密的能力。如用户A拥有布朗大学的学生证和罗德岛州选民登记他就可以解密发件人加密的消息。然而单权威方案的缺点就是这些属性都是来自一台可信赖的服务器，这台服务器需要监管所有的属性。现实中，驾照应该由交管所来管理，选民登记应该由委员会来管理，而学生证应该由学校管理。我们可以看到多权威方案的模式更加符合现实世界的运作，每个机构为管理一组属性（每一权威机构之间的属性是不不想交）。因此，多权威方案孕育而生，提高了系统的灵活性和可扩展性。

本论文的结果

本论文实现了多权威机构的基于属性加密，在方案中存在一个中心权威机构和k个属性权威机构以及用户。该方案支持发送者为每个权威机构k指定一组属性和数字dk，使得一个用户满足所有权威机构k中规定的至少dk的属性时才能解密。对于安全性来讲，该方案允许任意数量的属性权威被破坏，并保证加密的安全性，只要所需的属性不能完全从这些权威获得并且受信任的权威保持诚实。此外，论文中还对方案提出一些扩展，这些扩展将在下文出现。

改进中的困难和使用的技术

本文是思路是通过运行多个SW方案然后管理这些副本，实现从单权威到多权威。

抗合谋问题

对于基础方案SW，我们要预防用户的合谋攻击，合谋攻击的具体表现文中也提供了例子：假设用户A拥有学生证，而用户B拥有驾驶证。在上文中提到的例子中，我们说如果一个用户拥有学生证和驾驶证就可以解密数据，但是现在看来无论是用户A和用户B他们都没有满足条件因此他们不能对加密的数据进行解密。对于一个用户去解密数据的简化流程大致如下，他需要拿着他的属性向权威机构去申请密钥，每一个属性会有一个属性密钥，用户拿着这些密钥去解密，如果密钥的数量够的话。回到例子，现在用户A和B就是想要解密，他们就密谋，他们将自己的向权威机构申请的属性密码分享给对方，对方拿到后将其拼接起来然后就变成了一个可以解密的合法密钥。

因此，我们需要做的就是，让密钥拼不起来。基础方案SW中使用方法是，每一个用户的密钥是使用不同的随机共享秘密生产的，因此密钥数学上自然而然拼接不起来。

我们将单权威机构变成多权威机构遇到的困难之一也是需要满足抗合谋攻击这个问题，因为方案中出现了新的实体，我们不只要防止用户和用户，还要防止属性权威机构之间的合谋问题。SW方案可以防止当局下的用户的合谋问题。但是如果用户在不同权威机构下的合谋呢？如果有一个密文解密需要权威机构一的一些属性，和权威机构二的一些属性，此时用户A满足一的属性要求，用户B满足二的属性要求，那他们的密钥还是能不能合并？显然，我们的方案需要二者的密钥是不能合并的。我们需要注意，这一防合谋的实现并不是因为SW方案带来的。因为对于单一权威机构来讲，对于每一个用户，可以查看用户请求的所有属性并给出密钥，因此它可以轻松地适当地重新随机化秘密共享。（在多权威的机构下，因为如果我们只是简单的使用多个SW的副本，那么每个权威会为其用户随机化秘密共享，这样子有可能出现两个用户如A和B他们的秘密共享是相同的，因此导致密钥可以合起来。）多权限情况下，我们再次希望以不同的方式为每个用户分割秘密，这次将其分配给多个权限。然而，现在我们需要在当局之间没有任何沟通的情况下做到这一点。

解决方法

我们继续来考虑A和B的问题，存在两个权威机构一和权威机构二，情况一：如果A用户向一申请属性集合A1的密钥，B用户向二申请属性集合A2的密钥；情况二：用户A分别向一申请A1的密钥以及向二申请A2的密钥。对于权威机构来讲这两种情况如果只依据属性来讲，就是相同的情况。而我们上面说过SW的防合谋就是因为查看到用户请求的所有属性，因此他可以做出随机化秘密分享（这里我有点不明白，这么说SW方案不用需有相同属性的用户申请属性密钥么？我也没看过基础方案，这里暂且不讨论）。既然情况一样，对于情况一的两个用户来说，随机化的秘密就是一样的因此就可以拼接。

解决方案就是退一步海阔天空的感觉，也就是给用户加入全局标识符GID，有没有IBE的味道？有了GID就可以辨别这两种方案了。此时，我们要区别于IBE，就要做到这个GID不影响解密能力的主导权是属性决定的，因此引入了中心权威机构。

中心权威机构

中心权威机构的加入是为用户的 GID 提供一个设置密钥，每一个用户会将自己的GID发送给中心权威机构之后接收相应的密钥。这个密钥用于和用户重构的秘密值相结合后就可以得到致盲因子，然后就可以解密。每个属性权威机构都有一个为随机函数(PRF)，用来随机化秘密值。当用户向中心权威申请密钥时，中心权限机构会为每一个属性权威计算PRF的结果并作为每一个SW副本的秘密。总结来说，PRF 的使用意味着每个用户的密钥独立于任何其他用户的密钥，并且不可能共谋。然后中央机构给出必要的附加密钥，以确保如果我们在同一 GID 上计算每个 PRF，我们总是可以将结果组合起来以获得固定值，从而允许我们给出独立于 GID 的密文。

多权威机构构建过程

我们将从如何构建单权威方案直到构建多权威方案，一步一步说起。

首先第一步实现秘密共享，这一步直接用到了拉格朗日插值法。简单的理解就是说我们将秘密值y作为多项式p(0)，如果这个多项式是d-1次的，我们就可以通过d个点恢复出来(例如，在二维坐标轴上，知道两个点确定一个直线方程，知道三个点确定一个一次方程等等等)，而这些点你可以看做是用户的属性，这样子是不是一个用户如果拥有d个属性就可以恢复出这个多项式方程我们就可以算出p(0)=y了。方案一如下图：

接下来，要实现的就是指定属性。以上方案的缺点就是任何d个点都可以恢复出多项式来，也就是任何满足数量的属性可以重建秘密值y，这并不是我们想要的。因此我们的做法就是将每一个属性都对应一个数值，并且在加密的时候，提供指定属性数据。运用到了双线性映射方案二如下图：

这样子我们就完成了单权威的构建。对于目前方案依旧存在一个问题，就是如果一个用户满足一个密文解密的属性要求后，他就将获得永久的解密能力即使在之后他的属性不满足其他密文的属性要求。这是因为加密使用了固定的 $y$ ，这意味着每一次加密如果想要不一样，需要向解密者重新生成私钥，以便生成不同的 $y$ 。解决的办法是在附上一个随机数，密文的格式： $E=Y^s=e(g,g)^{ys}m$ ，这就保证了每一个密文都不同。现在解密需要 $g^{t_is}$ 和适应的 $s$ ，因为引入了随机数放在指数上，所以提供了额外的公钥。

上文提及到，使用多个SW副本来实现多权威。我们对多权威的要求是，一个用户需要满足所有属性权威机构至少d个属性才可能解密。第一个思路就是使用两次秘密分享的办法。一个用户对于第k个属性权威机构如果满足至少d个属性那么可以恢复出 $y_k$ （k权威机构所持的秘密），如果对于所有的属性权威机构用户都能恢复出秘密值，用户可以对这些秘密值相加最终得到主秘密 $y_0$ 。 $\sum_{k=1}^{K}Y_k=y_0$ ，方案具体构造如下：

上面的方案有一个问题，我们考虑如下情景，我们假设有k个用户和k个属性授权机构，第k个用户拥有第k个属性授权机构要求的属性，但不具有其他属性机构的属性。此时，这些用户会出现合谋的现象，每个用户都计算出自己达到要求的属性权威机构的秘密，之后将他们的秘密相乘起来得到主秘密。这代表着k个单独的用户拥有属性集 $A^k_C$ （累加起来就是 $A_C$ ）和一个用户拥有属性集 $A_C$ 是一样的。我们需要去识别每一个用户。解决的方法就是为每一个用户加上GID，用户必须向每一个权威机构提供相同的GID，以便接受一组一致的密钥。此外，唯一标识不会影响正常的解密能力。此外，我们为了防止不会出现合谋的现象。我们为每一个属性权威机构k去选择一个不同的随机值 $y_{k,u}$ ，由于 $y_{k,u'}$ 和 $y_{k,u}$ 是独立无关的所有不会出现能够合并的情况。

如果所有的权威机构都独立的选择 $y_{k,u}$ ，怎么保证对于不同的用户他们从自己的每一个权威机构重建的秘密值累加之和都为 $y_0$ 呢？有一种方法是让权威们互相沟通，这样就能确保他们选择的秘密最终累加起来会是最后的 $y_0$ ，但是我们不希望权威之间是互通，因为这些权威并不是完全可信的。此时，就运用到了我们先前提及到的中心权威机构，它不负责监管属性，而是知道各个属性权威机构设置秘密值的状态，由它来为各个权威机构分配 $y_{k,u}$ 。它使用秘密状态的信息提供一个秘密密钥，当该密钥与加密中给出的 $g^s$ 以及各个机构中获得的秘密值 $y_{k,u}$ 相结合起来就会为用户提供“主秘密”。具体的算法如下：

安全分析

我们将从基础的SW的安全分析过渡到本文提出方案的安全分析。

SW方案安全性分析

方案是选择id安全的，方案的底层困难问题是DBDH问题。

简单的说就是给定 $e(g,g)^{abc},e(g,g)^R$ 让敌手去区分。我们说如果存在一个敌手能够攻破SW方案，那么我们就可以利用这个敌手去解决BDH问题。（最终我们得出结果说解决了BDH问题，但是由于BDH是数学难题是解决不了的所以出现矛盾，我们最后得出结果就是不存在这样可以攻破我们方案的敌手）我们可以证明我们，即使在给定挑战密钥和自适应选择密文的密钥查询下，消息 $M_b=\frac{E}{e(g,g)^{y_0s}}$ 和随便的消息是不可区分的，进一步说明 $e(g,g)^{y_0s}$ 和 $G_2$ 中的其他元素是不可区分的。既然要归约到DBH问题，那我们就需要将问题实例嵌入到我们的方案中，我们设置 $s=c,y_0=ab$ 。

多权威机构安全性分析

我们可以将单权威对安全性的分析应用到多权威方案。在这里，我们说只要一个权威机构需求的属性条件，用户没有办法达到，我们就可以允许敌手发起对给定用户的私钥和属性私钥查询。所以，最坏的情况是除了某个k属性权威机构外，其余的权威机构的秘密敌手都能算出来，并且能够计算出用户私钥和 $g^s$ 的双线性配对。我们需要让

是不可计算的对于敌人来说。因此，我们必须将这个不可计算的值隐藏在 $y_{k,u}$ 上面。这个秘密是由用户属性不满足属性权威的机构来保存的，我们让这些属性权威机构的编号为 $\hat{k}$ ，并且设置 $y_{\hat{k},u}=ab+z_{k,u}b$ 。对于其他诚实的权威机构来讲，我们要求他们的秘密是可以计算的所以设置 $y_{{k},u}=z_{k,u}b$ 。

密钥查询设置

首先，为了确保归约的成功，我们需要对属性权威生成公钥。

公钥 $T_{k,i}=g^{t_{k,i}}$ ，我们分两种情况设置，如果属性是权威机构所需要的，由于后面的计算需要 $E_{k,i}=T_{k,i}^s=g^{t_{k,i}s}=g^{t_{k,i}c}$ 的存在，我们需要让这个是可以计算的。因此我们设置 $t_{k,i}=\beta _{{k,i}}$ 。对于属性不是权威机构所要求的，我们设置 $t_{k,i}=\beta _{{k,i}}b$ ，这样这些属性的 $E_{k,i}=T_{k,i}^s$ 就是不可计算的。

这里将属性权威分为两类清空，第一种情况是用户属性不满足条件的属性权威机构，第二种是用户属性满足的情况。对于第一种情况，我们需要设置计算不出来的密钥例如 $p(0)=ab+z_{k,u}b$ 。对于第二种情况，我们可以秘密 $p(0)=z_{k,u}b$ 。

对于第一种情况，我们设置了 $p(0)=ab+z_{k,u}b$ ，对于最多d-1个点，也就是对应的属性我们给这些属性私钥 $D_{k,i}=g^{p(i)/t_{k,i}}=g^{p(i)/\beta _{k,i}}$ 。我们通过插值法，选择d个点，定义一个多项式。对与挑战中的属性i，我们设置 $p(i)$ 是 $b$ 的一个倍数。我们已经有了 $p(0)$ 以及b个点，我们可以恢复多项式，对于其他的点我们可以通过插值来找到 $g^{p(i)/t_{k,i}}$ 是

$g^{p(0)/t_{k,i}}$ 和 $g^{p(j)/t_{k,i}}$ 的一个加权乘积。 $g^{p(j)/t_{k,i}}$ 这个将是B的一个倍数，对于 $g^{p(0)/t_{k,i}}=g^\frac{{(ab+z_{k,u}b)}}{b\beta _{k,i}}=g^\frac{{(a+z_{k,u})}}{\beta _{k,i}}$ 这也是可以计算的。

具体的安全归约如下图所示

扩展

现在我们能来说说对我们方案的一些扩展。第一个扩展是改变解密需要的属性数量值 $d_k$ ，在本方案我们视为每次需要的数量都是最大数量。将虚拟属性加入到我们的属性集合之中，每个用户也会获得虚拟属性对于的私钥。对于一个密文，如果想要将其需求的属性数量少于默认值 $d_{max}$ ,我们只需要在输出密文时，多附带上额外的 $E_i=T_i^s$ 。（用户可以在属性数目没达到需求数目的时候，使用虚拟属性重建秘密）

第二个扩展是第一个扩展的特例，可以无视某一权威机构（直接提供足够多的虚拟属性，我们就不需要管我们的属性是否满足该权威机构的条件了。）但是，如果这么做那么有一点麻烦就是需要用户还是需要去该权威获得到所以虚拟属性的密钥。为了解决这一问题，我们添加了一个权威机构属性 $k$ 对于每一个权威，同时添加公钥 $T_{Nk}=g^{t_{Nk}}$ ，以及给予每一个用户一个用于每个权威机构的秘密密钥 $D_{Nk}=g^{\frac{y_{k,u}}{T_{Nk}}}$ ，用了这个，对于被指定忽略的权威机构，我们直接通过公钥和用户的密钥来恢复权威的秘密达到了忽略属性是否满足条件的效果。

我们的方案目前是要求用户满足所有属性权威机构才能解密，因此第三个扩展是支持满足D个权威机构就可以解密。大体的思路就是用两次拉格朗日插值，足够的属性可以获得权威的秘密，足够的秘密直接获得主密钥。具体做法是中心权威机构给每个用户一个密钥 $D_{CA}=g^{P(k)-F_{s_k(u)}}$ ，然后每一个用户用其属性恢复 $F_{s_k(u)}$ 结合 $D_{CA}=g^{P(k)-F_{s_k(u)}}$ 得到 $g^{P(k)}$ 最后在恢复出秘密之 $P(0)$ 。

此外，还可以为我们的方案在任何时候添加属性权威机构以及将我们多权威的方案是为单一授权CNF属性加密。在后者中，每一个权威机构对应于一个句子。唯一的计算开销是每个权威机构中属性不能重复，对于这个问题的解决方法是每一个属性创建独立的副本（也就是即使是相同的属性：学生证，在权威机构一获得的对应属性密钥和在权威机构二中获得是不一样的）