基于整数规划的一般访问结构秘密共享方案
|
摘要
在利用整数规划实现一般访问结构的秘密共享时,为简化访问结构、保证所有的整数规划都有解,提出一种将整数规划以直接构造的方式应用于一般访问结构秘密共享的方案。通过构建整数规划将秘密隐藏于目标函数的解中,并将约束条件作为秘密份额发送给参与者。参与者可通过共享秘密份额重构整数规划,并利用解方程组的方法找到目标函数的正确解,以恢复秘密。分析结果表明,与借助(t,n)门限的方案相比,该方案能实现所有的访问结构,无须采用传统方式求解整数规划和推导最大拒绝集,降低了计算复杂度。
In order to simplify the access structure and ensure that all integer programming have solutions,a scheme is proposed to apply integer programming directly to the secret sharing of general access structure.By constructing integer programming,the secret is hidden in the solution to the objective function,and the constraint condition is sent to the participants as the secret share.Participants can use their shares to reconstruct the integer programming problem,and get the correct solution to the objective function quickly by the method of solving equations,and then the secret is recovered.Analysis results show that,compared with the scheme using(t,n) threshold,this scheme can achieve all the access structures.It doesn't need to solve integer programming with the classical method or deduce the maximal unauthorized subsets,which reduce its computational complexity.
In order to simplify the access structure and ensure that all integer programming have solutions,a scheme is proposed to apply integer programming directly to the secret sharing of general access structure.By constructing integer programming,the secret is hidden in the solution to the objective function,and the constraint condition is sent to the participants as the secret share.Participants can use their shares to reconstruct the integer programming problem,and get the correct solution to the objective function quickly by the method of solving equations,and then the secret is recovered.Analysis results show that,compared with the scheme using(t,n) threshold,this scheme can achieve all the access structures.It doesn't need to solve integer programming with the classical method or deduce the maximal unauthorized subsets,which reduce its computational complexity.
引文
[1] SHAMIR A.How to share a secret[J].Communications of the ACM,1979,22(11):612-613.
[2] BLAKLEY G R.Safeguarding cryptographic keys[C]//Proceedings of AFIPS’79.New York,USA:AFIPS Press,1979:313-317.
[3] PEDERSEN T P.A threshold cryptosystem without a trusted party[C]//Proceedings of International Conference on Theory and Application of Cryptographic Techniques.New York,USA:ACM Press,1991:522-526.
[4] NAOR M.Visual cryptography[C]//Proceedings of Workshop on the Theory and Application of Cryptographic Techniques.Berlin,Germany:Springer,1994:1-12.
[5] 苗得雨.基于一般访问结构的用户友好的可视秘密共享方案[D].西安:西安电子科技大学,2015.
[6] DING Fan,LONG Yihong,WU Peili.Study on secret sharing for sm2 digital signature and its application[C]//Pro-ceedings of the 14th International Conference on Com-putational Intelligence and Security.Washington D.C.,USA:IEEE Computer Society,2018:205-209.
[7] 何晓婷,苗付友,方亮.基于秘密共享的(t,m,n)-AS组认证方案[J].计算机工程,2018,44(1):154-159.
[8] SCHOENMAKERS B.A simple publicly verifiable secret sharing scheme and its application to electronic voting[C]//Proceedings of International Cryptology Conference on Advances in Cryptology.Berlin,Germany:Springer,1999:148-164.
[9] GENNARO R,RABIN M O,RABIN T.Simplified VSS and fast-track multiparty computations with applications to threshold cryptography[C]//Proceedings of the 17th ACM Symposium on Principles of Distributed Computing.New York,USA:ACM Press,1998:101-111.
[10] ITO M,SAITO A,NISHIZEKI T.Secret sharing scheme realizing general access structure[J].Electronics and Communications in Japan,1989,72(9):56-64.
[11] IWAMOTO M,YAMAMOTO H,OGAWA H.Optimal multiple assignments based on integer programming in secret sharing schemes[C]//Proceedings of International Symposium on Information Theory.Washington D.C.,USA:IEEE Press,2004:16.
[12] LI Qiang,LI Xiangxue,LAI Xuejia,et al.Optimal assignment schemes for general access structures based on linear programming[J].Designs,Codes and Cryptography,2015,74(3):1-22.
[13] HARN L,HSU C,ZHANG Mingwu,et al.Realizing secret sharing with general access structure[J].Information Sciences,2016(367/368):209-220.
[14] 彭凤.整数规划算法效率的研究[D].长沙:中南大学,2010.
[15] 于春田,李法朝,惠红旗.运筹学[M].2版.北京:科学出版社,2011.
[16] 申卯兴,许进.求解线性规划的单纯形法的直接方法[J].计算机工程与应用,2007,43(30):94-96.
[2] BLAKLEY G R.Safeguarding cryptographic keys[C]//Proceedings of AFIPS’79.New York,USA:AFIPS Press,1979:313-317.
[3] PEDERSEN T P.A threshold cryptosystem without a trusted party[C]//Proceedings of International Conference on Theory and Application of Cryptographic Techniques.New York,USA:ACM Press,1991:522-526.
[4] NAOR M.Visual cryptography[C]//Proceedings of Workshop on the Theory and Application of Cryptographic Techniques.Berlin,Germany:Springer,1994:1-12.
[5] 苗得雨.基于一般访问结构的用户友好的可视秘密共享方案[D].西安:西安电子科技大学,2015.
[6] DING Fan,LONG Yihong,WU Peili.Study on secret sharing for sm2 digital signature and its application[C]//Pro-ceedings of the 14th International Conference on Com-putational Intelligence and Security.Washington D.C.,USA:IEEE Computer Society,2018:205-209.
[7] 何晓婷,苗付友,方亮.基于秘密共享的(t,m,n)-AS组认证方案[J].计算机工程,2018,44(1):154-159.
[8] SCHOENMAKERS B.A simple publicly verifiable secret sharing scheme and its application to electronic voting[C]//Proceedings of International Cryptology Conference on Advances in Cryptology.Berlin,Germany:Springer,1999:148-164.
[9] GENNARO R,RABIN M O,RABIN T.Simplified VSS and fast-track multiparty computations with applications to threshold cryptography[C]//Proceedings of the 17th ACM Symposium on Principles of Distributed Computing.New York,USA:ACM Press,1998:101-111.
[10] ITO M,SAITO A,NISHIZEKI T.Secret sharing scheme realizing general access structure[J].Electronics and Communications in Japan,1989,72(9):56-64.
[11] IWAMOTO M,YAMAMOTO H,OGAWA H.Optimal multiple assignments based on integer programming in secret sharing schemes[C]//Proceedings of International Symposium on Information Theory.Washington D.C.,USA:IEEE Press,2004:16.
[12] LI Qiang,LI Xiangxue,LAI Xuejia,et al.Optimal assignment schemes for general access structures based on linear programming[J].Designs,Codes and Cryptography,2015,74(3):1-22.
[13] HARN L,HSU C,ZHANG Mingwu,et al.Realizing secret sharing with general access structure[J].Information Sciences,2016(367/368):209-220.
[14] 彭凤.整数规划算法效率的研究[D].长沙:中南大学,2010.
[15] 于春田,李法朝,惠红旗.运筹学[M].2版.北京:科学出版社,2011.
[16] 申卯兴,许进.求解线性规划的单纯形法的直接方法[J].计算机工程与应用,2007,43(30):94-96.