一种可证安全的密钥隔离无证书代理重加密方案

何粒波，卢震宇，耿贞伟，秦志光

(1.电子科技大学信息与软件工程学院 成都 610054；2.云南电网有限责任公司信息中心 昆明 650000)

代理重加密机制是文献[1]提出的一种特殊的公钥加密体制。在代理重加密的加密系统里，一个由Bob公钥生成的密文可由不可信的代理服务器转化为在Alice公钥下生成的密文，Alice可使用自己的私钥解密出明文。在整个代理重加密的过程中，代理服务器无法解密密文或获取任何用户的私钥。由于密文转化的功能，这一加密系统非常适用于构建针对云计算的安全数据共享方案。为提高代理重加密方案的安全性和效率，大量的代理重加密体制陆续出现[2-7]。但在基于传统公钥证书框架下提出的代理重加密体制本身存在着复杂的公钥证书管理的缺陷(如证书的生成、传输、验证、存储及废除)。于是，文献[8]在2007年提出了第一个基于身份基的代理重加密体制。随后，这一研究领域成为热点。学术界涌现了大量的基于身份基的代理重加密体制[9-11]，在这种加密体制里，由于公钥可以直接由用户的属性(如用户的电子邮件)生成，所以避免了使用基于公钥加密的代理重加密体制里复杂的公钥基础。但是由于私钥是由私钥生成中心生成的，所以基于身份的代理重加密体制存在着密钥托管问题。鉴于此，文献[12]在2010年提出了第一个无证书代理重加密体制。这种加密体制可以避免采用复杂的公钥管理体制，也解决了密钥托管问题，从而使得代理重加密这一密码学原语被更加广泛地应用于不同的场景中。

随着社会工程学与边信道攻击的快速发展，用户的私钥面临着前所未有的威胁。一旦用户私钥泄露，整个公钥密码体制的安全性将面临灭顶威胁。文献[13]提出了第一个密钥隔离的公钥密码体制，在系统里增加了一个物理安全的部件(称之为协助器)，整个系统的时间分为n个碎片，在每一个时间片里，协助器生成一个新的协助器私钥，作为用户私钥的一部分，通过这种方法，用户的私钥在每一个时间片里被更新。即使前面时间片的私钥暴露了，也不会泄露后面时间片的私钥。考虑到目前有的代理重加密方案都未考虑密钥泄露带来的威胁，本文结合密钥隔离的思想提出具有抗密钥泄露功能的无证书代理重加密方案。本文的贡献如下：1)通过结合密钥隔离和无证书代理重加密方案，给出了密钥隔离无证书代理重加密方案的形式化定义和安全模型；2)采用构建于椭圆曲线密钥体制上的双线性映射工具，提出了一个密钥隔离无证书代理重加密方案的具体方案；3)在随机预言机模型中给出了所提方案的安全性证明，同时采用Miracl库函数具体实现了该方案，实验结果表明该方案高效实用；4)利用该方案设计了一个基于云计算的适用于移动互联网的安全数据共享协议。

2 形式化定义和安全模型

本章讨论了密钥隔离无证书代理重加密体制(KI-CLPRE)的形式化定义、KI-CLPRE体制的IND-CPA安全证明模型及相关困难问题假设。

2.1 形式化定义

KI-CLPRE体制由以下11个算法构成：

Setup：算法输入安全参数k，输出系统参数params、master-key和master-helper-key。

SetSecretVal：算法输入params，用户A身份输出秘密值

HelperKeyUpdate：算法输入params，masterhelper-key，用户A身份IDA和时间周期i，输出用户A的第i个时刻的协助器密钥

PartialKeyExtract：算法输入params，master-key和用户A身份IDA，输出用户A的部分密钥

SetPrivateKey：算法输入params、iψ、EA、SA和时间周期i，输出用户A第i个时刻的密钥

SetPublicKey：算法输入params、PA和SA，算法输出用户A公钥

SetReEncKey：算法输入PKA、SKA、PKB，用户A的身份IDA，用户B的身份IDB和时间周期i，输出第i个时刻的重加密密钥

