# Tag Info

27

There is no public paper available yet, so this answer is preliminary and based on what was presented in the talk and the follow-up discussion. A full understanding cannot be reached until there is a paper to verify, evaluate, and compare to prior work and known results. However, a good understanding of the situation already seems to be emerging. The tl;dr ...

22

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

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 ...

15

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 ...

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 ...

15

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 ...

15

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 ...

14

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^... 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)$... 12 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 ... 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: $$\mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\}$$ In cryptography, we are interested on integer lattices, i.... 10 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 ... 10 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 ... 9 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 ... 9 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 ... 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 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 ... 9 From Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process 3.12 NewHope NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is Regev’s original idea for public-key encryption from plain LWE but specialized to a power-of-2 cyclotomic ring structure, enabling smaller ciphertext and key ... 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

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 ...

8

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 ...

8

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 ...

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.

8

No, we cannot say that Short Integer Solution ($SIS$) problem is NP-Complete. The results from those two papers are not directly related like that, because on the first one, the reduction is from $SIVP_\sqrt{n}$ to $SIS$ while in the second paper, $SIVP_c$ is proven to be NP-Hard for any constant $c$. Until now, there is no proof that $SIVP_\sqrt{n}$ is NP-...

8

TL;DR The AGCD problem does require asymptotic exponential time to be solved. In general, LLL cannot solve the AGCD problem The parameters $(\gamma, \eta, \rho) = (\lambda^5, \lambda^2, \lambda)$ proposed in DGHV10 guarantee (asymptotic) security level of $2^{\Omega(\lambda)}$. Lattice attacks on the AGCD problem You are supposing that one can solve the ...

7

I give another simple proof using the leftover hash lemma. The proof goes as follows, where I'll abuse the notation and assume that q is prime. Game0 The adversary can see $$(A,b,c,u,v,w,s) = (A, As+e, At+f, rA, rb+x\lfloor q/2 \rceil, rc+y\lfloor q/2 \rceil, s).$$ Game1 The view is changed as (A,b,c,u,v,w,s) = (A, As+e, c, rA, rb+x\lfloor q/2 \rceil, ...

7

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'...

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