Isogeny-Based Password-Authenticated Key Exchange Based on Shuffle Algorithm
摘要
At CRYPTO 2022, Abdalla et al. incorporate the ability to compute the quadratic twist of elliptic curves to extend the framework of group actions introduced by Alamati et al. (ASIACRYPT 2020), and proposed two password-authenticated key exchange (PAKE) protocols. Their first protocol \(\textsf{X}\) - \(\textsf{GA}\) - \(\textsf{PAKE}_\ell \) is a provably secure one-round isogeny-based scheme with a password length of \(\ell \) , which improves security by increasing computation and communication overhead. In \(\textsf{X}\) - \(\textsf{GA}\) - \(\textsf{PAKE}_\ell \) , each party needs to choose \(2 \ell \) elements and perform \(5 \ell \) group actions. In this paper, we present an isogeny-based PAKE protocol that is more efficient than \(\textsf{X}\) - \(\textsf{GA}\) - \(\textsf{PAKE}_\ell \) . In our scheme, we reduce the number of set elements to \(\ell \) , thus the overhead of communication between users and servers is significantly decreased. By using the shuffle algorithm, the number of group actions that each party needs to perform is reduced to \(2\ell \) , but our protocol can still prevent trivial attacks using twists. Due to the use of Merkle root and password in the shuffle function, the attackers cannot select a message from the received message. Also, the length of the message used for key derivation is reduced from \(3\ell \) to \(\ell \) . We prove the security based on the security assumption in the isogeny-based setting.