We present the No IC Encryption (NICE)-PAKE, a (semi)-generic symmetric Password Authenticated Key Exchange (PAKE) framework providing a quantum-safe alternative for the Ideal Cipher (IC), utilizing simpler cryptographic components for the authentication step. To give a formal proof, we introduce the notions of A-Part Secrecy (A-SEC-CCA), Splittable Collision Freeness (A-CFR-CCA) and Public Key Uniformity (SPLIT-PKU) for splittable LWE KEMs. We show the relation of the former to the Non-uniform LWE and the Weak-Hint LWE assumptions, as well as its application to Ring and Module LWE. Finally, we show how to obtain a secure PAKE from our construction with concrete parameter choices for lattice KEMs.
We present the No IC Encryption (NICE)-PAKE, a (semi)-generic symmetric Password Authenticated Key Exchange (PAKE) framework providing a quantum-safe alternative for the Ideal Cipher (IC), utilizing simpler cryptographic components for the authentication step. To give a formal proof, we introduce the notions of A-Part Secrecy (A-SEC-CCA), Splittable Collision Freeness (A-CFR-CCA) and Public Key Uniformity (SPLIT-PKU) for splittable LWE KEMs. We show the relation of the former to the Non-uniform LWE and the Weak-Hint LWE assumptions, as well as its application to Ring and Module LWE. Finally, we show how to obtain a secure PAKE from our construction with concrete parameter choices for lattice KEMs.
Password-based authenticated key exchange (PAKE) allows participants sharing low-entropy passwords to agree on cryptographically strong session keys over insecure networks. In this paper, we present two PAKE protocols from lattices in the two-party and three-party settings, respectively, which can resist quantum attacks and achieve mutual authentication. The protocols in this paper achieve two rounds of communication by carefully utilizing the splittable properties of the underlying primitive, a CCA (Chosen-Ciphertext Attack)-secure public key encryption (PKE) scheme with associated nonadaptive approximate smooth projection hash (NA-ASPH) system. Compared with other related protocols, the proposed two-round PAKE protocols have relatively less communication and computation overhead. In particular, the two-round 3PAKE is more practical in large-scale communication systems.
The Password-Authenticated Key Exchange (PAKE) protocol is a useful tool for establishing secure remote communication between users, especially given the prevalence of amplifying a human-memorable password into a strong session key in the age of hand-held devices. Recent advances in quantum computing have stimulated interest in quantum-safe cryptographic schemes. Therefore, we propose QSPAK and QSPPK, two post-quantum and efficient PAKE protocols which are parallel extensions of PAK and PPK, but based on the hardness assumption over module lattices. Specifically, we make a comprehensive trade-off among multiple significant performance indicators such as the post-quantum security, the failure rate, the communication cost and the running time to guide optimal parameter choices. This rigorous instantiation has never been seen in previous PAKE papers. Additionally, utilizing the flexibility of module lattices, we provide three parameter sets (#1, #2, and #3) matching different security scenarios. We implement and benchmark QSPAK and QSPPK against other competitive proposals. The performance results indicate that our QSPAK and QSPPK, besides being more efficient, exhibit the flexibility and security advantages over the latter schemes. Furthermore, we construct a post-quantum password-authenticated TLS 1.3 framework, aimed towards provide a further suggestion for IETF standardization of quantum-safe PAKE.
Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S\&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient methods for compiling essentially any KEM into advanced cryptographic protocols, namely password-authenticated key exchange (PAKE) and oblivious transfer (OT), by relying only on idealized symmetric-key primitives. They have become leading candidates for practically-implementable PAKE and OT due to (1) their simplicity, (2) their plug-and-play nature, allowing for flexibility in the choice of KEM, and (3) existing proofs of UC-security (in the classical adversarial model).
Due to point (2) above, these compilers yield attractive candidates for efficient \emph{post-quantum} PAKE and OT, especially given the recent post-quantum KEM standardization efforts. This motivates the question of whether the (UC-)security of these compilers translates to the quantum adversarial model. In this work, we show that it does not. In particular, we prove that a general family of (O)EKE protocols, as well as Masny-Rindal OT, are \emph{not} UC-secure against quantum polynomial-time adversaries, even when instantiated with a post-quantum KEM. To establish UC-insecurity, we devise an adversarial strategy that provably thwarts any attempt by the simulator to extract its input (the password in the case of PAKE, and the receiver's choice bit in the case of OT).
To complement these negative results, we establish that both compilers yield certain notions of \emph{game-based} security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.
Password authentication is a prevalent method of user verification across the Internet, and its use extends to scenarios where resources are limited. However, current password authentication protocols primarily rely on traditional password authenticated key exchange (PAKE) protocols (e.g., SRP, OPAQUE), which are vulnerable to attacks by quantum adversaries. To date, no efficient quantum algorithm has been found to solve the common challenges in lattice-based cryptography. Therefore, quantum-resistant PAKE protocols are generally built upon lattice-based cryptography. In this work, we propose a threshold verifiable oblivious pseudorandom function () protocol based on secret sharing. We then integrate it into a PAKE protocol and present an instantiation of a quantum-safe threshold PAKE protocol () based on the Ring Learning with Errors (RLWE) assumption. This integration gives our PAKE protocol resistance to precomputation attacks, similar to OPAQUE. Furthermore, by incorporating thresholding techniques into the PAKE protocol, we mitigate the risk of single points of failure on the server side. Our protocol not only preserves the security guarantees of traditional PAKE schemes but also resists attacks from quantum adversaries. We also provide a comprehensive security analysis and evaluation of, providing valuable insights for its practical implementation.
Driven by advances in the standardization of NIST’s Post-Quantum Cryptography (PQC) algorithms, research on constructing Password Authenticated Key Exchange (PAKE) protocols using Key Encapsulation Mechanisms (KEMs) has gained considerable attention. Several PAKE protocols have established precise security requirements for the underlying KEM. Arriaga et al. introduced a PAKE protocol called CHIC, which requires the KEM to achieve anonymity under plaintext-checkable attacks (ANO-1PCA). An anonymous KEM does not leak any information about which public key was used for encryption. It protects the identities and privacy of participants and is critical in preventing identity-guessing attacks, therefore, anonymity is also called key-privacy. The anonymity of NIST PQC Round-3 candidates has recently been analyzed, some of which satisfied ANO-CCA.Huguenin-Dumittan and Vaudenay proposed two efficient constructions, TCHand TH, to create KEM from public-key encryption (PKE) schemes. Jiang et al. introduced TRHbased on TH. These constructions can transform any OW-CPA PKE into an IND-qCCA KEM efficiently and avoid re-encryption. However, prior to this work, no research has been conducted to determine whether these constructions preserve or lift anonymity.In this paper, we proved that for any OW-CPA, DS-IND PKE, the construction KEMRH= TRH[PKE,H] achieves ANO1-CCA in the quantum random oracle model (QROM). We then construct a KEM called KyberRH, and provide an algorithm for the CHIC protocol using KyberRH.
An approximate smooth projective hash(ASPH) function is an important primitive of the lattice-based cryptography,and it is used to construct password-based authenticated key exchange(PAKE) protocol which is resistant to quantum attacks by Katz et al.The available ASPH function based on the hardness of the standard lattice problem has a large key size and impractical implementations.Based on learning with error problem from ideal lattices(R-LWE),this paper designs a new public-key encryption scheme and an associated ASPH function that can apply to PAKE protocol,and gives a proof of its security.Compared with the existing system,the new system has a small key size,fast computing speed and high efficiency.