Key exchange protocols from the learning with errors (LWE) problem share many similarities with the Diffie–Hellman–Merkle (DHM) protocol, which plays a central role in securing our Internet. Therefore, there has been a long time effort in designing authenticated key exchange directly from LWE to mirror the advantages of DHM-based protocols. In this paper, we revisit signal leakage attacks and show that the severity of these attacks against LWE-based (authenticated) key exchange is still underestimated. In particular, by converting the problem of launching a signal leakage attack into a coding problem, we can significantly reduce the needed number of queries to reveal the secret key. Specifically, for DXL-KE we reduce the queries from 1,266 to only 29, while for DBS-KE, we need only 748 queries, a great improvement over the previous 1,074,434 queries. Moreover, our new view of signals as binary codes enables recognizing vulnerable schemes more easily. As such we completely recover the secret key of a password-based authenticated key exchange scheme by Dabra et al. with only 757 queries and partially reveal the secret used in a two-factor authentication by Wang et al. with only one query. The experimental evaluation supports our theoretical analysis and demonstrates the efficiency and effectiveness of our attacks. Our results caution against underestimating the power of signal leakage attacks as they are applicable even in settings with a very restricted number of interactions between adversary and victim.

Lattice problem such as NTRU problem and LWE problem is widely used as the security base of post-quantum cryptosystems. And currently doing lattice reduction by BKZ algorithm is the most efficient way to solve it. In this paper, we give several further improvements on BKZ algorithm, which can be used for different SVP subroutines base on both enumeration and sieving. These improvements in combination provide a speed up of 2^{3~4} in total. It is significant in concrete attacks. Using these new techniques, we solved the 656 dimensional ideal lattice challenge in only 380 thread hours (also with a enumeration based SVP subroutine), much less than the previous records (which costs 4600 thread hours in total). With these improvements enabled, we can still simulate the new BKZ algorithm easily. One can also use this simulator to find the blocksize strategy (and the corresponding cost) to make Pot of the basis (defined in section 5.2) decrease as fast as possible, which means the length of the first basis vector decrease the fastest if we accept the GSA assumption. It is useful for analyzing concrete attacks on lattice-based cryptography.

Often times, the ability to distinguish between random data and a public key can leads to an attack against the cryptosystem itself. In this paper, we will show experimentally a very efficient distinguisher based on the distribution of ranks of the symmetric matrices associated with the central map in the multivariate cryptosystem HFE when the degree D of the central map is very small.

Our purpose is to compare how much the F5 algorithm can gain in efficiency compared to the F4 algorithm. This can be achieve as the F5 algorithm uses the concept of signatures to foresee potential useless computation which the F4 algorithm might make represented by zero rows in the reduction of a large matrix. We experimentally show that this is a modest increase in efficiency for the parameters we tested.

In 2017, Ward Beullenset al.submitted Lifted Unbalanced Oil andVinegar, which is a modification to the Unbalanced Oil and Vinegar Schemeby Patarin. Previously, Dinget al.proposed the Subfield Differential Attack which prompted a change of parameters by the authors of LUOV for the sec-ond round of the NIST post quantum standardization competition. In this paper we propose a modification to the Subfield Differential Attack called the Nested Subset Differential Attack which fully breaks half of the pa-rameter sets put forward. We also show by experimentation that this attack ispractically possible to do in under 210 minutes for the level I security param-eters and not just a theoretical attack. The Nested Subset Differential attack isa large improvement of the Subfield differential attack which can be used inreal world circumstances. Moreover, we will only use what is called the "lifted"structure of LUOV, and our attack can be thought as a development of solving"lifted" quadratic systems.

Anonymous veto networks (AV-nets), originally proposed by Hao and Zielinski (2006), are particularly lightweight protocols for evaluating a veto function in a peer-to-peer network such that anonymity of all protocol participants is preserved. Prior to this work, anonymity in all AV-nets from the literature relied on the decisional Diffie-Hellman (DDH) assumption and can thus be broken by (scalable) quantum computers. In order to defend against this threat, we propose two practical and completely lattice-based AV-nets. The first one is secure against passive and the second one is secure against active adversaries. We prove that anonymity of our AV-nets reduces to the ring learning with errors (RLWE) assumption. As such, our AV-nets are the first ones with post-quantum anonymity. We also provide performance benchmarks to demonstrate their practicality.

The HFEv- signature scheme is a twenty year old multivariate public key signature scheme. It uses the Minus and the Vinegar modifier on the original HFE scheme. An instance of the HFEv- signature scheme called GeMSS is one of the alternative candidates for signature schemes in the third round of the NIST Post Quantum Crypto (PQC) Standardization Project. In this paper, we propose a new key recovery attack on the HFEv- signature scheme. We show that the Minus modification does not enhance the security of cryptosystems of the HFE family, while the Vinegar modification increases the complexity of our attack only by a polynomial factor. By doing so, we show that the proposed parameters of the GeMSS scheme are not as secure as claimed. Our attack shows that it is very difficult to build a secure and efficient signature scheme on the basis of HFEv-.

In this paper, we present a simple attack on LWE and Ring LWE encryption schemes used directly as Key Encapsulation Mechanisms (KEMs). This attack could work due to the fact that a key mismatch in a KEM is accessible to an adversary. Our method clearly indicates that any LWE or RLWE (or any similar type of construction) encryption directly used as KEM can be broken by modifying our attack method according to the respective cases.

