25

Post-quantum security: As you note, quantum attacks are not known to break lattice-based cryptosystems. But some other proposals like McEliece, as well as most symmetric primitives are not known to be poly-time breakable on a quantum computer. Security from worst case assumptions: In security proofs for cryptosystems we typically assume that some problem ...


20

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard. What is required for cryptography is average-case hardness --- i.e., a randomly selected instance of a problem should be "hard" for an adversary to solve. However, random instances of some NP-hard problems (3SAT, e.g.) turn out to be easy with high ...


19

As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) of http://www.scottaaronson.com/blog/?p=2996


16

The authors themselves point out that this doesn't break lattice-based assumptions used in crypto. To quote: Lattice problems have received enormous attention in recent years, mainly because of their algebraic structure has allowed constructions of cryptographic primitives, culminating in the Learning-with-Errors (LWE) encryption scheme due to Regev [...


15

Unless I misunderstood the definitions, an algorithm for the problem in Definition 1 (i.e. their main result) is in fact enough to attack decision-LWE if the noise is small. The fact that they need a promise that the point is always close to the lattice doesn't seem to be a problem. A decision-LWE problem mod q, where samples are of dimension n and the ...


14

One line: worst means any and average means random. Lattice-based cryptosystem Let me restate. Fix security parameter $n$. What the reduction shows is the existence of a solver for the lattice problem on input any $n$-dimensional lattice using the adversary breaking a lattice-based cryptosystem with the security parameter $n$ on the average case. Since ...


14

The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual" $n$-dimensional lattices $L$ (i.e., $L^* = L$) where $\lambda_1(L) = \lambda_1(L^*) = \Omega(\sqrt{n})$, hence $\eta_{2^{-n}}(L) = O(1)$ but $\tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n})$. The statement and proof of ...


13

Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different types of algorithms, lattice-based algorithms dominate the submissions. These include NTRU and its variants, R-LWE, and FALCON (designed in part by one of our ...


13

Independently of the algorithmic claim, I indeed have serious doubts about Theorem 2. Here is a counterargument (using standard techniques) cooked up with Yang Yu and Wessel van Woerden: Suppose that $q$ is prime, and suppose that the minimum distance in the 2-norm is indeed bounded by $b=O(1)$. There are at most $Binom[m,b] \cdot (2b+1)^b = poly(m)$ ...


11

I'm also afraid you couldn't understand this as D.W., but let us start. I sometimes cannot understand your questions. Please restate them, if possible. The definition of the Ajtai hash functions Let $n$, $m$, and $q$ be positive integers. Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$. Let us define a function, which maps a vector in $D^...


11

How is a lattice defined? A lattice $\mathcal L(B)$ is the set of all integer combinations of the basis $B = \{b_1, ..., b_n\}$ of $n$ linearly independent vectors. That is, lattice $\mathcal L(B)$ is defined as: \begin{equation} \mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\} \end{equation} In cryptography, we are interested on integer lattices, i....


11

The TL;DR: From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness; In practice, most of the time you can replace Gaussians by other distributions without too much trouble. Theory First, let me elaborate on a few reasons why Gaussians are better in theory: When ...


11

It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM. So here is what you can do: there is a public polynomial $a\in Z_q[X]/(X^n+1)$ that is shared by everyone. It needs to be uniformly random, so it can be set to XOF(1), where XOF is ...


9

Recall that any ideal $I$ of $R$ is in particular an additive subgroup of $R$, and that the quotient $R/I$ is the collection of cosets $a + I = \{a + i : i \in I\}$ for each $a \in R$. Two cosets $a+I, b+I$ are equal iff $a-b \in I$. The map that sends $a \in R$ to $a + I \in R/I$ is called "reduction modulo $I$," and often written "$a \bmod I$." The ...


9

The way and the purpose in which gaussians are used in key exchange and digital signatures is completely different. In public key encryption (and key exchange), we need computational-indistinguishablilty of (A,As+e) when A is a random matrix (over some ring) and (s,e) are vectors over that same ring with small coefficients. To get the tightest security ...


9

A Gaussian distribution satisfies the following desirable properties: It can be implemented coordinate-wise: If $x_1, x_2, \ldots , x_n$ are each sampled from a one-variable Gaussian distribution, then $(x_1,x_2,\ldots,x_n)$ is sampled from a multivariable Gaussian distribution. It approximates a uniform error distribution modulo a lattice exponentially ...


8