Encrypt：算法输入params、明文m、用户A身份IDA、PKA和时间周期i，输出第i个时刻的

ReEncrypt：算法输入 params、 RKA→B、和时间周期i，输出第i个时刻的

Decrypt1：算法输入params、RKA→B、和时间周期i，输出明文m。

Decrypt2：算法输入params、SKA和时间周期i，输出明文m。

2.2 安全模型

本文定义KI-CLPRE的IND-CPA语义安全模型。在这个安全模型里，攻击者可被分为两类：第一类攻击者A1和第二类攻击者A2。第一类攻击者A1代表恶意的第三方，它不能获得master-key和masterhelper-key，但是它能够知道秘密值，可以任意值重置公钥；第二类攻击者A2代表一个诚实但好奇的密钥生成中心，可以获得master-key和master-helperkey，不能得知秘密值，所以不能替换公钥。在代理重加密的加密体制里有两种不同级别的密文，据此，本文将分别建立KI-CLPRE在IND-CPA游戏中对一级密文和二级密文的安全模型。

在KI-CLPRE体制中攻击者可能执行的预言机：

Set-Secret-Value：攻击者A输入参数ID，询问预言机Set-Secret-Value，挑战者S返回秘密值给A。

Helper-Key-Update：攻击者A输入参数ID和时间周期i，询问预言机Helper-Key-Update，挑战者S返回用户的第i个时刻的协助器密钥iψ=给A。

Partial-Key-Extract：攻击者A输入参数ID，询问预言机Partial-Key-Extract，挑战者S返回用户的部分密钥给A。

Set-Private-Key：攻击者A输入参数ID和时间周期i，询问预言机Set-Private-Key，挑战者S返回用户第i个时刻的密钥给A。

Set-Public-Key：攻击者A输入参数ID，询问预言机Set-Public-Key，挑战者S返回输出用户公钥给A。

Set-ReEncrypt-Key：攻击者A输入参数ID和时间周期i，询问预言机Set-ReEncrypt-Key，挑战者S返回输出第i个时刻的重加密密钥RKA→B=给A。

Public-Key-Replace：A可以通过询问Public-Key-Replace预言机，用自己选择的秘密值来重置公钥PA。

game1_level1_ciphertext(第一类攻击者A1基于一级密文对于KI-CLPRE体制的IND-CPA游戏)：

系统建立阶段：输入安全系数k，挑战者S执行Setup算法，并返回除了master-key和masterhelper-key的系统参数params给A1。

第一阶段：A1适当询问以下的预言机：Helper-Key-Update、Partial-Key-Extract、Set-Private-Key、Set-Public-Key、Set-ReEncrypt-Key、Public-Key-Replace。询问这些预言机时，A1需要遵守对其的行为限定规则。

挑战阶段：一旦A1决定第一阶段结束，A1选择一个挑战身份*ID进行挑战，并输出两个等长的明文挑战者S随机地选择一个比特，并计算出挑战的密文并将密文C∗返回给A1。

猜测阶段：最后，A1输出一个猜测比特如果b′=b，则A1获胜。

对A1的行为限定规则：攻击者A1为外部用户，所以无法获取密钥生成中心的主密钥，但可以用任意值替换用户公钥。特别的，A1无法替换挑战中的用户ID∗的公钥。

游戏game2_level1_ciphertext(第二类攻击者A2基于一级密文对于KI-CLPRE体制的IND-CPA游戏)与游戏game1_level1_ciphertext类似，不再赘述。

game1_level2_ciphertext(第一种类型的攻击者基于二级密文对于KI-CLPRE体制的IND-CPA游戏)：

系统建立阶段：输入安全系数k，挑战者S执行Setup算法，并返回除了master-key和masterhelper-key的系统参数params给A1。

第一阶段：A1适当询问以下的预言机：Helper-Key-Update、Partial-Key-Extract、Set-Private-Key、Set-Public-Key、Set-ReEncrypt-Key、Public-Key-Replace。询问这些预言机时，A1需要遵守对其的行为限定规则。

