若干关于矩阵的密码协议的设计与分析
|
摘要
矩阵理论作为一种基本的数学工具,在数学、物理学和其它科学技术领域(如统计分析、数值计算、优化理论、微分方程、概率统计、系统工程等)都有广泛应用.计算机及网络通信技术的发展也为矩阵理论的应用开辟了更广阔的前景.近年来,矩阵理论和密码学的交叉应用备受国内外学者的关注,获得了大量的研究成果.一方面,以矩阵理论为基础构造安全高效的密码体制解决信息安全问题.另一方面,利用各种密码技术设计安全高效的计算协议解决矩阵理论的多方共享问题.本文研究了矩阵理论在多方安全计算、秘密分享、基于身份签密这三个热点领域内的应用,得到了许多新的有意义的结果,这些结果进一步丰富了矩阵理论与信息安全领域的交叉应用.全文主要包括以下四个方面：
1.一般线性方程组安全两方计算协议的设计与分析.广义逆矩阵是研究线性方程组解的一个不可或缺的重要工具,因此,本文在不经意传输的意义下,利用有限域上计算广义逆的概率算法,设计新的安全协议,解决了保护私有信息的一般线性方程组在有限域上的安全两方计算问题,丰富了隐私保护的线性方程组求解的研究内容.
2.一般矩阵和安全多方计算协议的设计与分析.矩阵加法是矩阵最基本的运算,因此,矩阵应用的基础性和广泛性决定了矩阵和的安全多方计算是设计众多应用协议的基础协议,是解决科学计算、统计分析等实际问题重要的底层工具.本文基于递归思想,在不经意传输的意义下,设计了一般矩阵和的安全多方计算协议,并通过模拟器的构造证明了安全性.新的基础协议将服务于更多应用问题的有效解决.
3.基于正交投影矩阵的秘密分享方案的密码攻击.正交投影矩阵的恒等不变性为门限秘密分享体制的设计提供了一种新的思路,本文对这种基于投影矩阵技术的秘密分享方案进行了密码分析,通过举例明确指出该方案不能抵抗欺诈攻击,无法阻止不诚实成员提供假份额参与秘密恢复,同时也无法识别恢复出秘密的真伪.更重要的是,本文利用投影矩阵理论和有限域上的矩阵理论严格证明了成员提供伪份额而不被发现的欺骗行为能以不可忽略的概率存在,并求出了该欺骗行为获得成功的概率.
4.格上基于身份签密方案的设计与分析.格是一种重要的代数结构,以矩阵为基本工具.基于格问题构造的密码方案除了能抵抗量子攻击外,使得具有平均情况下安全性的公钥密码体制设计成为了可能,是后量子时代公钥密码的首选.本文基于q模格上的LWE困难问题和SIS困难问题,构造了一个基于身份的签密方案,并在随机预言模型下证明了方案的IND-CCA2和EUF-CMA安全性.另外,格上运算的线性性降低了方案的计算代价,提高了效率.
As a fundamental tool, matrix theory has found many applications in math-ematical and physical science, as well as fertile felds for research including statis-tical analysis, numerical calculation, optimization theory, diferential equations,probability and statistics, and system engineering. The rapid development ofcomputer network and information technology also ofers new opportunities forits further application. Among them, studies on the application of matrix the-ory in cryptography have been extensively carried out by scholars both at homeand abroad. For instance, secure and efcient cryptographic systems based onmatrix theory have been designed to solve the problems of information security.On the other hand, secure and efcient computing protocols utilizing diferentcryptographic techniques provide alternative access to multi-party sharing prob-lems in matrix theory. In this thesis, we focused our attention on solving severalopen questions in the feld of secure multi-party computation, secret sharing andidentity-based signcryption, thus providing many meaningful new results over theknown ones. These results further facilitate the developments on matrix theoryand information security to some extent. Accordingly, the main contributions ofthis dissertation are as follows,
1.Researches on the design and analysis of a secure two-party protocol forsolving systems Ax=b of m linear equations in n variables over a fnite feld.Generalized inverses play an important role in the solution of such linear sys-tems of equations. Given an implementation of oblivious transfer, we can solveprivacy-preserving cooperative linear system of equations of the form Ax=bby computing the generalized inverse. Based on this probabilistic algorithm, wepresent a secure two-party protocol to enrich the research contents on securelysolving linear system of equations.
2.Researches on the design and analysis of a secure multi-party protocol of matrix addition. Matrix addition represents a basic operation in matrix theory,hence we propose a privacy-preserving cooperative matrix addition protocol inthe k-party model via oblivious transfer protocol and recursive method. In suchcase, the security is proven through constructing simulator. This basic protocolcan serve as a new tool to protect privacy in practical applications.
3.Researches on the attack analysis of a secret sharing scheme using matrixprojection. Matrix projection and its invariance property provide a novel ideafor constructing threshold secret sharing system. In this thesis, the securitydefciency against cheating, which lies in a threshold secret sharing scheme usingprojection matrix, is presented. We exemplify that there exists only single cheaterpassing the check that makes other participants reconstruct an invalid secretwithout being detected. Most importantly, we also give a strict proof according tomatrix projection and matrix theory over fnite feld, which show that the cheaterhas non-negligible advantage in above deception. Moreover, the probability ofsuccessfully cheating is given.
4.Researches on the design and analysis of ID-based signcryption from lattice.Lattice is an important algebraic structure with matrix as its basic tool. Owing toits strong resistance against quantum attack and security proofs based on average-case hardness, lattice-based cryptographic constructions hold a great promisefor post-quantum cryptography. In view of the average-case hard problems inq modular lattice such as LWE and SIS, we propose an ID-based signcryptionscheme, which security can be proved in the random oracle model of IND-CCA2and EUF-CMA security formally. Since linear operations in lattice reduce thecomputational cost, the presented scheme becomes more efcient.
1.一般线性方程组安全两方计算协议的设计与分析.广义逆矩阵是研究线性方程组解的一个不可或缺的重要工具,因此,本文在不经意传输的意义下,利用有限域上计算广义逆的概率算法,设计新的安全协议,解决了保护私有信息的一般线性方程组在有限域上的安全两方计算问题,丰富了隐私保护的线性方程组求解的研究内容.
2.一般矩阵和安全多方计算协议的设计与分析.矩阵加法是矩阵最基本的运算,因此,矩阵应用的基础性和广泛性决定了矩阵和的安全多方计算是设计众多应用协议的基础协议,是解决科学计算、统计分析等实际问题重要的底层工具.本文基于递归思想,在不经意传输的意义下,设计了一般矩阵和的安全多方计算协议,并通过模拟器的构造证明了安全性.新的基础协议将服务于更多应用问题的有效解决.
3.基于正交投影矩阵的秘密分享方案的密码攻击.正交投影矩阵的恒等不变性为门限秘密分享体制的设计提供了一种新的思路,本文对这种基于投影矩阵技术的秘密分享方案进行了密码分析,通过举例明确指出该方案不能抵抗欺诈攻击,无法阻止不诚实成员提供假份额参与秘密恢复,同时也无法识别恢复出秘密的真伪.更重要的是,本文利用投影矩阵理论和有限域上的矩阵理论严格证明了成员提供伪份额而不被发现的欺骗行为能以不可忽略的概率存在,并求出了该欺骗行为获得成功的概率.
4.格上基于身份签密方案的设计与分析.格是一种重要的代数结构,以矩阵为基本工具.基于格问题构造的密码方案除了能抵抗量子攻击外,使得具有平均情况下安全性的公钥密码体制设计成为了可能,是后量子时代公钥密码的首选.本文基于q模格上的LWE困难问题和SIS困难问题,构造了一个基于身份的签密方案,并在随机预言模型下证明了方案的IND-CCA2和EUF-CMA安全性.另外,格上运算的线性性降低了方案的计算代价,提高了效率.
As a fundamental tool, matrix theory has found many applications in math-ematical and physical science, as well as fertile felds for research including statis-tical analysis, numerical calculation, optimization theory, diferential equations,probability and statistics, and system engineering. The rapid development ofcomputer network and information technology also ofers new opportunities forits further application. Among them, studies on the application of matrix the-ory in cryptography have been extensively carried out by scholars both at homeand abroad. For instance, secure and efcient cryptographic systems based onmatrix theory have been designed to solve the problems of information security.On the other hand, secure and efcient computing protocols utilizing diferentcryptographic techniques provide alternative access to multi-party sharing prob-lems in matrix theory. In this thesis, we focused our attention on solving severalopen questions in the feld of secure multi-party computation, secret sharing andidentity-based signcryption, thus providing many meaningful new results over theknown ones. These results further facilitate the developments on matrix theoryand information security to some extent. Accordingly, the main contributions ofthis dissertation are as follows,
1.Researches on the design and analysis of a secure two-party protocol forsolving systems Ax=b of m linear equations in n variables over a fnite feld.Generalized inverses play an important role in the solution of such linear sys-tems of equations. Given an implementation of oblivious transfer, we can solveprivacy-preserving cooperative linear system of equations of the form Ax=bby computing the generalized inverse. Based on this probabilistic algorithm, wepresent a secure two-party protocol to enrich the research contents on securelysolving linear system of equations.
2.Researches on the design and analysis of a secure multi-party protocol of matrix addition. Matrix addition represents a basic operation in matrix theory,hence we propose a privacy-preserving cooperative matrix addition protocol inthe k-party model via oblivious transfer protocol and recursive method. In suchcase, the security is proven through constructing simulator. This basic protocolcan serve as a new tool to protect privacy in practical applications.
3.Researches on the attack analysis of a secret sharing scheme using matrixprojection. Matrix projection and its invariance property provide a novel ideafor constructing threshold secret sharing system. In this thesis, the securitydefciency against cheating, which lies in a threshold secret sharing scheme usingprojection matrix, is presented. We exemplify that there exists only single cheaterpassing the check that makes other participants reconstruct an invalid secretwithout being detected. Most importantly, we also give a strict proof according tomatrix projection and matrix theory over fnite feld, which show that the cheaterhas non-negligible advantage in above deception. Moreover, the probability ofsuccessfully cheating is given.
4.Researches on the design and analysis of ID-based signcryption from lattice.Lattice is an important algebraic structure with matrix as its basic tool. Owing toits strong resistance against quantum attack and security proofs based on average-case hardness, lattice-based cryptographic constructions hold a great promisefor post-quantum cryptography. In view of the average-case hard problems inq modular lattice such as LWE and SIS, we propose an ID-based signcryptionscheme, which security can be proved in the random oracle model of IND-CCA2and EUF-CMA security formally. Since linear operations in lattice reduce thecomputational cost, the presented scheme becomes more efcient.
引文
[1] C. Asmuth, J. Bloom, A Modular Approach to Key Safeguarding, IEEE Trans onInformation Throry,29(2)(1983)208-210.
[2] S. Agrawal, X. Boyen, Identity-based encryption from lattices in the standardmodel [EB/OL]. http://www.cs.standford.edu/xb/ab09/.
[3] S. Agrawal, D. Boneh, X. Boyen, Efcient lattice (H)IBE in the standard model,Advances in Cryptology-Eurocrypt2010:29th Annual International Conferenceon the Theory and Applications of Cryptographic Techniques, Berlin: Springer-Verlag,(2010)553-572.
[4] M. Ajtai, Generating hard instances of lattice problems (extended abstract), InSTOC, ACM,(1996).
[5] M. Ajtai, Generating hard instances of the short basis problem, In ICALP,(1999)1-9.
[6] M. Ajitai, R. Kumar, D. Sivakumar, A sieve algorithm for the shortest latticevector problem, STOC, ACM,(2001)601-610.
[7] L. Bai, A strong ramp secret sharing scheme using matrix projection, Proc. In-ternational Symposium on a World of Wireless, Mobile and Multimedia Network,(2006)652-656.
[8] G. Brassard, C. Crepeau, J.M. Robert, Information theoretic reduction amongdisclosure problems, In Proceedings of the27th FOCS,(1986)168-173.
[9] G. Brassard, C. Crepeau, J.M. Robert, All-or-nothing disclosure of secrets, In:CRYPTO’86, LNCS, Springer-Verlag,263(1987)234-238.
[10] D. Boneh, M. Franklin, Identity-based encryption from the Weiling pairing, InProc. of CRYPTO’01, LNCS,2139(2001)213-229.
[11] I.F. Blake, V. Kolesnikov, One-round secure comparison of integers, J. Math.Crypt.3(2009)37-68.
[12] M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for noncryp-tographic fault-tolerant distributed computations, In20th STOC, ACM,(1988)1-10.
[13] G.R. Blakley, Safeguarding cryptographic keys, Proc. AFIPS1979, National Com-puter Conference,48(1979)313-137.
[14] P.S.L.M. Barreto, B. Libert, N. McCullagh, J.J. Quisquater, Efcient andprovably-secure identity-based signatures and signcryption from bilinear maps,Advances in Cryptology-ASIACRYPT2005, LNCS, Berlin: Springer-Verlag,3788(2005)515-532.
[15] X. Boyen, Multipurpose identity-based signcryption:a swiss army knife foridentity-based cryptography, Advances in Cryptology-CRYPTO2003, LNCS,Berlin: Springer-Verlag,2729(2003)383-399.
[16] M. Bellare, P. Rogaway, Random oracles are practical: A paradigm for design-ing efcient protocols, In Proceedings of the ACM Conference on Computer andCommunications Security,(1993)62-73.
[17] E.F. Brickell, D.R. Stinson, The detection of cheaters in threshold schemes, Ad-vances in Cryptology-CRYPTO’88, LNCS, Springer Verlag,403(1990)564-577.
[18] L. Bai, X. Zou, A proactive secret sharing scheme in matrix projection method,Int. J. Security and Networks,4(4)(2009)201-209.
[19] J. Cha, J. Cheon, An identity-based signature from Gap Dife-Hellman group, InPKC2003,(2003)18-30.
[20] R. Cramer, I. Damgard, Secure distributed linear algebra in a constant number ofrounds, CRYPTO01, LNCS, Berlin: Springer,2139(2001)119-136.
[21] D. Chaum, C. Crepeau, I. Damgard, Multiparty unconditionally secure protocols.In20th STOC, ACM,(1988)11-19.
[22] R. Cramer, I. Damgard, U. Maurer, General secure multi-party computation fromany linear secret-sharing scheme, Proc. EUROCRYPT2000, LNCS, Springer-Ver-lag,1807(2000)316-334.
[23] M. Carpentieri, A.D. Santis, U. Vaccaro, Size of shares and probability of cheatingin threshold schemes, Proc. Eurocrypt’93, LNCS, Springer-Verlag,765(1993)118-125.
[24] R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology revisited(Preliminary Version), STOC,(1998)209-218.
[25] B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, Verifable Secret Sharing andAchieving Simultaneity in the Presence of Faults(Extended Abstract), FOCS,(1985)383-395.
[26] D. Cash, D. Hofheinz, E. Kiltz. How to delegate a lattice basis. Cryptology ePrintArchive, Report2009/351,(2009), http://eprint.iacr.org/.
[27] D. Cash, D. Hofheinz, E. Kiltz, C. Peikert, Bonsai Trees, or How to Delegate aLattice Basis, In Advances in cryptology-EUROCRYPT2010,(2010)523-552.
[28] R. Cramer, E. Kiltz, C. Padro, A note on secure computation of the Moore-PenrosePseudoinverse and its application to secure linear algebra, CRYPTO07, LNCS,Berlin: Springer,4622(2007)613-630.
[29] L. Chen, J. Malone-Lee, Improved identity-based signcryption.Public KeyCryptography-PKC2005, LNCS,Berlin: Springer-Verlag,3386(2005)362-379.
C. Crepeau, Equivalence between two flavors of oblivious transfer, In: CRYPTO'87, LNCS, Springer-Verlag,293(1987)350-354.
[31]R. Cramer, V. Shoup, A practical public key cryptosystem provable secure against adaptive chosen ciphertext attack, In Advances in Cryptology-Crypto1998, LNCS, Berlin:Springer-Verlag, Germany,1462(1998)13-25.
[32]陈鲁生,沈世镒,现代密码学,北京：科学出版社,(2002).
[33]S.S.M. Chow, S.M. Yiu, L.C.K. Hui, K.P. Chow, Efficient forward and provably secure ID-based signcryption scheme with public verifiability and public cipher-text authenticity, Information Security and Cryptology-ICISC2003, LNCS, Berlin: Springer-Verlag,2971(2004)352-369.
[34]Z. Chen, H. Zhu, Quantum m-out-of-n oblivious transfer, Technical report, arXiv:cs.CR/0311039,(2003).
[35]W.L. Du, M.J. Atallah, Secure multi-party computation problems and their ap-plications:A review and open problems. In Proc. of New Security Paradigms Workshop, Cloudcroft, New Mexico, USA.(2001)11-20.
[36]W.L. Du, M.J. Atallah, Privacy-preserving cooperative scientific computations, In Proc. of the14th IEEE Computer Security Foundations Workshop, Nova Scotia, Canada.(2001)273-282.
[37]W.L. Du, M.J. Atallah, Privacy-preserving cooperative statistical analysis, In:17th Annual Computer Security Applications Conference, New Orleans, Louisiana, USA,(2001)102-110.
[38]Y. Dodis, S. Micali, Lower bounds for oblivious transfer reductions, In:EURO-CRYPT'99, LNCS, Springer-Verlag,1592(1999)42-55.
[39]W.L. Du, A study of several specific secure two-party computation prob-lems[Ph.D.dissertation], Purdue University, USA,(2000).
[40] D. Dolev, A.C. Yao, On the security of public key protocols, IEEE Transactionson Information Theory,29(2)(1983)198-208.
[41] S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts,Communications of the ACM,28(6)(1985)637-647.
[42] P. Feldman, A practical scheme for non-interactive verifable secret sharing, InProceedings of the28th IEEE Annual Symposium on Foundations of ComputerScience,(1987)427-437.
[43] M. Fischlin, A cost-efective pay-per-multiplication comparison method for mil-lionaires, In Proceedings of the2001Conference on Topics in Cryptology: TheCryptographer’s Track at RSA, LNCS, Springer-Verlag,2020(2001)457-472.
[44] A. Fiat, A. Shamir, How to prove yourself: Practical solutions to identifcationand signature problems, In Advances in Cryptology-Crypto’86, LNCS, Berlin:Springer-Verlag,263(1986)186-194.
[45] S. Goldwasser, S. Micali, Probabilistic encryption, Journal of Computer and Sys-tem Sciences,28(2)(1984)270-299.
[46] O. Goldreich, S. Micali, A. Wigderson, How to play ANY mental game, The19thAnnual ACM Conference on Theory of Computing, New York,(1987)218-229.
[47] O. Goldreich, Foundations of Cryptography: Basic Applications, London: Cam-bridge University Press,(2004)599-729.
[48] S. Goldwasser, Multi-party computations: past and present, Proceedings ofthe sixteenth annual ACM symposium on Principles of distributed computings,NewYork: ACM Press,(1997)21-24.
[49] O. Goldreich, Secure multi-party computation (working draft). Available fromhttp://www.wisdom.weizmann.ac.il/home/oded/public html/foc.html,(1998).
C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, In Proc. of STOC'08,(2008)197-206.
[51]O. Goldreich, R. Vainish, How to solve any protocol problem-an efficiency im-provement. In:CRYPTO'87, LNCS, Springer-Verlag,293(1988)73-86.
[52]I. Ioannidis, A. Grama, An Efficient Protocol for Yao's Millionaires' Problem, In Proceedings of the36th Hawaii Internatinal Conference on System Sciences2003,(2003).
[53]荆巍巍,安全多方计算中若干基础协议及应用的研究,中国科学技术大学博士论文,(2008).
[54]E.E. Karnin, J.W. Greene, M.E. Hellman, On secret sharing systems, IEEE trans-actions on information theory,29(1983)35-41.
[55]J.S. Kang, D. Hong, A Practical Privacy-Preserving Cooperative Computation Protocol without Oblivious Transfer for Linear Systems of Equations. Interna-tional Journal of Information Processing Systems,3(1)(2007)21-25.
[56]J. Kilian, Founding cryptography on oblivious transfer, Proc of20th Annual Sym-posium on the Theory of Computation(STOC), ACM,(1988)20-31.
[57]N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation,48(1987)203+209.
[58]A. Lenstra, H. Lenstra, L.Lovasz, Factoring polynomials with rational coefficients, Mathematische Annalen,261(4)(1982)515-534.
[59]W. J. Luo, X. Li, The secure multi-party protocol of matrix product and its appli-cation, Chinese Journal of Computers,28(7)(2005)1230-1235.
[60]G. Leurent,P.Q. Nguyen, How risky is the random-oracle model, CRYPTO'09,(2009)445-464.
[61]B. Libert, J.J. Quisquater, New identity based signcryption schemes from pairings.2003IEEE Information Theory Workshop, Paris, France,(2003)155-158.
[62]刘木兰,张志芳,密钥共享体制和安全多方计算,北京：电子工业出版社,(2008).
[63]J. Malone-Lee, Identity based signcryption.Cryptology ePrint Archive,Report2002/098,(2002). Available from:http://eprint.iacr.org/2002/098.
[64]V. Miller, Use of elliptic curves in cryptography, CRYPTO'85,(1985).
[65]T. Migler, K.E. Morrison, M. Ogle, How much does a matrix of rank k weight, Mathematics Magazine,79(4)(2006)262-271.
[66]D. Micciancio, O.Regev, Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput.,37(1)(2007)267-302.
[67]R.J. McEliece, D.V. Sarwate, On sharing secrets and reed-solomon codes, Com-munications of the ACM,24(1981)583-584.
[68]Y. Mu, J. Zhang, V. Varadharajan, M out of n oblivious transfer, In Proceedings of the7th Australasian Conference on Information Security and Privacy (ACISP'02), LNCS, Springer-Verlag,2384(2002)395-405.
[69]M. Naor, B. Pinkas, Oblivious Transfer and Polynomial Evaluation, In Proceedings of the31th Annual ACM Symposium on the Theory of Computing (STOC'99), ACM,(1999)245-254.
[70]M. Naor, B. Pinkas, Oblivious transfer with adaptive queries, In Proceedings of Advances in Cryptology-CRYPTO'99, LNCS, Springer-Verlag,1666(1999)573-590.
[71]K. Nissim, E. Weinreb, Communication efficient secure linear algebra, TCC2006, LNCS, Berlin:Springer,3876(2006)522-541.
[72] S. Obana, T. Araki, Almost optimum secret sharing scheme secure against cheatingfor arbitrary secret distribution, Advances in Asiacrypt’2006, LNCS, SpringerVerlag,4284(2006)364-379.
[73] T. Okamoto, Efcient Blind and Partially Blind Signatures Without Random Or-acles, In: S.Halevi and T.Rabin(Eds.): TCC2006, LNCS, Berlin: Springer-Verlag,3876(2006)80-99.
[74] W. Ogata, K. Kurosawa, D. R. Stinson, Optimum Secret Sharing Scheme Secureagainst Cheating, SIAM Journal on Discrete Mathematics,20(1)(2006)79-95.
[75] K.G. Paterson, ID-based signature from pairings on Elliptic Curves, IEE Electron-ics Letters,38(18)(2002)1025-1026.
[76] T.P. Pedersen, A threshold cryptosystem without a trusted party, In Advances inCryptology-EUROCRYPT’91, LNCS, Springer-Verlag,547(1991)522-526.
[77] C. Peikert, Bonsai trees (or, arboriculture in lattice-based cryptography). Cryp-tology ePrint Archive, Report2009/359,(2009), http://eprint.iacr.org/.
[78] K.G. Paterson, J.C.N. Schuldt, Efcient identity-based signatures secure in thestandard model, In: Proceedings of the11th Australasian Conference on Informa-tion Security and Privacy, LNCS, Springer,4058(2006)207-222.
[79] M. Rabin, How to exchange secrets by oblivious transfer. Technical Report TR-81,Aiken Computation Laboratory, Harvard University,(1981).
[80] O. Regev, On lattices, learning with errors, random linear codes, and cryptogra-phy, In STOC,(2005)84-93.
[81] C.P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms,Theor. Comput. Sci.,53(1987)201-224.
[82] A. Shamir, How to share a secret, Communications of the ACM,22(11)(1979)612-613.
[83] A. Shamir, Identity-based cryptosystems and signature schemes, In Proc. ofCRYPTO’84,(1985)47-53.
[84] P.W. Shor, Polynomial-time algorithms for prime factorization and discrete loga-rithms on a quantum computer, SIAM J. Comput.,26(5)(1997)1484-1509.
[85] H.M. Sun, S.P. Shieh, Constructions of dynamic threshold schemes.Electronicsletters,30(24)(1994)2023-2025.
[86] R. Steinfeld, H. X. Wang, J. Pieprzyk, Lattice-based threshold-changeabilityfor standard shamir secret-sharing schemes, Advances in Asiacrypt’2004, LNCS,Springer Verlag,3329(2004)170-186.
[87] J.R. Troncoso-Pastoriza, P. Comesan a, F. P e′rez Gonz′alez, Secure Direct andIterative Protocols for Solving Systems of Linear Equations, In SPEED Workshop,Lausanne, Switzerland,(2009)122-141.
[88] M. Tompa, H. Woll, How to Share a Secret with Cheaters, Journal of Cryptology,1(3)(1989)133-138.
[89] W. Tzeng, Efcient1-out-of-n oblivious transfer schemes with universally usableparameters, IEEE TRANSACTIONS ON COMPUTERS,53(2)(2004)232-240.
[90] N.N. Wu, J. Zhang, N. Li, Privacy-preserving discovery of multivariate linearrelationship, Journal of Systemics, Cybernetics and Informatics,4(5)(2006)67-72.
[91] K. Wang, X. Zou, Y. Sui, A multiple secret sharing scheme base on matrix projec-tion, Proc. COMPSAC’09,33rd Annual IEEE International Computer Softwareand Applications Conference,1(2009)400-405.
[92]F. Xia, B. Yang, W. Sun, S. Ma, An efficient identity-based signature from lattice in the random oracle model, Journal of Computational Information Systems,7(11)(2011)3963-3971.
[93]A.C. Yao, Protocols for secure computations, The23rd IEEE Symposium on Foun-dations of Computer Science, Piscataway, USA, IEEE,(1982)160-164.
[94]姚亦飞,保护私有信息的统计计算问题研究,中国科学技术大学博士论文,(2008).
[95]H. Yanai, K. Takeuchi, Y. Takane, Projecion matrices, generalized inverse matri-ces, and singular value decomposition, New York, NY Springer Science+Business Media, LCC,(2011)25-32.
[96]X. Yang, Z. Yu, B. Kang, Privacy-Preserving Cooperative Linear System of Equa-tions Protocol and its Application, The4th International Conference on Wireless Communications, Networking and Mobile Computing. Dalian.(2008).
[97]Y. Yu, B. Yang, Y. Sun et al, Identity based signcryption scheme without random oracle, Computer Standards/Interfaces,3(1)(2009)56-62.
[98]Y. Zheng, Digital signcryption or how to achieve cost (signature/encryption) cost (signature)+cost(encryption), Advances in Cryptology-CRYPTO'97, LNCS, Berlin:Springer-Verlag,1294(1997)165-179.
[2] S. Agrawal, X. Boyen, Identity-based encryption from lattices in the standardmodel [EB/OL]. http://www.cs.standford.edu/xb/ab09/.
[3] S. Agrawal, D. Boneh, X. Boyen, Efcient lattice (H)IBE in the standard model,Advances in Cryptology-Eurocrypt2010:29th Annual International Conferenceon the Theory and Applications of Cryptographic Techniques, Berlin: Springer-Verlag,(2010)553-572.
[4] M. Ajtai, Generating hard instances of lattice problems (extended abstract), InSTOC, ACM,(1996).
[5] M. Ajtai, Generating hard instances of the short basis problem, In ICALP,(1999)1-9.
[6] M. Ajitai, R. Kumar, D. Sivakumar, A sieve algorithm for the shortest latticevector problem, STOC, ACM,(2001)601-610.
[7] L. Bai, A strong ramp secret sharing scheme using matrix projection, Proc. In-ternational Symposium on a World of Wireless, Mobile and Multimedia Network,(2006)652-656.
[8] G. Brassard, C. Crepeau, J.M. Robert, Information theoretic reduction amongdisclosure problems, In Proceedings of the27th FOCS,(1986)168-173.
[9] G. Brassard, C. Crepeau, J.M. Robert, All-or-nothing disclosure of secrets, In:CRYPTO’86, LNCS, Springer-Verlag,263(1987)234-238.
[10] D. Boneh, M. Franklin, Identity-based encryption from the Weiling pairing, InProc. of CRYPTO’01, LNCS,2139(2001)213-229.
[11] I.F. Blake, V. Kolesnikov, One-round secure comparison of integers, J. Math.Crypt.3(2009)37-68.
[12] M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for noncryp-tographic fault-tolerant distributed computations, In20th STOC, ACM,(1988)1-10.
[13] G.R. Blakley, Safeguarding cryptographic keys, Proc. AFIPS1979, National Com-puter Conference,48(1979)313-137.
[14] P.S.L.M. Barreto, B. Libert, N. McCullagh, J.J. Quisquater, Efcient andprovably-secure identity-based signatures and signcryption from bilinear maps,Advances in Cryptology-ASIACRYPT2005, LNCS, Berlin: Springer-Verlag,3788(2005)515-532.
[15] X. Boyen, Multipurpose identity-based signcryption:a swiss army knife foridentity-based cryptography, Advances in Cryptology-CRYPTO2003, LNCS,Berlin: Springer-Verlag,2729(2003)383-399.
[16] M. Bellare, P. Rogaway, Random oracles are practical: A paradigm for design-ing efcient protocols, In Proceedings of the ACM Conference on Computer andCommunications Security,(1993)62-73.
[17] E.F. Brickell, D.R. Stinson, The detection of cheaters in threshold schemes, Ad-vances in Cryptology-CRYPTO’88, LNCS, Springer Verlag,403(1990)564-577.
[18] L. Bai, X. Zou, A proactive secret sharing scheme in matrix projection method,Int. J. Security and Networks,4(4)(2009)201-209.
[19] J. Cha, J. Cheon, An identity-based signature from Gap Dife-Hellman group, InPKC2003,(2003)18-30.
[20] R. Cramer, I. Damgard, Secure distributed linear algebra in a constant number ofrounds, CRYPTO01, LNCS, Berlin: Springer,2139(2001)119-136.
[21] D. Chaum, C. Crepeau, I. Damgard, Multiparty unconditionally secure protocols.In20th STOC, ACM,(1988)11-19.
[22] R. Cramer, I. Damgard, U. Maurer, General secure multi-party computation fromany linear secret-sharing scheme, Proc. EUROCRYPT2000, LNCS, Springer-Ver-lag,1807(2000)316-334.
[23] M. Carpentieri, A.D. Santis, U. Vaccaro, Size of shares and probability of cheatingin threshold schemes, Proc. Eurocrypt’93, LNCS, Springer-Verlag,765(1993)118-125.
[24] R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology revisited(Preliminary Version), STOC,(1998)209-218.
[25] B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, Verifable Secret Sharing andAchieving Simultaneity in the Presence of Faults(Extended Abstract), FOCS,(1985)383-395.
[26] D. Cash, D. Hofheinz, E. Kiltz. How to delegate a lattice basis. Cryptology ePrintArchive, Report2009/351,(2009), http://eprint.iacr.org/.
[27] D. Cash, D. Hofheinz, E. Kiltz, C. Peikert, Bonsai Trees, or How to Delegate aLattice Basis, In Advances in cryptology-EUROCRYPT2010,(2010)523-552.
[28] R. Cramer, E. Kiltz, C. Padro, A note on secure computation of the Moore-PenrosePseudoinverse and its application to secure linear algebra, CRYPTO07, LNCS,Berlin: Springer,4622(2007)613-630.
[29] L. Chen, J. Malone-Lee, Improved identity-based signcryption.Public KeyCryptography-PKC2005, LNCS,Berlin: Springer-Verlag,3386(2005)362-379.
C. Crepeau, Equivalence between two flavors of oblivious transfer, In: CRYPTO'87, LNCS, Springer-Verlag,293(1987)350-354.
[31]R. Cramer, V. Shoup, A practical public key cryptosystem provable secure against adaptive chosen ciphertext attack, In Advances in Cryptology-Crypto1998, LNCS, Berlin:Springer-Verlag, Germany,1462(1998)13-25.
[32]陈鲁生,沈世镒,现代密码学,北京：科学出版社,(2002).
[33]S.S.M. Chow, S.M. Yiu, L.C.K. Hui, K.P. Chow, Efficient forward and provably secure ID-based signcryption scheme with public verifiability and public cipher-text authenticity, Information Security and Cryptology-ICISC2003, LNCS, Berlin: Springer-Verlag,2971(2004)352-369.
[34]Z. Chen, H. Zhu, Quantum m-out-of-n oblivious transfer, Technical report, arXiv:cs.CR/0311039,(2003).
[35]W.L. Du, M.J. Atallah, Secure multi-party computation problems and their ap-plications:A review and open problems. In Proc. of New Security Paradigms Workshop, Cloudcroft, New Mexico, USA.(2001)11-20.
[36]W.L. Du, M.J. Atallah, Privacy-preserving cooperative scientific computations, In Proc. of the14th IEEE Computer Security Foundations Workshop, Nova Scotia, Canada.(2001)273-282.
[37]W.L. Du, M.J. Atallah, Privacy-preserving cooperative statistical analysis, In:17th Annual Computer Security Applications Conference, New Orleans, Louisiana, USA,(2001)102-110.
[38]Y. Dodis, S. Micali, Lower bounds for oblivious transfer reductions, In:EURO-CRYPT'99, LNCS, Springer-Verlag,1592(1999)42-55.
[39]W.L. Du, A study of several specific secure two-party computation prob-lems[Ph.D.dissertation], Purdue University, USA,(2000).
[40] D. Dolev, A.C. Yao, On the security of public key protocols, IEEE Transactionson Information Theory,29(2)(1983)198-208.
[41] S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts,Communications of the ACM,28(6)(1985)637-647.
[42] P. Feldman, A practical scheme for non-interactive verifable secret sharing, InProceedings of the28th IEEE Annual Symposium on Foundations of ComputerScience,(1987)427-437.
[43] M. Fischlin, A cost-efective pay-per-multiplication comparison method for mil-lionaires, In Proceedings of the2001Conference on Topics in Cryptology: TheCryptographer’s Track at RSA, LNCS, Springer-Verlag,2020(2001)457-472.
[44] A. Fiat, A. Shamir, How to prove yourself: Practical solutions to identifcationand signature problems, In Advances in Cryptology-Crypto’86, LNCS, Berlin:Springer-Verlag,263(1986)186-194.
[45] S. Goldwasser, S. Micali, Probabilistic encryption, Journal of Computer and Sys-tem Sciences,28(2)(1984)270-299.
[46] O. Goldreich, S. Micali, A. Wigderson, How to play ANY mental game, The19thAnnual ACM Conference on Theory of Computing, New York,(1987)218-229.
[47] O. Goldreich, Foundations of Cryptography: Basic Applications, London: Cam-bridge University Press,(2004)599-729.
[48] S. Goldwasser, Multi-party computations: past and present, Proceedings ofthe sixteenth annual ACM symposium on Principles of distributed computings,NewYork: ACM Press,(1997)21-24.
[49] O. Goldreich, Secure multi-party computation (working draft). Available fromhttp://www.wisdom.weizmann.ac.il/home/oded/public html/foc.html,(1998).
C. Gentry, C. Peikert, V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, In Proc. of STOC'08,(2008)197-206.
[51]O. Goldreich, R. Vainish, How to solve any protocol problem-an efficiency im-provement. In:CRYPTO'87, LNCS, Springer-Verlag,293(1988)73-86.
[52]I. Ioannidis, A. Grama, An Efficient Protocol for Yao's Millionaires' Problem, In Proceedings of the36th Hawaii Internatinal Conference on System Sciences2003,(2003).
[53]荆巍巍,安全多方计算中若干基础协议及应用的研究,中国科学技术大学博士论文,(2008).
[54]E.E. Karnin, J.W. Greene, M.E. Hellman, On secret sharing systems, IEEE trans-actions on information theory,29(1983)35-41.
[55]J.S. Kang, D. Hong, A Practical Privacy-Preserving Cooperative Computation Protocol without Oblivious Transfer for Linear Systems of Equations. Interna-tional Journal of Information Processing Systems,3(1)(2007)21-25.
[56]J. Kilian, Founding cryptography on oblivious transfer, Proc of20th Annual Sym-posium on the Theory of Computation(STOC), ACM,(1988)20-31.
[57]N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation,48(1987)203+209.
[58]A. Lenstra, H. Lenstra, L.Lovasz, Factoring polynomials with rational coefficients, Mathematische Annalen,261(4)(1982)515-534.
[59]W. J. Luo, X. Li, The secure multi-party protocol of matrix product and its appli-cation, Chinese Journal of Computers,28(7)(2005)1230-1235.
[60]G. Leurent,P.Q. Nguyen, How risky is the random-oracle model, CRYPTO'09,(2009)445-464.
[61]B. Libert, J.J. Quisquater, New identity based signcryption schemes from pairings.2003IEEE Information Theory Workshop, Paris, France,(2003)155-158.
[62]刘木兰,张志芳,密钥共享体制和安全多方计算,北京：电子工业出版社,(2008).
[63]J. Malone-Lee, Identity based signcryption.Cryptology ePrint Archive,Report2002/098,(2002). Available from:http://eprint.iacr.org/2002/098.
[64]V. Miller, Use of elliptic curves in cryptography, CRYPTO'85,(1985).
[65]T. Migler, K.E. Morrison, M. Ogle, How much does a matrix of rank k weight, Mathematics Magazine,79(4)(2006)262-271.
[66]D. Micciancio, O.Regev, Worst-case to average-case reductions based on Gaussian measures, SIAM J. Comput.,37(1)(2007)267-302.
[67]R.J. McEliece, D.V. Sarwate, On sharing secrets and reed-solomon codes, Com-munications of the ACM,24(1981)583-584.
[68]Y. Mu, J. Zhang, V. Varadharajan, M out of n oblivious transfer, In Proceedings of the7th Australasian Conference on Information Security and Privacy (ACISP'02), LNCS, Springer-Verlag,2384(2002)395-405.
[69]M. Naor, B. Pinkas, Oblivious Transfer and Polynomial Evaluation, In Proceedings of the31th Annual ACM Symposium on the Theory of Computing (STOC'99), ACM,(1999)245-254.
[70]M. Naor, B. Pinkas, Oblivious transfer with adaptive queries, In Proceedings of Advances in Cryptology-CRYPTO'99, LNCS, Springer-Verlag,1666(1999)573-590.
[71]K. Nissim, E. Weinreb, Communication efficient secure linear algebra, TCC2006, LNCS, Berlin:Springer,3876(2006)522-541.
[72] S. Obana, T. Araki, Almost optimum secret sharing scheme secure against cheatingfor arbitrary secret distribution, Advances in Asiacrypt’2006, LNCS, SpringerVerlag,4284(2006)364-379.
[73] T. Okamoto, Efcient Blind and Partially Blind Signatures Without Random Or-acles, In: S.Halevi and T.Rabin(Eds.): TCC2006, LNCS, Berlin: Springer-Verlag,3876(2006)80-99.
[74] W. Ogata, K. Kurosawa, D. R. Stinson, Optimum Secret Sharing Scheme Secureagainst Cheating, SIAM Journal on Discrete Mathematics,20(1)(2006)79-95.
[75] K.G. Paterson, ID-based signature from pairings on Elliptic Curves, IEE Electron-ics Letters,38(18)(2002)1025-1026.
[76] T.P. Pedersen, A threshold cryptosystem without a trusted party, In Advances inCryptology-EUROCRYPT’91, LNCS, Springer-Verlag,547(1991)522-526.
[77] C. Peikert, Bonsai trees (or, arboriculture in lattice-based cryptography). Cryp-tology ePrint Archive, Report2009/359,(2009), http://eprint.iacr.org/.
[78] K.G. Paterson, J.C.N. Schuldt, Efcient identity-based signatures secure in thestandard model, In: Proceedings of the11th Australasian Conference on Informa-tion Security and Privacy, LNCS, Springer,4058(2006)207-222.
[79] M. Rabin, How to exchange secrets by oblivious transfer. Technical Report TR-81,Aiken Computation Laboratory, Harvard University,(1981).
[80] O. Regev, On lattices, learning with errors, random linear codes, and cryptogra-phy, In STOC,(2005)84-93.
[81] C.P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms,Theor. Comput. Sci.,53(1987)201-224.
[82] A. Shamir, How to share a secret, Communications of the ACM,22(11)(1979)612-613.
[83] A. Shamir, Identity-based cryptosystems and signature schemes, In Proc. ofCRYPTO’84,(1985)47-53.
[84] P.W. Shor, Polynomial-time algorithms for prime factorization and discrete loga-rithms on a quantum computer, SIAM J. Comput.,26(5)(1997)1484-1509.
[85] H.M. Sun, S.P. Shieh, Constructions of dynamic threshold schemes.Electronicsletters,30(24)(1994)2023-2025.
[86] R. Steinfeld, H. X. Wang, J. Pieprzyk, Lattice-based threshold-changeabilityfor standard shamir secret-sharing schemes, Advances in Asiacrypt’2004, LNCS,Springer Verlag,3329(2004)170-186.
[87] J.R. Troncoso-Pastoriza, P. Comesan a, F. P e′rez Gonz′alez, Secure Direct andIterative Protocols for Solving Systems of Linear Equations, In SPEED Workshop,Lausanne, Switzerland,(2009)122-141.
[88] M. Tompa, H. Woll, How to Share a Secret with Cheaters, Journal of Cryptology,1(3)(1989)133-138.
[89] W. Tzeng, Efcient1-out-of-n oblivious transfer schemes with universally usableparameters, IEEE TRANSACTIONS ON COMPUTERS,53(2)(2004)232-240.
[90] N.N. Wu, J. Zhang, N. Li, Privacy-preserving discovery of multivariate linearrelationship, Journal of Systemics, Cybernetics and Informatics,4(5)(2006)67-72.
[91] K. Wang, X. Zou, Y. Sui, A multiple secret sharing scheme base on matrix projec-tion, Proc. COMPSAC’09,33rd Annual IEEE International Computer Softwareand Applications Conference,1(2009)400-405.
[92]F. Xia, B. Yang, W. Sun, S. Ma, An efficient identity-based signature from lattice in the random oracle model, Journal of Computational Information Systems,7(11)(2011)3963-3971.
[93]A.C. Yao, Protocols for secure computations, The23rd IEEE Symposium on Foun-dations of Computer Science, Piscataway, USA, IEEE,(1982)160-164.
[94]姚亦飞,保护私有信息的统计计算问题研究,中国科学技术大学博士论文,(2008).
[95]H. Yanai, K. Takeuchi, Y. Takane, Projecion matrices, generalized inverse matri-ces, and singular value decomposition, New York, NY Springer Science+Business Media, LCC,(2011)25-32.
[96]X. Yang, Z. Yu, B. Kang, Privacy-Preserving Cooperative Linear System of Equa-tions Protocol and its Application, The4th International Conference on Wireless Communications, Networking and Mobile Computing. Dalian.(2008).
[97]Y. Yu, B. Yang, Y. Sun et al, Identity based signcryption scheme without random oracle, Computer Standards/Interfaces,3(1)(2009)56-62.
[98]Y. Zheng, Digital signcryption or how to achieve cost (signature/encryption) cost (signature)+cost(encryption), Advances in Cryptology-CRYPTO'97, LNCS, Berlin:Springer-Verlag,1294(1997)165-179.