Key Exchange (KE) is, undoubtedly, one of the most used cryptographic primitives in practice. Its authenticated version, Authenticated Key Exchange (AKE), avoids man-in-the-middle-based attacks by providing authentication for both parties involved. It is widely used on the Internet, in protocols such as TLS or SSH. In this work, we provide new constructions for KE and AKE based on ideal lattices in the Random Oracle Model (ROM). The contributions of this work can be summarized as follows: 1) It is well-known that RLWE-based KE protocols are not robust for key reuses since the signal function leaks information about the secret key. We modify the design of previous RLWE-based KE schemes to allow key reuse in the ROM. Our construction makes use of a new technique called pasteurization which enforces a supposedly RLWE sample sent by the other party to be indeed indistinguishable from a uniform sample and, therefore, ensures no information leakage in the whole KE process. 2) We build a new AKE scheme based on the construction above. The scheme provides implicit authentication (that is, it does not require the use of any other authentication mechanism, like a signature scheme) and it is proven secure in the Bellare-Rogaway model with weak Perfect Forward Secrecy in the ROM. It improves previous designs for AKE schemes based on lattices in several aspects. Our construction just requires sampling from only one discrete Gaussian distribution and avoids rejection sampling and noise flooding techniques, unlike previous proposals (Zhang et al., EUROCRYPT 2015). Thus, the scheme is much more efficient than previous constructions in terms of computational and communication complexity. Since our constructions are provably secure assuming the hardness of the RLWE problem, they are considered to be robust against quantum adversaries and, thus, suitable for post-quantum applications.

Homomorphic Encryption is a breakthrough technology which can enable private cloud storage and computation solutions, and many applications have been described in the literature in the last few years. But before Homomorphic Encryption can be adopted in medical, health, and financial sectors to protect data and patient and consumer privacy, it will have to be standardized, most likely by multiple standardization bodies and government agencies. An important part of standardization is broad agreement on security levels for varying parameter sets. Although extensive research and benchmarking has been done in the research community to establish the foundations for this effort, it is hard to find all the information in one place, along with concrete parameter recommendations for applications and deployment. This document is the first Homomorphic Encryption Standard (HES) approved by the Homomorphicencryption.org community in 2018. It captures the collective knowledge on the state of security of these schemes, specifies the schemes, and recommends a wide selection of parameters to be used for homomorphic encryption at various security levels. We describe known attacks and their estimated running times in order to make these security parameter recommendations.

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.

In this paper, we propose a new algorithm for solving the general approximate common divisors (GACD) problems, which is based on lattice reduction algorithms on certain special lattices and linear equation solving algorithms over integers. Through both theoretical arguments and experimental data, we show that our new algorithm works in polynomial time but under roughly the following condition: \begin{itemize} \item There is a positive integer t such that \frac{\gamma+\eta}{t} + \frac{t}{H} + \rho < \eta; \item We have more than t GACD samples. \end{itemize} or equivalently \begin{itemize} \item H(\eta-\rho)^2 - 4(\gamma+\eta) > 0; \item We have more than t = \lceil\frac{H(\eta-\rho) - \sqrt{H^2(\eta-\rho)^2 - 4H(\gamma+\eta)}{2}\rceil GACD samples. \end{itemize} Here \gamma, \eta and \rho are parameters describing a GACD problem, H = 1/\log_2 F and F is the Hermite Factor. In our experiments, H is shown to be roughly 40 when using the LLL reduction algorithm and it should be around 80 when using Deep or BKZ algorithms. % We use our algorithm to solve concrete problems that no other algorithm could solve before. We show how our algorithm can be applied to attack the fully homomorphic encryption schemes which are based on the general approximate common divisors problem and its limitations.

We present a new method for building pairs of HFE polynomials of high degree, such that the map constructed with such a pair is easy to invert. The inversion is accomplished using a low degree polynomial of Hamming weight three, which is derived from a special reduction via Hamming weight three polynomials produced by these two HFE polynomials. This allows us to build new candidates for multivariate trapdoor functions in which we use the pair of HFE polynomials to fabricate the core map. We performed the security analysis for the case where the base field is GF(2) and showed that these new trapdoor functions have high degrees of regularity, and therefore they are secure against the direct algebraic attack. We also give theoretical arguments to show that these new trapdoor functions over GF(2) are secure against the MinRank attack as well.

In this paper we present a new algorithm to attack lattice based cryptosystems by solving a problem over real numbers. In the case of the NTRU cryptosystem, if we assume the additional information on the modular operations, we can break the NTRU cryptosystems completely by getting the secret key. We believe that this fact was not known before.

We present a generalized learning with errors (LWE) problem, which is essentially a simple and direct extension of the original LWE problem to the case of matrices. Then we use this new version of LWE problem, which we call matrix LWE problem to build new cryptographic schemes, which include a new scalable key distribution scheme, a new key exchanges scheme and a new simple identity-based encryption scheme.

We use the learning with errors (LWE) problem to build a new simple and provably secure key exchange scheme. The basic idea of the construction can be viewed as certain extension of Diffie-Hellman problem with errors. The mathematical structure behind comes from the commutativity of computing a bilinear form in two different ways due to the associativity of the matrix multiplications: (x^t \times A)\times y = x^t \times (A\times y), where x,y are column vectors and A is a square matrix. We show that our new schemes are more efficient in terms of communication and computation complexity compared with key exchange schemes or key transport schemes via encryption schemes based on the LWE problem. Furthermore, we extend our scheme to the ring learning with errors (RLWE) problem, resulting in small key size and better efficiency.