Abstract. We use a variant of learning with errors (LWE) problem, a simple and direct extension of the original LWE problem to the case of a small secret, which we call a small LWE problem (SLWE), to build a new simple and provably secure key exchange scheme. The basic idea behind the construction can be viewed as certain type of bilinear pairing with errors (PE). We build a more efficient implementation of our scheme using a similar LWE problem but solely based on matrices, and we extend our construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem. 1
Abstract. We use a variant of learning with errors (LWE) problem, a simple and direct extension of the original LWE problem to the case of a small secret, which we call a small LWE problem (SLWE), to build a new simple and provably secure key exchange scheme. The basic idea behind the construction can be viewed as certain type of bilinear pairing with errors (PE). We build a more efficient implementation of our scheme using a similar LWE problem but solely based on matrices, and we extend our construction further using the ring LWE problem, where the provable security is based on the hardness of the ring LWE problem. 1
We construct a key exchange scheme with session key security and Alice's privacy, assuming the hardness of "small integer solution" (SIS) problem and "learning with errors" (LWE) problem, which have worst-case to average-case reductions from lattice problems. Our key exchange scheme is the first lattice-based key exchange scheme with provable security. Moreover, our scheme can be modified to be secure under impersonation attack by adding an authentication step, also, it can be modified to be more efficient using a new variant of LWE.
Abstract. In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.
In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.
In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution.Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice.At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems.After presenting the construction of our scheme we prove its security and propose asymptotic parameters.Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise.We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.
Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.
This note describes a key exchange method based on the ring-LWE (RLWE)
assumption. It builds upon several results, including Regev's
landmark quantum reduction from certain worst case lattice problems
(approx. GapSVP and SIVP) to random instances of the search variant of
a particular learning problem (LWE). It also builds on the follow on
work of Lyubashevsky, Peikert and Regev on the average case hardness
of the RLWE search variant for polynomially bounded numbers of RLWE
samples, along with novel applications of automorphism groups in
number fields for a RLWE search to decision reduction (thereby
demonstrating pseudorandomness of RLWE in these number fields).
Subsequently, these results were adopted for the construction of
Diffie-Hellman like key exchange methods by Peikert, and then by
Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who
proposed efficient variants of such protocols. Subsequent work by
Peikert proposed another efficient variant, phrased as a key
encapsulation method, incorporating a low bandwidth reconciliation
technique allowing two parties to exactly agree on a uniformly
distributed secret value from noisy RLWE instances. This was followed
by a concrete instantiation with parameter sets by Bos, Costello,
Naehrig, Stebila, followed by another instantiation by Alkim, Ducas,
Poppelmann and Schwabe with the same ring polynomial but a smaller
modulus and a different reconciliation method. Unlike most other
public key cryptography based key exchange methods, it is believed
that RLWE based key exchange would remain secure in the event that an
adversary is able to build a quantum computer. This document is a
product of the Crypto Forum Research Group (CFRG).