MathSciDoc: An Archive for Mathematician ∫

Authenticated Key Exchange (AKE) is a cryptographic scheme with the aim to establish a high-entropy and secret session key over a insecure communications network. Password-Authenticated Key Exchange (PAKE) assumes that the parties in play share a simple password, which is cheap and human-memorable and is used to achieve the authentication. PAKEs are practically relevant as these features are extremely appealing in an age where most people access sensitive personal data remotely from more-and-more pervasive hand-held devices. Theoretically, PAKEs allow the secure computation and authentication of a high-entropy piece of data using a low-entropy string as a starting point. In this paper, we apply the recently proposed technique introduced in [19] to construct two lattice-based PAKE protocols enjoying a very simple and elegant design that is an parallel extension of the class of Random Oracle Model (ROM)-based protocols PAK and PPK [13, 41], but in the lattice-based setting. The new protocol resembling PAK is three-pass, and provides mutual explicit authentication, while the protocol following the structure of PPK is two-pass, and provides implicit authentication. Our protocols rely on the Ring-Learning-with-Errors (RLWE) assumption, and exploit the additive structure of the underlying ring. They have a comparable level of efficiency to PAK and PPK, which makes them highly attractive. We present a preliminary implementation of our protocols to demonstrate that they are both efficient and practical. We believe they are suitable quantum safe replacements for PAK and PPK.

Secure Remote Password (SRP) protocol is an augmented Password-based Authenticated Key Exchange (PAKE) protocol based on discrete logarithm problem (DLP) with various attractive security features. Compared with basic PAKE protocols, SRP does not require server to store user’s password and user does not send password to server to authenticate. These features are desirable for secure client-server applications. SRP has gained extensive real-world deployment, including Apple iCloud, 1Password etc. However, with the advent of quantum computer and Shor’s algorithm, classic DLP-based public key cryptography algorithms are no longer secure, including SRP. Motivated by importance of SRP and threat from quantum attacks, we propose a RLWE-based SRP protocol (RLWE-SRP) which inherit advantages from SRP and elegant design from RLWE key exchange. We also present parameter choice and efficient portable C++ implementation of RLWE-SRP. Implementation of our 209-bit secure RLWE-SRP is more than 3x faster than 112-bit secure original SRP protocol, 5.5x faster than 80-bit secure J-PAKE and 14x faster than two 184-bit secure RLWE-based PAKE protocols with more desired properties.

A review of the current state of multivariate public-key cryptosystems compares and contrasts the most promising multivariate schemes in digital signatures and public-key encryption as well as their security.

The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.

Key Exchange (KE) from RLWE (Ring-Learning with Errors) is a potential alternative to Diffie-Hellman (DH) in a post quantum setting. Key leakage with RLWE key exchange protocols in the context of key reuse has already been pointed out in previous work. The initial attack described by Fluhrer is designed in such a way that it only works on Peikert’s KE protocol and its variants that derives the shared secret from the most significant bits of the approximately equal keys computed by both parties. It does not work on Ding’s key exchange that uses the least significant bits to derive a shared key. The Signal leakage attack relies on changes in the signal sent by the responder reusing his key, in a sequence of key exchange sessions initiated by an attacker with a malformed key. A possible defense against this attack would be to require the initiator of a key exchange to send the signal, which is the one pass case of the KE protocol. In this work, we describe a new attack on Ding’s one pass case without relying on the signal function output but using only the information of whether the final key of both parties agree. We also use LLL reduction to create the adversary’s keys in such a way that the party being compromised cannot identify the attack in trivial ways. This completes the series of attacks on RLWE key exchange with key reuse for all variants in both cases of the initiator and responder sending the signal. Moreover, we show that the previous Signal leakage attack can be made more efficient with fewer queries and how it can be extended to Peikert’s key exchange, which was used in the BCNS implementation and integrated with TLS and a variant used in the New Hope implementation.

