Quantum security analysis of a lattice-based oblivious transfer protocol

Mo-meng LIU; Juliane KRMER; Yu-pu HU; Johannes BUCHMANN

doi:10.1631/FITEE.1700039

Your Location：

Home >

Browse articles >

Quantum security analysis of a lattice-based oblivious transfer protocol

Regular Papers | Updated：2022-05-19

- Quantum security analysis of a lattice-based oblivious transfer protocol
- 一个格上不经意传输协议的量子安全性分析
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 9, Pages: 1348-1369(2017)
- Affiliations：
  
  State Key Laboratory of Integrated Service Networks, Xidian University, Xi'an 710071, China
  Technische Universitt Darmstadt, Darmstadt 64289, Germany
- Author bio：
  
  Mo-meng LIU, E-mail: liumomeng@gmail.com
- Funds：
- DOI：10.1631/FITEE.1700039
  CLC： TP309.7
- Received：12 January 2017，
  
  Revised：2017-;9-24，
  
  Published：2017-09
- Accepted：
Scan QR Code
Mo-meng LIU, Juliane KRMER, Yu-pu HU, et al. Quantum security analysis of a lattice-based oblivious transfer protocol[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(9): 1348-1369.
DOI：

Mo-meng LIU, Juliane KRMER, Yu-pu HU, et al. Quantum security analysis of a lattice-based oblivious transfer protocol[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(9): 1348-1369. DOI： 10.1631/FITEE.1700039.

摘要

不经意传输协议（oblivious transfer

OT）因其简易的密码功能广泛应用于安全多方计算。以往OT协议都是基于传统数论问题（例如，离散对数，大数分解问题）所构造的，随着量子计算技术的发展，基于传统困难问题的OT协议安全性受到极大的威胁。因此，人们转而考虑使用后量子密码技术替代以往OT协议所依赖的传统困难问题。目前，已有一些基于后量子密码体制的OT协议被提出。然而，大多数后量子密码构造只在假设传统敌手存在的环境下证明其方案安全性。在本文中，我们在量子敌手存在的环境下，证明一个基于格公钥密码的OT协议（[PVW08]）的安全性。首先我们使用量子平移定理（[Unr10]）证明该协议的安全性可以完全平移到量子环境中，此外，我们还使用其他两个专用于分析后量子密码原语的分析模型（[HSS11]，[Son14]）从不同的角度对该协议进行安全性分析，从而保证我们给出的量子安全证明的正确性。我们的成果可以看作对后量子密码协议分析模型的一个实际应用实例。

Abstract

Because of the concise functionality of oblivious transfer (OT) protocols

they have been widely used as building blocks in secure multiparty computation and high-level protocols. The security of OT protocols built upon classical number theoretic problems

such as the discrete logarithm and factoring

however

is threatened as a result of the huge progress in quantum computing. Therefore

post-quantum cryptography is needed for protocols based on classical problems

and several proposals for post-quantum OT protocols exist. However

most post-quantum cryptosystems present their security proof only in the context of classical adversaries

not in the quantum setting. In this paper

we close this gap and prove the security of the lattice-based OT protocol proposed by Peikert et al. (CRYPTO

2008)

which is universally composably secure under the assumption of learning with errors hardness

in the quantum setting. We apply three general quantum security analysis frameworks. First

we apply the quantum lifting theorem proposed by Unruh (EUROCRYPT

2010) to prove that the security of the lattice-based OT protocol can be lifted into the quantum world. Then

we apply two more security analysis frameworks specified for post-quantum cryptographic primitives

i.e.

simple hybrid arguments (CRYPTO

2011) and game-preserving reduction (PQCrypto

2014).

关键词

Keywords

references

D.J. Bernstein , , , J. Buchamann , , , E. Dahmen . . PostQuantum Cryptography . . Springer, Berlin. , , 2009 . . DOI: 10.1007/978-3-540-88702-7 http://doi.org/10.1007/978-3-540-88702-7 . .

R. Canetti . . Universally composable security: a new paradigm for cryptographic protocols . . Proc. 42nd IEEE Symp. on Foundations of Computer Science , , 2001 . . p.136 - - 145 . . DOI: 10.1109/SFCS.2001.959888 http://doi.org/10.1109/SFCS.2001.959888 . .

I. Damg rd , , , J. Funder , , , J.B. Nielsen , , , 等 . . Superposition attacks on cryptographic protocols . . LNCS , , 2014 . . 8317 142 - - 161 . . DOI: 10.1007/978-3-319-04268-8_9 http://doi.org/10.1007/978-3-319-04268-8_9 . .

S. Even , , , O. Goldreich , , , A. Lempel . . A randomized protocol for signing contracts . . Commun. ACM , , 1985 . . 28 ( ( 6 ): ): 637 - - 647 . . DOI: 10.1145/3812.3818 http://doi.org/10.1145/3812.3818 . .

S. Fehr , , , J. Katz , , , F. Song , , , 等 . . Feasibility and completeness of cryptographic tasks in the quantum world . . LNCS , , 2013 . . 7785 281 - - 296 . . DOI: 10.1007/978-3-642-36594-2_16 http://doi.org/10.1007/978-3-642-36594-2_16 . .

C. Gentry , , , C. Peikert , , , V. Vaikuntanathan . . Trapdoors for hard lattices and new cryptographic constructions . . Proc. 40th Annual ACM Symp. on Theory of Computing , , 2008 . . p.197 - - 206 . . DOI: 10.1145/1374376.1374407 http://doi.org/10.1145/1374376.1374407 . .

N. Gilboa . . Two party RSA key generation . . LNCS , , 1999 . . 1666 116 - - 129 . . DOI: 10.1007/3-540-48405-1_8 http://doi.org/10.1007/3-540-48405-1_8 . .

S. Hallgren , , , A. Smith , , , F. Song . . Classical cryptographic protocols in a quantum world . . LNCS , , 2011 . . 6841 411 - - 428 . . DOI: 10.1007/978-3-642-22792-9_23 http://doi.org/10.1007/978-3-642-22792-9_23 . .

S. Hallgren , , , A. Smith , , , F. Song . . Classical cryptographic protocols in a quantum world . . Cryptology ePrint Archive , , 2015 . . 2015/687 http://eprint.iacr.org/2015/687 http://eprint.iacr.org/2015/687 , , . .

Y. Ishai , , , J. Kilian , , , K. Nissim , , , 等 . . Extending oblivious transfers efficiently . . LNCS , , 2003 . . 2729 145 - - 161 . . DOI: 10.1007/978-3-540-45146-4_9 http://doi.org/10.1007/978-3-540-45146-4_9 . .

R.W.F. Lai , , , H.K.F. Cheung , , , S.S.M. Chow . . Trapdoors for ideal lattices with applications . . LNCS , , 2014 . . 8957 239 - - 256 . . DOI: 10.1007/978-3-319-16745-9_14 http://doi.org/10.1007/978-3-319-16745-9_14 . .

V. Lyubashevsky , , , C. Peikert , , , O. Regev . . On ideal lattices and learning with errors over rings . . J. ACM , , 2013 . . 60 ( ( 6 ): ): 43 DOI: 10.1145/2535925 http://doi.org/10.1145/2535925 . .

D. Micciancio , , , O. Regev . . Lattice-based cryptography. I n: Bernstein D.J., Buchmann J., Dahmen, E. (Eds.), Post-Quantum Cryptography . . Springer, Berlin , , 2009 . . p.147 - - 191 . . DOI: 10.1007/978-3-540-88702-7_5 http://doi.org/10.1007/978-3-540-88702-7_5 . .

M.A. Nielsen , , , I.L. Chuang . . Quantum Computation and Quantum Information , , : : Cambridge Cambridge University Press , , 2010 . . .

C. Peikert . . Some recent progress in lattice-based cryptography . . LNCS , , 2010 . . 5444 72 DOI: 10.1007/978-3-642-00457-5_5 http://doi.org/10.1007/978-3-642-00457-5_5 . .

C. Peikert , , , V. Vaikuntanathan , , , B. Waters . . A framework for efficient and composable oblivious transfer . . LNCS , , 2008 . . 5157 554 - - 571 . . DOI: 10.1007/978-3-540-85174-5_31 http://doi.org/10.1007/978-3-540-85174-5_31 . .

M.O. Rabin . . How to Exchange Secrets with Oblivious Transfer . . Technical Report No. TR-81, Aiken Computation Lab, Harvard University, Cambridge, MA. , , 1981 . . http://eprint.iacr.org/2005/187 http://eprint.iacr.org/2005/187 , , . .

O. Regev . . On lattices, learning with errors, random linear codes, and cryptography . . Proc. 37th Annual ACM Symp. on Theory of Computing , , 2005 . . p.84 - - 93 . . DOI: 10.1145/1060590.1060603 http://doi.org/10.1145/1060590.1060603 . .

N. Sendrier . . Code-based cryptography. In : van Tilborg H.C.A., Jajodia, S. (Eds.), Encyclopedia of Cryptography and Security . . Springer, New York , , 2011 . . p.215 - - 216 . . DOI: 10.1007/978-1-4419-5906-5_378 http://doi.org/10.1007/978-1-4419-5906-5_378 . .

P.W. Shor . . Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer . . SIAM J. Comput. , , 1997 . . 26 ( ( 5 ): ): 1484 - - 1509 . . DOI: 10.1137/S0097539795293172 http://doi.org/10.1137/S0097539795293172 . .

F. Song . . A note on quantum security for post-quantum cryptography . . LNCS , , 2014 . . 8772 246 - - 265 . . DOI: 10.1007/978-3-319-11659-4_15 http://doi.org/10.1007/978-3-319-11659-4_15 . .

D. Unruh . . Universally composable quantum multiparty computation . . LNCS , , 2010 . . 6110 486 - - 505 . . DOI: 10.1007/978-3-642-13190-5_25 http://doi.org/10.1007/978-3-642-13190-5_25 . .

D. Unruh . . Quantum proofs of knowledge . . LNCS , , 2012 . . 7237 135 - - 152 . . DOI: 10.1007/978-3-642-29011-4_10 http://doi.org/10.1007/978-3-642-29011-4_10 . .

J. Watrous . . Zero-knowledge against quantum attacks . . SIAM J. Comput. , , 2009 . . 39 ( ( 1 ): ): 25 - - 58 . . DOI: 10.1137/060670997 http://doi.org/10.1137/060670997 . .

M. Zhandry . . How to construct quantum random functions . . IEEE 53rd Annual Symp. on Foundations of Computer Science , , 2012 . . p.679 - - 687 . . DOI: 10.1109/FOCS.2012.37 http://doi.org/10.1109/FOCS.2012.37 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