挑战阶段：一旦A1决定第一阶段结束，A1选择一个挑战身份ID∗进行挑战，并输出两个等长的明文挑战者S随机地选择一个比特并计算出挑战的密文并将密文C*返回给A1。

猜测阶段：最后，A1输出一个猜测比特如果b′=b，则A1获胜。

对A1的行为限定规则：攻击者A1为外部用户，所以无法获取密钥生成中心的主密钥，但可以用任意值替换用户公钥。特别的，A1无法替换挑战中的用户ID∗的公钥。

游戏game2_level2_ciphertext (第二类攻击者A2基于二级密文对于KI-CLPRE体制的IND-CPA游戏)与游戏game1_level2_ciphertext类似，不再赘述。

2.3 相关困难问题

计算Diffie-Hellman(CDH)问题：给定一个阶为q的循环群G，g为它的生成元。随机选定的值，给定计算出abg的值非常困难。

3 方案构造

本文在无证书代理重加密体制CLPRE[14]的基础上构造了具有密钥隔离功能的密钥隔离无证书代理重加密体制KI-CLPRE。具体方案如下：

1)Setup(k)： 给定一个安全参数k，Setup算法运行如下：

输入一个安全参数k，生成一个q阶的乘法循环群G。选择一个群G的生成元g。

选择加密哈希函数：

4 安全证明

证明：将规约到计算Diffie-Hellman困难问题上进行安全证明。设定计算Diffie-Hellman问题，挑战者S利用攻击者A1来计算出。当game1_level1_ciphertext游戏开始后，由于攻击者A1为外部用户，所以该攻击者无法获取密钥生成中心的主密钥master-key。挑战者S设定y=gx=ga，并且模拟哈希函数为随机预言机。之后，设置在仿真试验中，挑战者需要在一个时间片内猜测目标明文中的每一位。在挑战阶段，挑战者S返回一个一级密文

其中：

显然，在ξ中均为已知，所以可以得到xrg即为CDH问题的解，即攻击者A1只有在解决CDH问题之后才能对所提方案中的一级密文进行解密。故本文的方案在随机预言机模型下是CPA安全的。

证明：将规约到计算Diffie-Hellman困难问题上进行安全证明。设定计算Diffie-Hellman问题，挑战者S利用攻击者A2来计算出。当game1_level1_ciphertext游戏开始后，由于攻击者A2为恶意的密钥生成中心，所以该攻击者可以获取密钥生成中心的主密钥master-key，但无法获得用户的密钥等参数。挑战者S设定并且模拟哈希函数为随机预言机。之后，设置在仿真试验中，挑战者需要在一个时间片内猜测目标明文中的每一位。在挑战阶段，挑战者S返回一个一级密文

其中：

显然，在ξ中gSA、及均为已知，所以挑战者可以获得ZArg即为CDH困难性问题的解。即攻击者A2只有在解决CDH问题之后才能对本文方案中的一级密文进行解密。故本文的方案在随机预言机模型下是CPA安全的。

证明：将规约到计算Diffie-Hellman困难问题上进行安全性证明。由于本文方案中一级密文与二级密文加密算法一致，所以安全性证明与定理1类似，不再赘述。攻击者A1只有在解决CDH问题之后才能对所提方案中的二级密文进行解密。故本文的方案在随机预言机模型下是CPA安全的。

证明：将规约到计算Diffie-Hellman困难问题上进行安全性证明。由于本文方案中一级密文与二级密文加密算法一致，所以安全性证明与定理2类似，不再赘述。攻击者A2只有在解决CDH问题之后才能对所提方案中的二级密文进行解密。故本文的方案在随机预言机模型下是CPA安全的。

5 性能分析

在密钥隔离无证书代理重加密体制KI-CLPRE方案中，A方和B方由KGC周期性得提供一个协助器密钥，从而得以在每个时间片更新各自的重加密密钥。该方法虽然增加了方案的执行时间，但是由于每个时间片的重加密密钥都得以更新，所以即使单个时间片的重加密密钥被泄露，却仍然保密了其他时间片的重加密密钥，减少了系统在复杂环境下密钥泄露问题，提高了方案的安全性。接下来，将本文的方案与文献[12]和文献[14]的方案进行性能和安全的对比分析。

