Paper 2016/913

Small Field Attack, and Revisiting RLWE-Based Authenticated Key Exchange from Eurocrypt'15

Boru Gong and Yunlei Zhao

Abstract

Authenticated key-exchange (AKE) plays a fundamental role in modern cryptography. Up to now, the HMQV protocol family is among the most efficient provably secure AKE protocols, which has been widely standardized and in use. Given recent advances in quantum computing, it would be highly desirable to develop lattice-based HMQV-analogue protocols for the possible upcoming post-quantum era. Towards this goal, an important step is recently made by Zhang et al. at Eurocrypt'15. Similar to HMQV, the HMQV-analogue protocols proposed there consists of two variants: a two-pass protocol $\Pi_2$, as well as a one-pass protocol $\Pi_1$ that implies, in turn, a signcryption scheme (named as "deniable encryption"). All these protocols are claimed to be provably secure under the ring-LWE (RLWE) assumption. In this work, we propose a new type of attack, referred to as small field attack (SFA), against the one-pass protocol $\Pi_1$, as well as its resultant deniable encryption scheme. With SFA, a malicious user can efficiently recover the static private key of the honest victim user in $\Pi_1$ with overwhelming probability. Moreover, the SFA attack is realistic and powerful in practice, in the sense that it is almost impossible for the honest user to prevent, or even detect, the attack. Besides, some new property regarding the CRT basis of $R_q$ is also developed in this work, which is essential for our small field attack and may be of independent interest. The security proof of the two-pass protocol $\Pi_2$ is then revisited. We are stuck at Claim 16 in [ZZDS14], with a gap identified and discussed in the security proof. To us, we do not know how to fix the gap, which traces back to some critical differences between the security proof of HMQV and that of its RLWE-based analogue.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. PQCrypto 2017, to appear
Keywords
small field attackauthenticated key exchangering-LWEideal latticeCRT basis
Contact author(s)
ylzhao @ fudan edu cn
History
2017-04-18: last of 6 revisions
2016-09-19: received
See all versions
Short URL
https://ia.cr/2016/913
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/913,
      author = {Boru Gong and Yunlei Zhao},
      title = {Small Field Attack, and Revisiting RLWE-Based Authenticated Key Exchange from Eurocrypt'15},
      howpublished = {Cryptology ePrint Archive, Paper 2016/913},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/913}},
      url = {https://eprint.iacr.org/2016/913}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.