The issue with the length-reduction criterion alone (and the reason the Lovász condition is included in the LLL algorithm) is that the following basis satisfies it: (The grey arrow is the projection of $b_2$ to the orthogonal complement of $b_1$.) Clearly, this basis is not very short, nor is it close to being orthogonal (i.e., note that length reduction ...


8

The cited paper, as well as the theorem of R-LWE in that paper only requires $f$ to be irreducible over the rationals. For this requirement one usually uses $f = x^n+1$ with $n$ a power of $2$. This polynomial is reducible modulo $q$ but it is okay for the proof to go through. The cited paper suggested to use cyclotomic polynomial $\phi_n = 1+x+x^2+...+x^{...


8

Why is lattice-based cryptography believed to be hard against quantum computer? Because no one has developed a quantum algorithm (yet) that breaks these crypto primitives. Wish we could do better than that, but that is the best we have at the moment. We believe these primitives to be quantum resistant because no one has given evidence otherwise.


7

The main advantage of using $q$-ary lattices is that it allows a cryptosystem designer to rely on the standard Short Integer Solution (SIS) and Learning With Errors (LWE) problems, which are known to be at least as hard as worst-case lattice problems. So the SIS/LWE problems abstract away the connection to lattices, and give the designer a strong hardness ...


7

It depends on the exact domain of the hash function and the quality of the SIS solution, i.e., its norm (and the choice of norm itself). Suppose the hash domain is $\{-d, \ldots, d\}^m$, i.e., vectors of $\ell_\infty$ norm at most $d$. Then any nonzero vector in Ajtai's lattice having Euclidean norm at most $d$ collides with the all-zeros input. (Actually, $...


7

Thanks for the question! You are correct that there is a bug here. Indeed, the sentence "choose $\mathbf{b}_i$ s.t. $\ldots$" makes no sense: the LHS is in $H$, but the RHS may not be. Fortunately, there is a simple fix which guarantees $\mathbf{y}'_i \in H$. (This must have been what we intended in the first place, based on how the rest of the proof goes;...


7

Bruteforce appears to work well enough. The following Sage script finds an instance quickly: from sage.libs.fplll.fplll import FP_LLL from sage.libs.fplll.fplll import gen_uniform n = 5 # dimension q = 16 # size of matrix entries while True: M = gen_uniform(n, n, q) L = M.LLL(delta=0.999) S = FP_LLL(L).shortest_vector(algorithm='proved') ...


7

Short just means small (in terms of some metric, usually Euclidean). You can see that if $e$ is the zero vector, $s$ becomes trivial to recover, using Gaussian elimination. If $e$ is uniformly random, then you can imagine that it is impossible to recover any information on $s$, since it is hidden against a uniformly random backdrop. If you're familiar with ...


7

Neither the secret nor the error in Ring-LWE (or LWE) encryption needs to be generated from the normal distribution. Only to get the tightest security proofs does one care about the "shape" of the distribution. For practical cryptanalysis, this does not matter -- only the size of the secret (and noise) does. Having said this, there is an advantage to the ...


7

The leftover hash lemma (LHL) says that $(A,u=Ax) \in \mathbb{Z}_q^{(n+1) \times (m+1)}$ is very close to uniformly random. In particular, this implies that for uniformly random $(A,u)$, there exists a solution $x \in \{0,1\}^m$ to $Ax=u$ with very high probability. For if not, a significant fraction of $u$ values would admit no solution, hence the ...


7

You are right. A worst-case to average-case reduction from problem P to a distribution D over instances of problem Q would mean roughly that $$\Pr_{q\leftarrow D(Q)}[q\text{ is hard} ~|~ \exists~\text{any instance of P that is hard}]>1-\text{negligible}.$$ So even if the support of distribution D is the entire set of instances of problem Q, this does not ...


7

Yes, LPN is (essentially by definition) equivalent to the hardness of decoding a random linear code over $\mathbb{F}_2$. No, there is no known reductions between LPN and LWE. It is usually believed that LPN is (in some sense) "harder to break" than LWE, simply because we know much less attacks on LPN. It seems to have less structure that could be exploited ...


6

The basic idea is to take random (Gaussian) integer combinations of the given LWE samples, and add a little "smoothing" noise. This will result in new samples which are statistically close to LWE samples with the same secret, but with a somewhat wider error distribution (by a factor of $\tilde{O}(\sqrt{n})$ for typical parameters). This is essentially Regev'...


6

xagawa's original answer is almost correct, except for the valid concern pointed out by Florian in the comments. (The updated answer looks good to me.) The answer to the question is "yes," except that the most 'lattice-y' proof works for the modified version of the Regev system defined in Applebaum-Cash-Peikert-Sahai CRYPTO'09. (A version of this was also ...


Only top voted, non community-wiki answers of a minimum length are eligible