te代表在群G中指数运算的执行时间，tp代表对运算的执行时间，分别代表群中元素的长度以及群TG元素的长度，代表随机数的长度，代表消息m的长度，代表签名的长度。

由表1可知，就执行效率而言，在文献[14]和文献[12]的方案中Encrypt、SetReEncrypt、算法的执行时间分别为，而在本文的方案中，执行上述算法的时间为4te、4te、te、3te、te，由此可知，本文方案和文献[14]的方案相当，而明显高于文献[12]的方案。就重加密密钥、原始密文以及转换密文长度而言，本文方案中的长度为而文献[14]和文献[12]的方案中对应长度分别为以及上述结论同样成立。就功能来说，本文方案在基于CDH困难问题的前提下能够达到CPA安全，并且能提供无证书和抗密钥泄露两种功能。虽然安全性达不到文献[12]方案中的CCA安全，但是文献[12]的方案不能提供抗密钥泄露和无证书两种功能，并且效率明显低于本文的方案。文献[14]的方案在性能方面和本文方案大致相当，但没有提供抗密钥泄露的功能。

综上所述，本文方案和文献[14]的方案相比，具有更多功能，比文献[12]的方案在效率方面具有明显的优势。表2给出了与表1相对应的定量分析，该数据证实了上述性能分析结论。图1～图4是几种方案在加密的消耗时间、一级密文解密时间以及二级密文解密时间方面的比较。本文方案通过周期性得更新密钥，提供了密钥隔离功能，减缓了在复杂环境下的密钥泄露问题。

表1 本文方案和文献[14]、文献[12]方案的性能对比

表2 对表1性能定量分析的对比

图2 不同方案一级密文解密所需时间的比较

图3 不同方案二级密文解密所需时间的比较

图4 应用场景

6 应用场景

基于无证书的密钥隔离代理重加密系统可以应用到受到私钥泄露问题困扰的一系列实际环境中。达到取消证书机构、避免密钥托管问题和降低密钥泄露的危害的目的。

将本文方案部署到手机邮件应用程序，如图4所示，该环境下系统对时间分片。每个用户持有手机和对应的充电器，充电器作为协助器，密钥分发中心(KGC)负责生成用户的部分私钥。例如，在该系统中，用户Alice想给用户Bob发送一份邮件m。首先，KGC将Alice的公钥PA部分私钥EA发给Alice，然后Alice在自己的手机上生成秘密值SA，并使用充电器生成时间片i下的协助器密钥ψA,i，利用这三部分信息，Alice将私钥更新为对应系统时间片i下的私钥同理，Bob按照这种方式得到自己的公私钥对。Alice计算出由Alice到Bob的重加密密钥RKA→B和邮件m对应的密文CA,i，将RKA→B和CA,i发送给重加密服务器。重加密服务器将CA,i转换为Bob使用自己的私钥就可以解密CB,i得到m。假设恶意的攻击者Malice想偷看Alice发给Bob的邮件，Malice偷取了Bob的手机，但由于Malice无法得到Bob的充电器(协助器)，因此无法得到最新的私钥，所以即使手机丢失，加密的内容仍然能保持机密性。

7 结束语

KI-CLPRE体制是将密钥隔离的功能嵌入到代理重加密体制而形成的。这种新的体制将时间分为n个时间片，在每个时间片周期性得更新用户的密钥和重加密密钥，即使在某个时期，用户的密钥或重加密密钥被泄露，也不会影响到系统在其它的时间片的安全性。从而，KI-CLPRE体制的私钥暴露问题在恶劣的实际环境中得到了减少。本文首先形式化定义了KI-CLPRE体制，并给出了安全模型和相关困难问题假设。接着，给出了KI-CLPRE体制的具体结构。最后，在随机预言机模型里，论证了KI-CLPRE体制在IND-CPA游戏里的安全性。