30
votes
What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?
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 ...
- 5,773
28
votes
Kyber and Dilithium explained to primary school students?
I'll take that challenge for Kyber, but I fear that a simplification of Dilithium could more easily lead to a dangerous understanding.
I'm going to describe a cryptographic design, mini-Kyber, that is ...
- 21.2k
22
votes
Why are only lattice problems used in cryptography?
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 ...
- 5,113
20
votes
Accepted
Is lattice-based cryptography practical?
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 ...
- 15k
19
votes
Accepted
New quantum attack on lattices (or Shor strikes again)?
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) ...
- 5,773
16
votes
Uniform vs discrete Gaussian sampling in Ring learning with errors
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 ...
- 1,082
16
votes
New quantum attack on lattices (or Shor strikes again)?
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 ...
- 27.5k
15
votes
New quantum attack on lattices (or Shor strikes again)?
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 ...
- 1,136
15
votes
Accepted
Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?
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(...
- 5,773
14
votes
Kyber and Dilithium explained to primary school students?
Despite Daniel's valiant effort I think the correct answer is no, you can not with reasonable effort explain the inner workings of post quantum cryptography to most primary school students.
You should ...
- 11.6k
13
votes
Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?
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 ...
- 1,193
13
votes
Current Consensus on Security of Lattice Based Cryptography?
The claimed attack does not "break" lattice-based cryptography, merely further improves known attacks.
I'll try to briefly describe the situation.
Asymptotics:
Asymptotically, our best ...
- 11.3k
12
votes
Accepted
Use of q-ary lattices in developing cryptosystems
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 ...
- 5,773
12
votes
Accepted
Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm
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 ...
- 1,136
12
votes
Accepted
Discrete Gaussian Sampling role in Lattice-Based Crypto?
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, ...
- 766
11
votes
Why is lattice-based cryptography believed to be hard against quantum computer?
I'm unaware of a great answer to this problem.
There are "partial answers", but they are not great.
Still, they are what I use to (vaguely) explain things, being someone interested in ...
- 11.3k
11
votes
NewHope and NIST's Post-quantum standardization
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 ...
- 46.5k
10
votes
Accepted
Why is the Lovász condition used in the LLL algorithm?
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 ...
- 11.9k
10
votes
Accepted
Peikert's framework for attacks on R-LWE: What "reduction modulo q" means?
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+...
- 5,773
10
votes
Accepted
Relation between decisional SIS and leftover hash lemma in lattices
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 ...
- 5,773
10
votes
Accepted
Why is lattice-based cryptography believed to be hard against quantum computer?
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 ...
- 38.4k
10
votes
Why did NIST select Kyber and Dilithium?
NIST did consider the MATZOV attacks. If we read their Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, we see in section 4.1.1 on page 29:
During the ...
- 21.2k
9
votes
Accepted
Irreducible polynomial in Ring-LWE
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 ...
- 691
9
votes
Accepted
Why does lattice KEX not require sampling with high precision?
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-...
- 1,136
9
votes
Accepted
Why do Problems for Post-Quantum algorithms have to be NP-Hard?
I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why ...
- 11.3k
9
votes
What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?
I created a website to crowdsource what is known about algorithms for lattice problems in NP intersect CoNP:
https://latticealgorithms.xyz
Our paper is up:
https://arxiv.org/abs/2201.13450
For the ...
- 91
8
votes
What is meant by a "short" vector in cryptography?
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,...
- 1,554
8
votes
Accepted
In R-LWE, is there any advantage to generate secret from normal distribution instead of uniform distribution
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 ...
- 1,136
8
votes
Accepted
Lattice Crypto worst case to average case
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~\...
- 1,136
8
votes
Hardness of Short Interger Solution in Lattices
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 $...
Only top scored, non community-wiki answers of a minimum length are eligible