In 1998, Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman introduced the famous NTRU cryptosystem, and called it "A ring-based public key cryptosystem". Actually, it turns out to be a lattice based cryptosystem that is resistant to Shor's algorithm. There are several modifications to the original NTRU and two of them are selected as round 2 candidates of NIST post quantum public key scheme standardization. In this paper, we present a simple attack on the original NTRU scheme. The idea comes from Ding et al.'s key mismatch attack. Essentially, an adversary can find information on the private key of a KEM by not encrypting a message as intended but in a manner which will cause a failure in decryption if the private key is in a certain form. In the present, NTRU has the encrypter generating a random polynomial with "small" coefficients, but we will have the coefficients be "large". After this, some further work will create an equivalent key.

Kyber is a KEM based their security on the Modular Learning with Errors problem and was selected in the second round of NIST Post-quantum standardization process. Before we put Kyber into practical application, it is very important to assess its security in hard practical conditions especially when the Fujisaki-Okamoto transformations are neglected. In this paper, we propose an efficient key mismatch attacks on Kyber, which can recover one participant's secret key if the public key is reused. We first define the oracles in which the adversary is able to launch the attacks. Then, we show that by accessing the oracle multiple times, the adversary is able to recover the coefficients in the secret key. Furthermore, we propose two strategies to reduce the queries and time in recovering the secret key. It turns out that it is actually much easier to use key mismatch attacks to break Kyber than NewHope, another NIST second round candidate, due to their different design structures. Our implementations have demonstrated the efficiency of the proposed attacks and verified our findings. Another interesting observation from the attack is that in the most powerful Kyber-1024, it is easier to recover each coefficient compared with that in Kyber-512 and Kyber-768. Specifically, for Kyber-512 on average we recover each coefficient with 2.7 queries, while in Kyber-1024 and 768, we only need 2.4 queries. This demonstrates further that implementations of LWE based schemes in practice is very delicate.

The aim of the present paper is to suggest that statistical physics provides the correct language to understand the practical behavior of the LLL algorithm, most of which are left unexplained to this day. To this end, we propose sandpile models that imitate LLL with compelling accuracy, and prove for these models some of the most desired statements regarding LLL. We also formulate a few conjectures that formally capture our heuristics and would serve as milestones for further development of the theory.

We use the signal function from RLWE key exchange to derive an efficient zero knowledge authentication protocol to validate an RLWE key p=as+e with secret s and error e in the Random Oracle Model (ROM). With this protocol, a verifier can validate that a key presented to him by a prover P is of the form p=as+e with s,e small and that the prover knows s. We accompany the description of the protocol with proof to show that it has negligible soundness and completeness error. The soundness of our protocol relies directly on the hardness of the RLWE problem. The protocol is applicable for both LWE and RLWE but we focus on the RLWE based protocol for efficiency and practicality. We also present a variant of the main protocol with a commitment scheme to avoid using the ROM.

We use an RLWE-based key exchange scheme to construct a simple and efficient post-quantum oblivious transfer based on the Ring Learning with Errors assumption. We prove that our protocol is secure in the Universal Composability framework against static malicious adversaries in the random oracle model. The main idea of the protocol is that the receiver and the sender interact using the RLWE-based key exchange in such a way that the sender computes two keys, one of them shared with the receiver. It is infeasible for the sender to know which is the shared key and for the receiver to get information about the other one. The sender encrypts each message with each key using a symmetric-key encryption scheme and the receiver can only decrypt one of the ciphertexts. The protocol is extremely efficient in terms of computational and communication complexity, and thus a strong candidate for post-quantum applications.

In this paper we show how to totally break the fully homomorphic encryption scheme of eprint 2017/458.

Error reconciliation is an important technique for learning with error (LWE) and ring-LWE (RLWE)-based constructions. In this paper, we present a comparison analysis on two error reconciliation-based RLWE key exchange protocols: Ding et al. in 2012 (DING12) and Bos et al. in 2015 (BCNS15). We take them as examples to explain the core idea of error reconciliation, building key exchange over RLWE problem, implementation and real-world performance, and compare them comprehensively. We also analyse a LWE key exchange 'Frodo' that uses an improved error reconciliation mechanism in BCNS15. To the best of our knowledge, our work is the first to present at least 128-bit classic (80-bit quantum) and 256-bit classic (> 200-bit quantum) secure parameter choices for DING12 with efficient portable C/C++ implementations. Benchmark shows that our efficient implementation is 11× faster than BCNS15 and one key exchange execution only costs 0.07 ms on a four-year-old middle range CPU. Error reconciliation is 1.57× faster than BCNS15.

The SimpleMatrix encryption scheme as proposed by Tao et al. \cite{TD13} is one of the very few existing approaches to create a secure and efficient encryption scheme on the basis of multivariate polynomials. However, in its basic version, decryption failures occur with non-negligible probability. Although this problem has been addressed in several papers \cite{DP14,TX15}, a general solution to it is still missing. In this paper we propose an improved version of the SimpleMatrix scheme, which eliminates decryption failures completely and therefore solves the biggest problem of the SimpleMatrix encryption scheme. Additionally, we propose a second version of the scheme, which reduces the blow-up factor between plain and ciphertext size to a value arbitrary close to 1.

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. \emph{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~\cite{DXX2012} 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 \msf{PAK} and \msf{PPK}~\cite{BMP2000,M2002}, but in the lattice-based setting. The new protocol resembling \msf{PAK} is three-pass, and provides \emph{mutual explicit authentication}, while the protocol following the structure of \msf{PPK} is two-pass, and provides \emph{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 \msf{PAK} and \msf{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 \msf{PAK} and \msf{PPK}.

In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key exchange protocols that use extensions by endomorpisms of matrices over a Galois field proposed in \cite{Kahrobaei-Lam-Shpilrain:2014}. We show that both protocols are vulnerable to a simple linear algebra attack.