密码学中理性与抗泄漏关键技术的研究
|
摘要
自上世纪70年代Diffie与Hellman的“密码学的新方向”开创性的工作以来,现代密码学无论在理论研究还是在实际应用方面均已取得了极大的成功,产生了各种各样密码学原型的定义和构建,例如数字签名,公钥加密,基于身份的加密等以及基于不同的密码学原型的运用。然而,随着时代发展和科技进步,现代密码学也面临新的挑战：
1.基于现代密码学通用的计算模型：安全计算理论,尤其是两方安全计算以及多方安全计算是否只要能够防范最强的恶意攻击者就能满足实际需要?
2.现代密码学的重要前提：密钥完备保密。然而当保密密钥遭受到威胁,如各种各样的边信道攻击时,原来可证安全的安全系统是否仍然安全?
上述这两个问题在近年来引起了计算机领域中理论研究工作者,尤其是密码学家的广泛关注。本文分别针对上述两个问题中的基本问题：理性与抗泄漏问题进行研究,主要取得如下研究成果：
本文对Halpern与Pass提出的问题,即能否运用具有计算成本的计算博弈理论模型,对计算具有成本的惩罚博弈与防范秘密攻击的两方安全计算建立联系的问题做出了肯定的回答。我们提出威慑度为1/2的防范秘密攻击的安全计算是错误可忽略的计算具有成本的惩罚博弈的调解人的通用实现,并给出了严格的理论证明。
自从Yao提出两方安全计算以及Goldweich等人提出多方计算等安全计算理论以来,围绕解决不同情形尤其是防范不同攻击者的安全计算等问题,研究者提出了防范半诚实攻击者、恶意攻击者以及秘密攻击者等有效的解决方案。然而,上述诸多方案在遇到现实情形中总想最大化其个人利益的攻击者,即理性攻击者时便不再保持其原来具有的安全性。在首届国际计算理论创新会议(ICS’10)上Halpern与Pass提出具有计算成本的计算博弈理论建立起了具有计算成本的计算博弈与安全计算之间的联系。直观上讲,具有惩罚的博弈模拟了参与者进行欺骗但又不想被抓住,也即安全计算中防范秘密攻击者的情形。如果参与者均诚实的提供其输入并输出调解人的响应,则其均能获得效用为1/2；然而如果其中一个参与者输出了“punish”,则另外一个参与者获得的效用将为0；因为参与者以1/2的概率被抓住从而被惩罚,因此其欺骗的期望效用为1/2×1+1/2 x0=1/2,将不会比诚实的提供其输入并输出调解人的响应所获得效用大,而这正对应威慑度为1/2的安全计算。因此本文在该理论框架的基础上,从计算具有成本的计算博弈的角度表明威慑度为1/2的防范秘密攻击的安全计算是具有可忽略错误的调节人的通用实现,并给出了严格的理论证明。
根据抗泄漏的基于身份的哈希证明系统密码原型,本文提出基于确定性双线性Diffie-Hellman(DH)困难性假设的抗泄漏的基于身份的哈希证明系统；基于该系统,提出了抗泄漏的基于身份的加密方案。同时,在基于带错误学习(LWE)的困难性假设的基础上,提出标准模型下抗泄漏的基于身份的哈希证明系统；并在该证明系统的基础上,提出了抗泄漏的基于身份的加密方案。
现代密码学的研究前提是保证密钥的安全性。然而随着各种各样的边信道攻击的出现,许多已有的可证安全的密码系统不再保持其安全性,因此研究抗泄漏的密码原型以及抗泄漏的安全方案的构建成为目前安全研究领域迫切的任务,目前已经提出大量的抗泄漏的密码原型及抗泄漏的安全方案。Naor与Segev在Crypto’09上首次提出基于哈希证明系统的抗泄漏的公钥加密方案,Alwen等人又对其推广到身份环境,提出了抗泄漏的基于身份的哈希证明系统的密码原型。基于该抗泄漏的密码原型,本文在基于确定性双线性DH困难性假设的基础上,提出了抗泄漏的基于身份的哈希证明系统；同时又基于确定性带错误学习的困难性假设,提出了标准模型下的基于身份的哈希证明系统。上述两个抗泄漏的基于身份的哈希证明系统,均比已有的方案的所基于的假设更加简单和实用,因此也取得了更加高效的性能。最后,基于上述两种不同困难性假设的抗泄漏哈希证明系统的构建,本文又提出了抗泄漏的基于身份的加密方案。
Since W. Diffie and M. Hellman published their groundbreaking work [22], great successes have been made in both theoretical research and practical applications about modern cryptography. Many kinds of cryptographic primitives and schemes, such as digital signature, public key encryption, and identity-based encryption, etc., are defined and constructed. Of course, there are also many efficient cryptographic applications which are based on different primitives above to be constructed. With developments of sciences and technologies, however, modern cryptography now faces many different new challenges. Specifically, we just mentioned here as follows:
1. Is general model of computation based on modern cryptography, secure compu-tation, sufficient to meet the need in practice as long as it is against malicious adversaries?
2. Are provable secure cryptographic systems still secure if the premise of modern cryptography in which private key used is perfectly secure is broken when the key is encountered with leakage by all kinds of different side attacks.
Recently, much attentions are paid to the two challenges above from theoretical researchers, particularly, cryptographers. We made some contributions to two basic problems mentioned above as follows:
We give positively an answer to one of questions proposed by Halpern and Pass which is whether or not, based on the framework of computational game-theoretical implementation for cryptography, we can build the relation between computational game with punishment and secure computation against covert ad-versaries. Namely, we give and prove strictly that secure two party computation with deterrent 1/2 above is a universal implementation of the mediator with negligible error in the computational game theory.
Since general theory about secure computation is proposed by Andrew Yao and Oded Goldreich et al., respectively, researchers proposed many efficient schemes against semi-honest, malicious, and covert adversaries for different situations. However, many schemes constructed failed when they are against rational adver-saries which always make their utilities to be maximize. In ICS’10, Halpern and Pass proposed a framework of game-theoretical computation for cryptography. Intuitively, game with punishment models the situation in which players want to cheat, not to be caught, which corresponds to covert adversaries in secure two party computation. If players honestly provide their inputs to the mediator and get their output, the utilities they should get is exactly 1/2. However, if one of players outputs”punish”, another will get the utility with 0. If rational player is caught with probability 1/2 to be punished, at this point his expected utility is 1/2 x 1+1/2 x 0= 1/2, which is not higher than that honestly providing his input to the mediator, which exactly corresponds to secure two party com-putation with deterrent 1/2 against covert adversaries. Therefor, based on the framework, we strictly prove that secure two party computation with deterrent 1/2 against covert adversaries is a universal implementation of the mediator in game theory with punishment and costly computation.
Based on a cryptographic primitive of identity-based hash proof system with resilient leakage, we propose two identity-based hash proof systems based on decisional bilinear Diffie-Hellman assumption and decisional learning with error assumption(dLWE), respectively. Particularly, it is constructed in the standard model, without random oracle for dLWE. Further according to the constructions above, we construct two identity-based encryption with resilient leakage:More-over, we give strict proofs to the schemes constructed above.
One of the key premises of modern cryptography is to ensure private key perfectly secure. Under all kinds of side channel attacks, however, many cryptographic sys-tems which are provably secure now are not secure against these attacks. Hence it is urgent for researchers to construct cryptographic systems with resilient leakage. Fortunately, nowadays there are many excellent schemes with resilient leakage proposed. In Crypto’10, Naor and Segev proposed first public key encryption with resilient leakage based on hash proof system. Then Alwen et al. extended it to the identity-based situation. Namely, they proposed public key encryption with resilient leakage based on the primitive of identity-based hash proof system. According to the cryptographic primitive, that is, identity-based hash proof sys- tem, we construct two identity-based hash proof system based on different in-tractable assumptions, namely, decisional bilinear DH assumption and dLWE. Our schemes are more efficient and practical than those constructed by Alwen et al. since in our schemes one is based on a simple assumption (i.e., decisional bilinear DH), the other is based on dLWE in the standard model. Based on two constructions above, we further propose two identity-based encryption schemes with resilient leakage which are proved strictly through a series of games.
1.基于现代密码学通用的计算模型：安全计算理论,尤其是两方安全计算以及多方安全计算是否只要能够防范最强的恶意攻击者就能满足实际需要?
2.现代密码学的重要前提：密钥完备保密。然而当保密密钥遭受到威胁,如各种各样的边信道攻击时,原来可证安全的安全系统是否仍然安全?
上述这两个问题在近年来引起了计算机领域中理论研究工作者,尤其是密码学家的广泛关注。本文分别针对上述两个问题中的基本问题：理性与抗泄漏问题进行研究,主要取得如下研究成果：
本文对Halpern与Pass提出的问题,即能否运用具有计算成本的计算博弈理论模型,对计算具有成本的惩罚博弈与防范秘密攻击的两方安全计算建立联系的问题做出了肯定的回答。我们提出威慑度为1/2的防范秘密攻击的安全计算是错误可忽略的计算具有成本的惩罚博弈的调解人的通用实现,并给出了严格的理论证明。
自从Yao提出两方安全计算以及Goldweich等人提出多方计算等安全计算理论以来,围绕解决不同情形尤其是防范不同攻击者的安全计算等问题,研究者提出了防范半诚实攻击者、恶意攻击者以及秘密攻击者等有效的解决方案。然而,上述诸多方案在遇到现实情形中总想最大化其个人利益的攻击者,即理性攻击者时便不再保持其原来具有的安全性。在首届国际计算理论创新会议(ICS’10)上Halpern与Pass提出具有计算成本的计算博弈理论建立起了具有计算成本的计算博弈与安全计算之间的联系。直观上讲,具有惩罚的博弈模拟了参与者进行欺骗但又不想被抓住,也即安全计算中防范秘密攻击者的情形。如果参与者均诚实的提供其输入并输出调解人的响应,则其均能获得效用为1/2；然而如果其中一个参与者输出了“punish”,则另外一个参与者获得的效用将为0；因为参与者以1/2的概率被抓住从而被惩罚,因此其欺骗的期望效用为1/2×1+1/2 x0=1/2,将不会比诚实的提供其输入并输出调解人的响应所获得效用大,而这正对应威慑度为1/2的安全计算。因此本文在该理论框架的基础上,从计算具有成本的计算博弈的角度表明威慑度为1/2的防范秘密攻击的安全计算是具有可忽略错误的调节人的通用实现,并给出了严格的理论证明。
根据抗泄漏的基于身份的哈希证明系统密码原型,本文提出基于确定性双线性Diffie-Hellman(DH)困难性假设的抗泄漏的基于身份的哈希证明系统；基于该系统,提出了抗泄漏的基于身份的加密方案。同时,在基于带错误学习(LWE)的困难性假设的基础上,提出标准模型下抗泄漏的基于身份的哈希证明系统；并在该证明系统的基础上,提出了抗泄漏的基于身份的加密方案。
现代密码学的研究前提是保证密钥的安全性。然而随着各种各样的边信道攻击的出现,许多已有的可证安全的密码系统不再保持其安全性,因此研究抗泄漏的密码原型以及抗泄漏的安全方案的构建成为目前安全研究领域迫切的任务,目前已经提出大量的抗泄漏的密码原型及抗泄漏的安全方案。Naor与Segev在Crypto’09上首次提出基于哈希证明系统的抗泄漏的公钥加密方案,Alwen等人又对其推广到身份环境,提出了抗泄漏的基于身份的哈希证明系统的密码原型。基于该抗泄漏的密码原型,本文在基于确定性双线性DH困难性假设的基础上,提出了抗泄漏的基于身份的哈希证明系统；同时又基于确定性带错误学习的困难性假设,提出了标准模型下的基于身份的哈希证明系统。上述两个抗泄漏的基于身份的哈希证明系统,均比已有的方案的所基于的假设更加简单和实用,因此也取得了更加高效的性能。最后,基于上述两种不同困难性假设的抗泄漏哈希证明系统的构建,本文又提出了抗泄漏的基于身份的加密方案。
Since W. Diffie and M. Hellman published their groundbreaking work [22], great successes have been made in both theoretical research and practical applications about modern cryptography. Many kinds of cryptographic primitives and schemes, such as digital signature, public key encryption, and identity-based encryption, etc., are defined and constructed. Of course, there are also many efficient cryptographic applications which are based on different primitives above to be constructed. With developments of sciences and technologies, however, modern cryptography now faces many different new challenges. Specifically, we just mentioned here as follows:
1. Is general model of computation based on modern cryptography, secure compu-tation, sufficient to meet the need in practice as long as it is against malicious adversaries?
2. Are provable secure cryptographic systems still secure if the premise of modern cryptography in which private key used is perfectly secure is broken when the key is encountered with leakage by all kinds of different side attacks.
Recently, much attentions are paid to the two challenges above from theoretical researchers, particularly, cryptographers. We made some contributions to two basic problems mentioned above as follows:
We give positively an answer to one of questions proposed by Halpern and Pass which is whether or not, based on the framework of computational game-theoretical implementation for cryptography, we can build the relation between computational game with punishment and secure computation against covert ad-versaries. Namely, we give and prove strictly that secure two party computation with deterrent 1/2 above is a universal implementation of the mediator with negligible error in the computational game theory.
Since general theory about secure computation is proposed by Andrew Yao and Oded Goldreich et al., respectively, researchers proposed many efficient schemes against semi-honest, malicious, and covert adversaries for different situations. However, many schemes constructed failed when they are against rational adver-saries which always make their utilities to be maximize. In ICS’10, Halpern and Pass proposed a framework of game-theoretical computation for cryptography. Intuitively, game with punishment models the situation in which players want to cheat, not to be caught, which corresponds to covert adversaries in secure two party computation. If players honestly provide their inputs to the mediator and get their output, the utilities they should get is exactly 1/2. However, if one of players outputs”punish”, another will get the utility with 0. If rational player is caught with probability 1/2 to be punished, at this point his expected utility is 1/2 x 1+1/2 x 0= 1/2, which is not higher than that honestly providing his input to the mediator, which exactly corresponds to secure two party com-putation with deterrent 1/2 against covert adversaries. Therefor, based on the framework, we strictly prove that secure two party computation with deterrent 1/2 against covert adversaries is a universal implementation of the mediator in game theory with punishment and costly computation.
Based on a cryptographic primitive of identity-based hash proof system with resilient leakage, we propose two identity-based hash proof systems based on decisional bilinear Diffie-Hellman assumption and decisional learning with error assumption(dLWE), respectively. Particularly, it is constructed in the standard model, without random oracle for dLWE. Further according to the constructions above, we construct two identity-based encryption with resilient leakage:More-over, we give strict proofs to the schemes constructed above.
One of the key premises of modern cryptography is to ensure private key perfectly secure. Under all kinds of side channel attacks, however, many cryptographic sys-tems which are provably secure now are not secure against these attacks. Hence it is urgent for researchers to construct cryptographic systems with resilient leakage. Fortunately, nowadays there are many excellent schemes with resilient leakage proposed. In Crypto’10, Naor and Segev proposed first public key encryption with resilient leakage based on hash proof system. Then Alwen et al. extended it to the identity-based situation. Namely, they proposed public key encryption with resilient leakage based on the primitive of identity-based hash proof system. According to the cryptographic primitive, that is, identity-based hash proof sys- tem, we construct two identity-based hash proof system based on different in-tractable assumptions, namely, decisional bilinear DH assumption and dLWE. Our schemes are more efficient and practical than those constructed by Alwen et al. since in our schemes one is based on a simple assumption (i.e., decisional bilinear DH), the other is based on dLWE in the standard model. Based on two constructions above, we further propose two identity-based encryption schemes with resilient leakage which are proved strictly through a series of games.
引文
[1]Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Y. Halpern. Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In PODC, pages 53-62,2006.
[2]Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient lattice (h)ibe in the standard model. In EUROCRYPT, pages 553-572,2010.
[3]Miklos Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99-108,1996.
[4]Miklos Ajtai. Generating hard instances of the short basis problem. In ICALP, pages 1-9,1999.
[5]Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In TCC, pages 474-495,2009.
[6]Joel Alwen, Yevgeniy Dodis, Moni Naor, Gil Segev, Shabsi Walfish, and Daniel Wichs. Public-key encryption in the bounded-retrieval model. In EUROCRYPT, pages 462-482,2010.
[7]Joel Alwen, Yevgeniy Dodis, and Daniel Wichs. Leakage-resilient public-key cryp-tography in the bounded-retrieval model. In CRYPTO, pages 36-54,2009.
[8]Joel Alwen and Chris Peikert. Generating shorter bases for hard random lattices. In STACS, pages 75-86,2009.
[9]Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast crypto-graphic primitives and circular-secure encryption based on hard learning problems. In CRYPTO, pages 595-618,2009.
[10]Gilad Asharov and Yehuda Lindell. Utility dependence in correct and fair rational secret sharing. In CRYPTO, pages 559-576,2009.
[11]Yonatan Aumann and Yehuda Lindell. Security against covert adversaries: Effi-cient protocols for realistic adversaries. In TCC, pages 137-156,2007.
[12]Eli Biham and Adi Shamir. Differential fault analysis of secret key cryptosystems. In CRYPTO, pages 513-525,1997.
[13]Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. On the importance of checking cryptographic protocols for faults (extended abstract). In EUROCRYPT, pages 37-51,1997.
[14]Dan Boneh and Matthew K. Franklin. Identity-based encryption from the weil pairing. In CRYPTO, pages 213-229,2001.
[15]Victor Boyko. On the security properties of oaep as an all-or-nothing transform. In CRYPTO, pages 503-518,1999.
[16]Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, and Vinod Vaikuntanathan. Cryptography resilient to continual memory leakage. Cryptology ePrint Archive, Report 2010/278,2010. http://eprint.iacr.org/.
[17]Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In EUROCRYPT, pages 453-469,2000.
[18]David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. In EUROCRYPT, pages 523-552,2010.
[19]Clifford Cocks. An identity based encryption scheme based on quadratic residues. In IMA Int. Conf., pages 360-363,2001.
[20]Ronald Cramer and Ivan Damg(?)rd. On the amortized complexity of zero-knowledge protocols. In CRYPTO, pages 177-191,2009.
[21]Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In EUROCRYPT, pages 45-64,2002.
[22]Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654,1976.
[23]Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Public-key encryption schemes with auxiliary inputs. In TCC, pages 361-381,2010.
[24]Yevgeniy Dodis, Shai Halevi, and Tal Rabin. A cryptographic solution to a game theoretic problem. In CRYPTO, pages 112-130,2000.
[25]Yevgeniy Dodis, Kristiyan Haralambiev, Adriana Lopez-Alt, and Daniel Wichs. Cryptography against continuous memory attacks. Cryptology ePrint Archive, Report 2010/196,2010. http://eprint.iacr.org/.
[26]Yevgeniy Dodis, Yael Tauman Kalai, and Shachar Lovett. On cryptography with auxiliary input. In STOC, pages 621-630,2009.
[27]Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, and Amit Sahai. On the (im)possibility of cryptography with imperfect randomness. In FOCS, pages 196-205,2004.
[28]Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extrac-tors:How to generate strong keys from biometrics and other noisy data. SIAM J. Comput.,38(1):97-139,2008.
[29]D. Dummit and R. Foote. Abstract Algebra. Prentice Hall, New Jersey,1999.
[30]Stefan Dziembowski and Krzysztof Pietrzak. Leakage-resilient cryptography. In FOCS, pages 293-302,2008.
[31]F. Forges. An approach to communication equilibria. Econometrica, 54(6):1375-1385,1986.
[32]F. Forges. Universal mechanisms. Econometrica,58(6):1341-1364,1990.
[33]Lance Fortnow and Rahul Santhanam. Bounding rationality by discounting time. In 1st ICS, Janurary 2010.
[34]Georg Fuchsbauer, Jonathan Katz, and David Naccache. Efficient rational secret sharing in standard communication networks. In TCC, pages 419-436,2010.
[35]Drew Fudenberg and Jean Tirole. Game Theory. MIT Press,1990.
[36]Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic anal-ysis:Concrete results. In CHES, number Generators, pages 251-261,2001.
[37]Craig Gentry. Practical identity-based encryption without random oracles. In EUROCRYPT, pages 445-464,2006.
[38]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197-206,2008.
[39]O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game-a completeness therorem for protocols with honest majority. In In 19th STOC, pages 218-229,1987.
[40]Oded Goldreich. Foundations of Cryptography: Volume 1-Basic Techniques. Cambridge Univ. Press,2001.
[41]Shafi Goldwasser, Yael Kalai, Chris Peikert, and Vinod Vaikuntanathan. Robust-ness of the learning with errors assumption. In 1st ICS, Janurary 2010.
[42]Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. One-time programs. In CRYPTO, pages 39-56,2008.
[43]S. Dov Gordon, Carmit Hazay, Jonathan Katz, and Yehuda Lindell. Complete fairness in secure two-party computation. In STOC, pages 413-422,2008.
[44]S. Dov Gordon and Jonathan Katz. Rational secret sharing, revisited. In SCN, pages 229-241,2006.
[45]Ronen Gradwohl. Rationality in the full-information model. In TCC, pages 401-418,2010.
[46]Ronen Gradwohl, Noam Livne, and Alon Rosen. Sequential rationality in crypto-graphic protocols. In FOCS, pages ??-??,2010.
[47]J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten. Lest we remember: Cold boot attacks on encryption keys. In USENIX Security Symposium, pages 45-60,2008.
[48]Joseph Y. Halpern and Vanessa Teague. Rational secret sharing and multiparty computation:extended abstract. In STOC, pages 623-632,2004.
[49]Josheph Halpern and Rafael Pass. A computational game-theoretic framework for cryptography. Unpublished manuscript, December 2009.
[50]Josheph Halpern and Rafael Pass. Game theory with costly computation:Formu-lation and application to protocol security. In 1st ICS, Janurary 2010.
[51]Yuval Ishai, Amit Sahai, and David Wagner. Private circuits:Securing hardware against probing attacks. In CRYPTO, pages 463-481,2003.
[52]Sergei Izmalkov, Matt Lepinski, and Silvio Micali. Verifiably secure devices. In TCC, pages 273-301,2008.
[53]Sergei Izmalkov, Silvio Micali, and Matt Lepinski. Rational secure computation and ideal mechanism design. In FOCS, pages 585-595,2005.
[54]Jonathan Katz and Vinod Vaikuntanathan. Signature schemes with bounded leakage resilience. In ASIACRYPT, pages 703-720,2009.
[55]Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography, pages 315-329,2007.
[56]Eike Kiltz, Krzysztof Pietrzak, Martijn Stam, and Moti Yung. A new randomness extraction paradigm for hybrid encryption. In EUROCRYPT, pages 590-609, 2009.
[57]Paul C. Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In CRYPTO, pages 104-113,1996.
[58]Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In CRYPTO, pages 388-397,1999.
[59]Gillat Kol and Moni Naor. Cryptography and game theory: Designing protocols for exchanging information. In TCC, pages 320-339, 2008.
[60]Gillat Kol and Moni Naor. Games for exchanging information. In STOC, pages 423-432,2008.
[61]Matt Lepinski, Silvio Micali, Chris Peikert, and Abhi Shelat. Completely fair sfe and coalition-safe cheap talk. In PODC, pages 1-10,2004.
[62]Matt Lepinski, Silvio Micali, and Abhi Shelat. Collusion-free protocols. In STOC, pages 543-552,2005.
[63]Allison B. Lewko and Brent Waters. New techniques for dual system encryption and fully secure hibe with short ciphertexts. In TCC, pages 455-479,2010.
[64]Xizhao Luo, Peide Qian, and Yanqin Zhu. A game-theoretic implementation of secure computation against covert adversaries. Accepted,2010.
[65]Xizhao Luo, Peide Qian, and Yanqin Zhu. Resilient-leakage identity-based en-cryption scheme from lattices in the standard model. Accpted,2010.
[66]Xizhao Luo, Peide Qian, Yanqin Zhu, and Shangping Wang. Resilient-leakage identity-based encryption scheme in the standard model. In NCM, pages ??-??, 2010.
[67]Anna Lysyanskaya and Nikos Triandopoulos. Rationality and adversarial behavior in multi-party computation. In CRYPTO, pages 180-197,2006.
[68]Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learn-ing with errors over rings. In EUROCRYPT, pages 1-23,2010.
[69]Silvio Micali and Rafael Pass. Local zero knowledge. In STOC, pages 306-315, 2006.
[70]Silvio Micali and Leonid Reyzin. Physically observable cryptography (extended abstract). In TCC, pages 278-296,2004.
[71]Silvio Micali and Abhi Shelat. Purely rational secret sharing (extended abstract). In TCC, pages 54-71,2009.
[72]Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: a cryp-tographic perspective, volume 671 of The Kluwer International Series in Engineer-ing and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts, March 2002.
[73]Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. In FOCS, pages 372-381,2004.
[74]Moni Naor and Gil Segev. Public-key cryptosystems resilient to key leakage. In CRYPTO, pages 18-35,2009.
[75]Noam Nisan and David Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci.,52(1):43-52,1996.
[76]Shien Jin Ong, David C. Parkes, Alon Rosen, and Salil P. Vadhan. Fairness with an honest minority and a rational majority. In TCC, pages 36-53,2009.
[77]Rafael Pass and abhi shelat. Renegotiation-safe protocols. Unpublished manuscript, August 2010.
[78]Chris Peikert. Public-key cryptosystems from the worst-case shortest vector prob-lem:extended abstract. In STOC, pages 333-342,2009.
[79]Chris Peikert. An efficient and parallel gaussian sampler for lattices. In CRYPTO, pages?-?,2010.
[80]Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, pages 554-571,2008.
[81]Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. In STOC, pages 187-196,2008.
[82]Christophe Petit, Frangois-Xavier Standaert, Olivier Pereira, Tal Malkin, and Moti Yung. A block cipher based pseudo random number generator secure against side-channel key recovery. In ASIACCS, pages 56-65,2008.
[83]Krzysztof Pietrzak. A leakage-resilient mode of operation. In EUROCRYPT, pages 462-482,2009.
[84]Oded Regev. New lattice-based cryptographic constructions. J. ACM,51(6):899-942,2004.
[85]Oded Regev. On lattices, learning with errors, random linear codes, and cryptog-raphy. In STOC, pages 84-93,2005.
[86]Oded Regev. Lattice-based cryptography. In CRYPTO, pages 131-141,2006.
[87]Ronald L. Rivest. All-or-nothing encryption and the package transform. In FSE, pages 210-218,1997.
[88]Adi Shamir. Identity-based cryptosystems and signature schemes. In CRYPTO, pages 47-53,1984.
[89]Yoav Shoham and Moshe Tennenholtz. Non-cooperative computation: Boolean functions with correctness and exclusivity. Theor. Comput. Sci., 343(1-2):97-113, 2005.
[90]Brent Waters. Efficient identity-based encryption without random oracles. In EUROCRYPT, pages 114-127,2005.
[91]Brent Waters. Dual system encryption:Realizing fully secure ibe and hibe under simple assumptions. In CRYPTO, pages 619-636,2009.
[92]A. Yao. How to generate and exchange secrets. In In 27th FOCS, pages 162-167, 1986.
1奇异值定义：设A为m×n阶矩阵,A＇表示A的转置矩阵,A＇×A的n个特征值的非负平方根叫作A的奇异值。上述奇异值满足：σ1(A)不会比■小,但也不会大很多。
2该算法不同于文献[2]之处在于我们采用了文献[79]提出的改进的取样算法,其具有更大的高斯宽度和改进的效率。
1为了简单化,我们在此仅对一比特信息进行加密
[2]Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient lattice (h)ibe in the standard model. In EUROCRYPT, pages 553-572,2010.
[3]Miklos Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99-108,1996.
[4]Miklos Ajtai. Generating hard instances of the short basis problem. In ICALP, pages 1-9,1999.
[5]Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In TCC, pages 474-495,2009.
[6]Joel Alwen, Yevgeniy Dodis, Moni Naor, Gil Segev, Shabsi Walfish, and Daniel Wichs. Public-key encryption in the bounded-retrieval model. In EUROCRYPT, pages 462-482,2010.
[7]Joel Alwen, Yevgeniy Dodis, and Daniel Wichs. Leakage-resilient public-key cryp-tography in the bounded-retrieval model. In CRYPTO, pages 36-54,2009.
[8]Joel Alwen and Chris Peikert. Generating shorter bases for hard random lattices. In STACS, pages 75-86,2009.
[9]Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast crypto-graphic primitives and circular-secure encryption based on hard learning problems. In CRYPTO, pages 595-618,2009.
[10]Gilad Asharov and Yehuda Lindell. Utility dependence in correct and fair rational secret sharing. In CRYPTO, pages 559-576,2009.
[11]Yonatan Aumann and Yehuda Lindell. Security against covert adversaries: Effi-cient protocols for realistic adversaries. In TCC, pages 137-156,2007.
[12]Eli Biham and Adi Shamir. Differential fault analysis of secret key cryptosystems. In CRYPTO, pages 513-525,1997.
[13]Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. On the importance of checking cryptographic protocols for faults (extended abstract). In EUROCRYPT, pages 37-51,1997.
[14]Dan Boneh and Matthew K. Franklin. Identity-based encryption from the weil pairing. In CRYPTO, pages 213-229,2001.
[15]Victor Boyko. On the security properties of oaep as an all-or-nothing transform. In CRYPTO, pages 503-518,1999.
[16]Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, and Vinod Vaikuntanathan. Cryptography resilient to continual memory leakage. Cryptology ePrint Archive, Report 2010/278,2010. http://eprint.iacr.org/.
[17]Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In EUROCRYPT, pages 453-469,2000.
[18]David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. In EUROCRYPT, pages 523-552,2010.
[19]Clifford Cocks. An identity based encryption scheme based on quadratic residues. In IMA Int. Conf., pages 360-363,2001.
[20]Ronald Cramer and Ivan Damg(?)rd. On the amortized complexity of zero-knowledge protocols. In CRYPTO, pages 177-191,2009.
[21]Ronald Cramer and Victor Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In EUROCRYPT, pages 45-64,2002.
[22]Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654,1976.
[23]Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Public-key encryption schemes with auxiliary inputs. In TCC, pages 361-381,2010.
[24]Yevgeniy Dodis, Shai Halevi, and Tal Rabin. A cryptographic solution to a game theoretic problem. In CRYPTO, pages 112-130,2000.
[25]Yevgeniy Dodis, Kristiyan Haralambiev, Adriana Lopez-Alt, and Daniel Wichs. Cryptography against continuous memory attacks. Cryptology ePrint Archive, Report 2010/196,2010. http://eprint.iacr.org/.
[26]Yevgeniy Dodis, Yael Tauman Kalai, and Shachar Lovett. On cryptography with auxiliary input. In STOC, pages 621-630,2009.
[27]Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, and Amit Sahai. On the (im)possibility of cryptography with imperfect randomness. In FOCS, pages 196-205,2004.
[28]Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extrac-tors:How to generate strong keys from biometrics and other noisy data. SIAM J. Comput.,38(1):97-139,2008.
[29]D. Dummit and R. Foote. Abstract Algebra. Prentice Hall, New Jersey,1999.
[30]Stefan Dziembowski and Krzysztof Pietrzak. Leakage-resilient cryptography. In FOCS, pages 293-302,2008.
[31]F. Forges. An approach to communication equilibria. Econometrica, 54(6):1375-1385,1986.
[32]F. Forges. Universal mechanisms. Econometrica,58(6):1341-1364,1990.
[33]Lance Fortnow and Rahul Santhanam. Bounding rationality by discounting time. In 1st ICS, Janurary 2010.
[34]Georg Fuchsbauer, Jonathan Katz, and David Naccache. Efficient rational secret sharing in standard communication networks. In TCC, pages 419-436,2010.
[35]Drew Fudenberg and Jean Tirole. Game Theory. MIT Press,1990.
[36]Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic anal-ysis:Concrete results. In CHES, number Generators, pages 251-261,2001.
[37]Craig Gentry. Practical identity-based encryption without random oracles. In EUROCRYPT, pages 445-464,2006.
[38]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197-206,2008.
[39]O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game-a completeness therorem for protocols with honest majority. In In 19th STOC, pages 218-229,1987.
[40]Oded Goldreich. Foundations of Cryptography: Volume 1-Basic Techniques. Cambridge Univ. Press,2001.
[41]Shafi Goldwasser, Yael Kalai, Chris Peikert, and Vinod Vaikuntanathan. Robust-ness of the learning with errors assumption. In 1st ICS, Janurary 2010.
[42]Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. One-time programs. In CRYPTO, pages 39-56,2008.
[43]S. Dov Gordon, Carmit Hazay, Jonathan Katz, and Yehuda Lindell. Complete fairness in secure two-party computation. In STOC, pages 413-422,2008.
[44]S. Dov Gordon and Jonathan Katz. Rational secret sharing, revisited. In SCN, pages 229-241,2006.
[45]Ronen Gradwohl. Rationality in the full-information model. In TCC, pages 401-418,2010.
[46]Ronen Gradwohl, Noam Livne, and Alon Rosen. Sequential rationality in crypto-graphic protocols. In FOCS, pages ??-??,2010.
[47]J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten. Lest we remember: Cold boot attacks on encryption keys. In USENIX Security Symposium, pages 45-60,2008.
[48]Joseph Y. Halpern and Vanessa Teague. Rational secret sharing and multiparty computation:extended abstract. In STOC, pages 623-632,2004.
[49]Josheph Halpern and Rafael Pass. A computational game-theoretic framework for cryptography. Unpublished manuscript, December 2009.
[50]Josheph Halpern and Rafael Pass. Game theory with costly computation:Formu-lation and application to protocol security. In 1st ICS, Janurary 2010.
[51]Yuval Ishai, Amit Sahai, and David Wagner. Private circuits:Securing hardware against probing attacks. In CRYPTO, pages 463-481,2003.
[52]Sergei Izmalkov, Matt Lepinski, and Silvio Micali. Verifiably secure devices. In TCC, pages 273-301,2008.
[53]Sergei Izmalkov, Silvio Micali, and Matt Lepinski. Rational secure computation and ideal mechanism design. In FOCS, pages 585-595,2005.
[54]Jonathan Katz and Vinod Vaikuntanathan. Signature schemes with bounded leakage resilience. In ASIACRYPT, pages 703-720,2009.
[55]Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography, pages 315-329,2007.
[56]Eike Kiltz, Krzysztof Pietrzak, Martijn Stam, and Moti Yung. A new randomness extraction paradigm for hybrid encryption. In EUROCRYPT, pages 590-609, 2009.
[57]Paul C. Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In CRYPTO, pages 104-113,1996.
[58]Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In CRYPTO, pages 388-397,1999.
[59]Gillat Kol and Moni Naor. Cryptography and game theory: Designing protocols for exchanging information. In TCC, pages 320-339, 2008.
[60]Gillat Kol and Moni Naor. Games for exchanging information. In STOC, pages 423-432,2008.
[61]Matt Lepinski, Silvio Micali, Chris Peikert, and Abhi Shelat. Completely fair sfe and coalition-safe cheap talk. In PODC, pages 1-10,2004.
[62]Matt Lepinski, Silvio Micali, and Abhi Shelat. Collusion-free protocols. In STOC, pages 543-552,2005.
[63]Allison B. Lewko and Brent Waters. New techniques for dual system encryption and fully secure hibe with short ciphertexts. In TCC, pages 455-479,2010.
[64]Xizhao Luo, Peide Qian, and Yanqin Zhu. A game-theoretic implementation of secure computation against covert adversaries. Accepted,2010.
[65]Xizhao Luo, Peide Qian, and Yanqin Zhu. Resilient-leakage identity-based en-cryption scheme from lattices in the standard model. Accpted,2010.
[66]Xizhao Luo, Peide Qian, Yanqin Zhu, and Shangping Wang. Resilient-leakage identity-based encryption scheme in the standard model. In NCM, pages ??-??, 2010.
[67]Anna Lysyanskaya and Nikos Triandopoulos. Rationality and adversarial behavior in multi-party computation. In CRYPTO, pages 180-197,2006.
[68]Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learn-ing with errors over rings. In EUROCRYPT, pages 1-23,2010.
[69]Silvio Micali and Rafael Pass. Local zero knowledge. In STOC, pages 306-315, 2006.
[70]Silvio Micali and Leonid Reyzin. Physically observable cryptography (extended abstract). In TCC, pages 278-296,2004.
[71]Silvio Micali and Abhi Shelat. Purely rational secret sharing (extended abstract). In TCC, pages 54-71,2009.
[72]Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: a cryp-tographic perspective, volume 671 of The Kluwer International Series in Engineer-ing and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts, March 2002.
[73]Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. In FOCS, pages 372-381,2004.
[74]Moni Naor and Gil Segev. Public-key cryptosystems resilient to key leakage. In CRYPTO, pages 18-35,2009.
[75]Noam Nisan and David Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci.,52(1):43-52,1996.
[76]Shien Jin Ong, David C. Parkes, Alon Rosen, and Salil P. Vadhan. Fairness with an honest minority and a rational majority. In TCC, pages 36-53,2009.
[77]Rafael Pass and abhi shelat. Renegotiation-safe protocols. Unpublished manuscript, August 2010.
[78]Chris Peikert. Public-key cryptosystems from the worst-case shortest vector prob-lem:extended abstract. In STOC, pages 333-342,2009.
[79]Chris Peikert. An efficient and parallel gaussian sampler for lattices. In CRYPTO, pages?-?,2010.
[80]Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, pages 554-571,2008.
[81]Chris Peikert and Brent Waters. Lossy trapdoor functions and their applications. In STOC, pages 187-196,2008.
[82]Christophe Petit, Frangois-Xavier Standaert, Olivier Pereira, Tal Malkin, and Moti Yung. A block cipher based pseudo random number generator secure against side-channel key recovery. In ASIACCS, pages 56-65,2008.
[83]Krzysztof Pietrzak. A leakage-resilient mode of operation. In EUROCRYPT, pages 462-482,2009.
[84]Oded Regev. New lattice-based cryptographic constructions. J. ACM,51(6):899-942,2004.
[85]Oded Regev. On lattices, learning with errors, random linear codes, and cryptog-raphy. In STOC, pages 84-93,2005.
[86]Oded Regev. Lattice-based cryptography. In CRYPTO, pages 131-141,2006.
[87]Ronald L. Rivest. All-or-nothing encryption and the package transform. In FSE, pages 210-218,1997.
[88]Adi Shamir. Identity-based cryptosystems and signature schemes. In CRYPTO, pages 47-53,1984.
[89]Yoav Shoham and Moshe Tennenholtz. Non-cooperative computation: Boolean functions with correctness and exclusivity. Theor. Comput. Sci., 343(1-2):97-113, 2005.
[90]Brent Waters. Efficient identity-based encryption without random oracles. In EUROCRYPT, pages 114-127,2005.
[91]Brent Waters. Dual system encryption:Realizing fully secure ibe and hibe under simple assumptions. In CRYPTO, pages 619-636,2009.
[92]A. Yao. How to generate and exchange secrets. In In 27th FOCS, pages 162-167, 1986.
1奇异值定义：设A为m×n阶矩阵,A＇表示A的转置矩阵,A＇×A的n个特征值的非负平方根叫作A的奇异值。上述奇异值满足：σ1(A)不会比■小,但也不会大很多。
2该算法不同于文献[2]之处在于我们采用了文献[79]提出的改进的取样算法,其具有更大的高斯宽度和改进的效率。
1为了简单化,我们在此仅对一比特信息进行加密