Ring Learning With Errors (RLWE)-based key exchange is one of the most efficient and secure primitive for post-quantum cryptography. One common approach to achieve key exchange over RLWE is error reconciliation. Recently, an efficient attack against reconciliation-based RLWE key exchange protocols with reused keys was proposed. This attack can recover a long-term private key if a key pair is reused. We also know that in the real world, key reuse is commonly adopted in applications like the Transport Layer Security (TLS) protocol to improve performance. Directly motivated by this attack, we construct a new randomized RLWE-based key exchange protocol against this attack. Our lightweight approach incorporates an additional ephemeral public error term into key exchange materials, so that this attack no longer works. With the same attack, we practically show that the signal value of our protocol is indistinguishable from uniform random, therefore, this attack no longer works. We explain how the attack fails, present 200-bit classic and 80-bit quantum secure parameter choice, efficient implementations, comparisons and discussion. Benchmark shows our protocol is truly efficient and even faster than related vulnerable protocols.

Two post-quantum password-based authenticated key exchange (PAKE) protocols were proposed at CTRSA 2017. Following this work, we give much more efficient and portable C++ implementation of these two protocols. We also choose more compact parameters providing 200-bit security. Compared with original implementation, we achieve 21.5x and 18.5x speedup for RLWE-PAK and RLWE-PPK respectively. Compare with quantum-vulnerable J-PAKE protocol, we achieve nearly 8x speedup. We also integrate RLWE-PPK into TLS to construct a post-quantum TLS ciphersuite. This allows simpler key management, mutual authentication and resistant to phishing attack. Benchmark shows that our ciphersuite is indeed practical

Oblivious transfer is one of the main pillars of modern cryptography and plays a major role as a building block for other more complex cryptographic primitives. In this work, we present an efficient and versatile framework for oblivious transfer (OT) using one-round key-exchange (ORKE), a special class of key exchange (KE) where only one message is sent from each party to the other. Our contributions can be summarized as follows: - We analyze carefully ORKE schemes and introduce new security definitions. Namely, we introduce a new class of ORKE schemes, called Alice-Bob one-round key-exchange (A-B ORKE), and the definitions of message and key indistinguishability. - We show that OT can be obtained from A-B ORKE schemes fulfilling message and key indistinguishability. We accomplish this by designing a new efficient, versatile and universally composable framework for OT in the Random Oracle Model (ROM). The efficiency of the framework presented depends almost exclusively on the efficiency of the A-B ORKE scheme used since all other operations are linear in the security parameter. Universally composable OT schemes in the ROM based on new hardness assumptions can be obtained from instantiating our framework. Examples are presented using the classical Diffie-Hellman KE, RLWE-based KE and Supersingular Isogeny Diffie-Hellman KE.

In CT-RSA 2019, Bauer et al. have analyzed the case when the public key is reused for the NewHope key encapsulation mechanism (KEM), a second-round candidate in the NIST Post-quantum Standard process. They proposed an elegant method to recover coefficients ranging from −6 to 4 in the secret key. We repeat their experiments but there are two fundamental problems. First, even for coefficients in [−6, 4] we cannot recover at least 262 of them in each secret key with 1024 coefficients. Second, for the coefficient outside [−6, 4], they suggested an exhaustive search. But for each secret key on average there are 10 coefficients that need to be exhaustively searched, and each of them has 6 possibilities. This makes Bauer et al.’s method highly inefficient. We propose an improved method, which with 99.22% probability recovers all the coefficients ranging from −6 to 4 in the secret key. Then, inspired by Ding et al.’s key mismatch attack, we propose an efficient strategy which with a probability of 96.88% succeeds in recovering all the coefficients in the secret key. Experiments show that our proposed method is very efficient, which completes the attack in about 137.56 ms using the NewHope parameters.

Short integer solution (SIS) and learning with errors (LWE) are two hard lattice problems. These two problems are believed having huge potential in application of cryptography. In 2012, Ding et al. [5] introduced the first provably secure key exchange based on LWE problem. On the other hand, we believe that it is very difficult to do key exchange on SIS problem only. In 2014, Wang et al. [6] did an attempt, but it was not successful. Mao et al. [7] broke the protocol by an attack based on CBi-SIS problem in 2016. However, their attack is not efficient. In this paper, we present a extremely straightforward and simple attack to Wang’s key exchange and then we will construct a key exchange based on SIS and LWE problems.