Small Field Attack, and Revisiting RLWE-Based Authenticated Key Exchange from Eurocrypt'15
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 analogue of HMQV protocols for the possible upcoming post-quantum era. Towards this goal, an important step was recently made by Zhang et al. at Eurocrypt’15 [ZZD+15,ZZDS14]. Similar to HMQV, this ring-LWE based analogue of HMQV proposed there consist of two variants: a two-pass protocol Π2, as well as a one-pass protocol Π1 that implies a signcryption scheme (named as “deniable encryption” in [ZZD+15]). 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 Π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 Π1 with overwhelming probability. Moreover, the SFA attack is realistic and powerful in practice, in the sense that it is hard in practice for the honest victim party to prevent, or even detect, the attack. Besides, some new property regarding the CRT basis forRq 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 Π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.