在多级秘密共享方案中, 每级存取结构里的授权集中参与者可联合重构对应的秘密. 但在实际中, 腐化了非授权集的攻击者可通过内存攻击获取部分或全部其余参与者的份额信息, 从而非法得到部分甚至是全部的秘密信息. 面对这样的内存泄漏, 现有的多级秘密共享方案都不再安全. 基于此, 首先给出了抗内存泄漏的多级秘密共享对选择秘密攻击不可区分的形式化的计算安全模型. 然后, 利用物理不可克隆函数及模糊提取器的联合作用, 基于极小线性码构造了一个适用于一般存取结构的抗内存泄露的可验证多级秘密共享方案. 同时, 在内存攻击者存在的情况下, 证明方案在随机预言模型下是计算安全的. 最后, 将所提出方案与现有方案在性能和计算复杂度两方面进行了比较分析.
In the multi-stage secret sharing scheme, the participants of authorized sets in each level of access structures can jointly reconstruct the corresponding secret. But in reality, adversaries who corrupted an unauthorized set can obtain some or even all of the share information of the uncorrupted participants through memory attacks, thereby illegally obtaining some or even all of the shared secrets. Facing with such memory leaks, the existing multi-stage secret sharing schemes are no longer secure. Based on this, this study firstly proposes a formal computational security model of indistinguishable ability against chosen secret attack for multi-stage secret sharing. Then, using the combination of the physical unclonable function and the fuzzy extractor, a verifiable memory leakage-resistant multi- stage secret sharing scheme for general access structures is constructed based on the minimal linear codes. Furthermore, in the presence of a memory attacker, it is proved that the scheme is computational secure in the random oracle model. Finally, the proposed scheme is compared with the existing schemes in terms of their properties and computational complexity.
秘密共享是现代密码学领域的重要分支, 在信息安全存储、群组密钥协商、多方安全计算及面向组的分布式安全协议等方面均具有重要的应用价值. 秘密共享方法一般是在一组参与者集合
然而, 很多秘密共享方案一次只能共享一个秘密, 在实际应用中, 我们需要共享多个秘密. 比如, 密钥分配机构需要为不同的保险柜分配不同的密钥, 此时有3种方法: 一种是为每一个密钥分别建立一个单秘密共享方案, 但每个参与方的子份额太多; 另一种称为一般多秘密共享方案[
另外, 现有的秘密共享安全性分析均基于腐化了非授权集的攻击者无法再获得其他未腐化参与者的内存信息这一前提. 而实际中, 参与者的长期秘密份额通常保管在非易失性的内存中, 敌手可以通过内存攻击得到非易失性的内存里的秘密信息, 此时, 秘密共享安全性分析的假设便不再成立. 因此, 面对存储信息的泄露, 现有的绝大多数的多秘密共享方案已不再安全. 针对上述问题, 文献[
基于以上讨论, 本文首先在内存泄露存在的情况下, 定义多级秘密共享的基于选择秘密攻击的不可区分实验的安全模型. 然后, 利用物理不可克隆函数以及模糊提取器提取相同的随机均匀分布的字符串(即秘密份额), 而不是将长期秘密份额保存在非易失性的内存里这一思想, 基于极小线性码构造了一个完全抗内存泄露的、多用的、可验证的可证安全多级秘密共享方案, 并证明了该方案是随机预言模型下计算安全的. 方案中每个参与者只需维护一个秘密份额, 就能实现不同的存取结构重构不同的秘密; 且相较于以往的(
一个[
在一个以
容易看出: 对于某个1≤
根据上述讨论,
物理不可克隆函数(physically unclonable functions, PUFs)是由Pappu等人于2002年首次提出的[
● 噪声有界性. 对一个激励
● 不可克隆性. 给定一个PUF, 对任意的激励
● 不可预测性. 假设一个PUF已接受过多项式次数的激励
正式地, 如果对于一个激励的集合
我们用(
在本文中, 我们利用PUFs替代存储在非易失性内存中的长期密钥. 但是显然, PUF是一个噪音函数, 即同一激励会产生不同的响应, 从而无法直接应用于密钥的产生. 为此, 我们使用了Dodis等人[
● Gen: {0, 1}
• Rep: {0, 1}
模糊提取器的正确性确保当
模糊提取器的安全性保证: 当输入的比特串
物理不可克隆函数与模糊提取器的联合作用即可产生密钥, 同一个PUF作用于同一个激励时会产生不同的响应, 但只要其差异足够小, 便可利用模糊提取器进行处理, 之后, 还是能得到唯一确定的均匀随机密钥(如
物理不可克隆函数与模糊提取器的结合机理
在本节中, 我们将详细描述一个秘密共享方案的内存泄露模型[
在现有的密码方案中, 绝大部分方案的长期秘密信息均存储在非易失性存储器中. 因此, 我们考虑如下的内存攻击者, 该攻击者不仅能够腐化非授权集合中的参与者, 而且还能获取其余未被腐化参与者的秘密信息的泄露信息.
在一个多级秘密共享方案中, 分发者想要在
一个多级秘密共享是一个四元组:
● 初始化算法Stp是以安全参数
● 分发算法
● 伪份额生成算法Sub是以秘密份额的集合
● 重构算法
一个多级秘密共享
(1) 正确性要求: 对任意一个
(2) 安全性要求: 对某些
抗内存泄露的多级秘密共享
● 初始化
攻击者
● 建立
挑战者运行参数建立过程
● 预备阶段
攻击者发出询问请求, 以获取被挑战参与者集合里参与者的份额.
● 挑战
挑战者随机选取
● 猜测
攻击者
定义攻击者
如果对任何多项式时间的攻击者
如果在完全内存攻击者存在的情况下, 多秘密共享方案是安全的, 则我们称这种方案是完全抗内存泄露的多秘密共享方案[
令
每个参与者
(1) 随机选择一个向量
(2) 计算
(3) 计算并公布
(4) 公开输出
假设授权集
(1) 每一个参与者
● 验证阶段:
(2) 若无欺诈,
(3) 根据线性码上秘密共享方案中秘密重构算法,
由于该方案最终重构秘密是基于极小线性码的对偶码上的多级秘密共享, 因此方案的存取结构满足以下定理.
证明: 设
且根据定义3, 生成矩阵的每个列向量均为非零向量, 即
例 1:由文献[
{2, 3, 4, 5, 6, 9, 11, 12, 13, 15, 17, 18, 19, 20}, {2, 3, 4, 5, 8, 10, 11, 12, 14, 16, 17, 18, 19, 20},
{5, 6, 8, 9, 10, 13, 14, 15, 16, 18, 19}, {2, 3, 6, 8, 9, 10, 12, 14, 15, 16, 17, 18, 19, 20}
{3, 4, 5, 8, 9, 10, 11, 13, 14, 16, 20}, {3, 4, 5, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18},
{2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20}, {4, 5, 6, 7, 9, 10, 12, 16, 17, 19, 20},
{3, 7, 8, 10, 11, 12, 15, 16, 17, 18, 20}, {2, 3, 5, 6, 8, 12, 13, 15, 16, 17, 20},
{2, 4, 5, 7, 11, 12, 14, 15, 16, 19, 20}, {2, 3, 4, 5, 6, 7, 8, 9, 12, 14, 15, 16, 18, 20},
{3, 4, 6, 10, 11, 13, 14, 15, 18, 19, 20}, {2, 3, 4, 5, 6, 7, 8, 11, 13, 14, 15, 17, 19, 20}.
{2, 3, 4, 5, 6, 7, 10, 12, 13, 14, 16, 18, 19, 20}, {2, 4, 8, 9, 11, 12, 13, 16, 17, 18, 19},
{2, 3, 4, 6, 7, 9, 13, 14, 16, 17, 18}, {2, 3, 4, 7, 9, 10, 11, 13, 15, 16, 17, 18, 19, 20},
{2, 5, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 20}, {2, 4, 5, 6, 9, 10, 11, 12, 14, 15, 17},
{4, 6, 7, 8, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20}, {2, 3, 6, 7, 8, 9, 11, 12, 14, 18, 19},
{2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19}, {2, 5, 6, 7, 8, 10, 11, 13, 17, 18, 20},
{3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 19, 20}, {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 17, 18, 19},
{2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 15, 16, 17, 19}.
证明: 令
因此, 存取结构
证明: 令
令
● 初始化
● 建立
挑战者
令
● 预备阶段
如果对于
● 挑战
对于其余的
● 猜测
对于
所以, 为了计算
令
由于
令
综上,
由此可知, 只要
注: 在定理3中, 因为参与者人数通常比哈希询问次数小, 所以
本节将所提出的多级秘密共享方案与文献[
多秘密共享方案的性能比较
性能 | 文献[ |
文献[ |
文献[ |
文献[ |
文献[ |
本文方案 |
多秘密 | 是 | 是 | 是 | 是 | 是 | 是 |
一般化的存取结构 | 是 | 是 | 是 | 否 | 否 | 是 |
可验证性 |
是 |
无 |
是 |
否 |
是 |
是 |
选择秘密攻击是不可区分的 | 是 | − | − | 是 | − | 是 |
抗内存泄漏的多秘密 | 否 | 否 | 否 | 否 | 是 | 是 |
下面我们将具体讨论本方案的一些重要性质.
(1) 抗泄露. 本方案是完全抗内存泄露的, 且在随机预言模型下, 方案对选择秘密攻击是不可区分的;
(2) 多用性. 因每个参与者计算伪份额
(3) 防欺诈. 由于秘密生成者
(4) 现有的大部分多秘密共享的存取结构是门限策略, 这种情况适用于参与者权力都相同的情况, 具有一定的局限性. 本方案突破了门限策略带来的约束, 实现了基于线性码上一般的存取结构.
另外, 在方案的计算复杂度方面, 我们将所提方案与文献[
一般存取结构上多秘密共享方案计算复杂度对比
性能 | 文献[ |
文献[ |
文献[ |
本文方案 |
初始化 | − | |||
分发阶段 | ( |
|||
实验阶段 | (2 |
− | ||
重构阶段 | | |
| |
| |
本文首次定义了抗内存泄漏的多级秘密共享的形式化的计算安全模型. 然后, 利用物理不可克隆函数以及模糊提取器联合产生密钥的原理, 构造了一个完全抗内存泄露的多级秘密共享方案. 该方案具有4个重要特性: (1) 方案是基于极小线性码的对偶码上多级秘密共享体系上建立的, 故其存取结构容易确定且较门限的方案更具一般性; (2) 最终的秘密是在参与者利用哈希函数生成的伪份额的帮助下重构的, 故其具有多用性; (3) 在秘密重构阶段, 能够验证参与者是否有欺诈行为; (4) 方案是计算可证明安全的. 因此, 本文的方案拓宽了多秘密共享的应用范围, 具有更好的应用前景.
Shamir A. How to share a secret. Communications of the ACM, 1979, 22: 612-613.
Blakley GR. Safeguarding cryptographic keys. Proc. of AFIPS NCC, 1979, 48: 313-317.
Zhang YS, Li WJ, Chen L, Bi W, Yang T. Verifiable special threshold secret sharing scheme based on eigenvalue. Journal on Communications, 2018, 39(8): 169-175 (in Chinese with English abstract).
张艳硕, 李文敬, 陈雷, 毕伟, 杨涛. 基于特征值的可验证特殊门限秘密共享方案. 通信学报, 2018, 39(8): 169-175. [doi: 10.11959/j.issn.1000-436x.2018143]
Tan ZH, Yang GM, Wang XW, Cheng W, Ning JY. Multidimensional spherical threshold secret sharing scheme for cloud storage. Ruan Jian Xue Bao/Journal of Software, 2016, 27(11): 2912-2928 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4943.htm[doi: 10.13328/j.cnki.jos.004943]
谭振华, 杨广明, 王兴伟, 程维, 宁婧宇. 面向云存储的多维球面门限秘密共享方案. 软件学报, 2016, 27(11): 2912-2928. http://www.jos.org.cn/1000-9825/4943.htm[doi: 10.13328/j.cnki.jos.004943]
Meng KJ, Miao FY, Huang WC,
Liu H, Li XH, Tian YL,
刘海, 李兴华, 田有亮, 雒彬, 马建峰, 彭长根. 理性公平的秘密共享方案. 计算机学报, 2020, 43(8): 1517-1533.
Ito M, Saito A, Nishizeki T. Secret sharing schemes realizing general access structures. In: Proc. of the IEEE Global Telecommunications Conf. 1987.99-102.
Massey JL. Some applications of coding theory in cryptography. In: Proc. of the Cryptography and Coding IV. Formara Ltd., 1995.33-47.
Stinson DR. An explication of secret sharing schemes. Designs Codes & Cryptography, 1992, 2(4): 357-390.
Brickell EF. Some ideal secret sharing schemes. Journal of Combinatorial Mathematics & Combinatorial Computing, 1989, 9(6): 105-113.
Lin C, Hu H, Chang CC,
Kabirirad S, Eslami Z. Improvement of (
Zhang BH, Tang YS. On the construction and analysis of verifiable multi-secret sharing based on non-homogeneous linear recursion. Journal of Information Science and Engineering, 2018, 34(3): 749-763.
Miao F, Wang L, Ji Y,
Dehkordi MH, Oraei H. How to construct a verifiable multi-secret sharing scheme based on graded encoding schemes. IET Information Security, 2019, 13(4): 343-351.
Li J, Wang X, Huang Z,
Mashhadi S, Dehkordi MH, Kiamari N. Provably secure verifiable multi-stage secret sharing scheme based on monotone span program. IET Information Security, 2017, 11(6): 326-331.
Song Y, Li ZH, Li YM,
Basit A, Chanakya P, Venkaiah VC,
Zhang J, Zhang F. Information-theoretical secure verifiable secret sharing with vector space access structures over bilinear groups and its applications. Future Generation Computer Systems, 2015, 52: 109-115.
Harn L. Unconditionally secure verifiable secret sharing scheme. Advances in Information Sciences & Service Sciences, 2012, 4(17): 514-518.
Krawczyk H. Secret sharing made short. In: Proc. of the Crypto'93. LNCS 773, Springer, 1993.136-146.
Hsu CF, Harn L, Cui G. An ideal multi-secret sharing scheme based on connectivity of graphs. Wireless Personal Communications, 2014, 77(1): 383-394.
Dehkordi MH, Mashhadi S, Oraei H. A proactive multi stage secret sharing scheme for any given access structure. Wireless Personal Communications, 2019, 104: 491-503.
Lin CL, Yan XF, Niu QW,
Zhang T, Ke X, Liu Y. (
Herranz J, Ruiz A, Saez G. Sharing many secrets with computational provable security. Information Processing Letters, 2013, 113(14-16): 572-579.
Herranz J, Ruiz A, Saez G. New results and applications for multi-secret sharing schemes. Designs, Codes and Cryptography, 2014, 73(3): 841-864.
Mashhadi S. A CSA-secure multi-secret sharing scheme in the standard model. Journal of Applied Security Research, 2020, 15(1): 84-95.
Dai SG, Wei JF, Zhang FG. Memory leakage-resilient secret sharing schemes. Science China (Information Sciences), 2015, 58(11): 1-9.
Ding C, Yuan J. Covering and secret sharing with linear codes. In: Proc. of the Discrete Mathematics and Theoretical Computer Science. LNCS 2731, Berlin: Springer, 2003.11-25.
Pappu R, Recht B, Taylor J,
Dodis Y, Ostrovsky R, Reuzin L,
Armknecht F, Maes R, Sadeghi AR,
Vega G, Wolfmann J. New classes of 2-weight cyclic codes. Designs Codes & Cryptography, 2007, 42(3): 327-334.
Lidl R, Niederreiter H. Finite Fields, Encyclopedia of Mathematics and Its Applications. Vol. 20.2nd ed., Cambridge University Press, 1997.