Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
495
questions
32
votes
3
answers
3k
views
New quantum attack on lattices (or Shor strikes again)?
Lior Eldar and Peter W. Shor published a paper on arXiv.org in which they present a new quantum algorithm against a variant of BDD. They claim that their new algorithm can efficiently solve the ...
- 2,880
31
votes
1
answer
2k
views
Uniform vs discrete Gaussian sampling in Ring learning with errors
The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply ...
- 589
24
votes
3
answers
5k
views
What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?
In An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor, the author claims they give a polynomial-time quantum algorithm for solving the Bounded Distance ...
- 777
19
votes
1
answer
4k
views
What are the benefits of lattice based cryptography?
Previously we visited the benefits of elliptic curves for cryptography. Lattice based cryptography is starting to become quite popular in academia. The primary benefit of lattice based crypto is the ...
- 38.3k
19
votes
1
answer
942
views
Quantum complexity of LWE
As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that ...
- 1,235
17
votes
2
answers
2k
views
Why is Approximate GCD a hard problem?
There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem.
The paper Algorithms for the Approximate ...
- 428
15
votes
0
answers
1k
views
Given a 'good' basis for a lattice, how can we solve the CVP?
I'm doing a little bit of reading about lattices. I read that if we can find a 'short' basis for our given lattice, we can solve CVP and SVP very efficiently. However, the paper didn't describe an ...
- 4,616
14
votes
4
answers
5k
views
Kyber and Dilithium explained to primary school students?
Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?
- 341
14
votes
1
answer
2k
views
Is lattice-based cryptography practical?
How viable is lattice-based cryptography in a "practical" setting?
It has been said that lattice-based cryptography would be a "post-quantum" cryptography scheme, but is it feasibly implementable?
- 313
13
votes
3
answers
1k
views
Why are only lattice problems used in cryptography?
There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?
- 229
12
votes
5
answers
1k
views
Why is lattice-based cryptography believed to be hard against quantum computer?
Why is lattice-based cryptography believed to be hard against quantum computer?
Learning With Errors(LWE) problem (reduction to SVP) is just one example.
Can you provide some intuition of the ...
- 1,545
12
votes
1
answer
2k
views
Current Consensus on Security of Lattice Based Cryptography?
In an edit to an answer by user forest, it was mentioned that there has been a new attack developed for lattice-based cryptography. I thought lattice-based cryptography is a fairly well established ...
- 313
12
votes
1
answer
2k
views
Why did NIST select Kyber and Dilithium?
NIST selected Kyber for key agreement and Dilithium for digital signature applications some days ago. But IDF's MATZOV group, in their paper, broke Kyber and Dilithium and brought the security levels ...
- 121
12
votes
0
answers
650
views
Potential Flaws With Lattice Based Cryptography?
From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
- 549
11
votes
2
answers
4k
views
What does "Worst-case hardness" mean in lattice-based cryptography?
In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below:
Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with ...
- 941
11
votes
1
answer
3k
views
Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?
In the paper, "Post Quantum Key Exhange - A New Hope," the authors present a lattice-based key exchange based on the work of Chris Peikert. In this "New Hope" key exchange the authors try to gain ...
- 111
11
votes
0
answers
97
views
Decision R-LWE parameters for spherical error with worst-case hardness
In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
- 111
11
votes
0
answers
635
views
Why SIVP Is Worst Case Problem?
I just started to study lattice Cryptography.
I'm now studying worst-case to average-case reduction for SIS.
In previous question, "worst means any and average means random".
And I wonder why the ...
- 477
10
votes
2
answers
1k
views
Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?
A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications ...
- 10.8k
10
votes
3
answers
821
views
Error-correcting Code VS Lattice-based Crypto
I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise....
- 2,543
10
votes
2
answers
2k
views
Why is the Lovász condition used in the LLL algorithm?
The LLL algorithm is used to approximate the Shortest Vector Problem, i.e., it outputs a reduced basis. Such a basis will satisfy two conditions:
$$ \forall i \gt j. \quad \lvert\mu_{ij}\rvert \le \...
- 879
10
votes
1
answer
1k
views
Use of q-ary lattices in developing cryptosystems
Why q-ary lattices are used to most cryptosystems rather than lattices.
In most of the papers q-ary lattices are used. Is there any advantage?
and
Given $$B=(v_1,v_2,v_3,.....v_n)$$ is the basis, ...
- 879
10
votes
1
answer
1k
views
Most influential/illuminating papers/books/courses on lattice based cryptography?
I'm interested in some sort of "compendium" on lattice-based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of ...
- 589
9
votes
2
answers
547
views
Peikert's framework for attacks on R-LWE: What "reduction modulo q" means?
I am reading Peikert's paper [Pei16] about secure instantiating of R-LWE problem. In section 3.1, The author gives a new attack framework by using "reduction modulo an ideal divisor $\mathfrak{q}$ of ...
- 990
9
votes
1
answer
517
views
Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm
By a “Diffe-Hellman-like” algorithm, I mean one that has the same API as Curve25519, etc (disregarding trivial differences such as the size of parameters): a function
$$F: (P_\text{other}, S_\text{...
- 4,763
9
votes
1
answer
1k
views
Lattice Crypto worst case to average case
I am currently reading the ETSI white paper Quantum Safe Cryptography and Security
On page 24 one finds the following statement:
Lattice problems also benefit from something called worst-case to ...
user27950
9
votes
1
answer
146
views
Collisions in the cyclotomic knapsack function
I've been working my way through the paper “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices” by Peikert and Rosen, and I've come across something that doesn't seem ...
- 193
9
votes
1
answer
390
views
Is HIMMO For Real?
I've come across something out of Philips Research called HIMMO Key Pre-Distribution Scheme (https://eprint.iacr.org/2016/410.pdf and https://www.ietf.org/proceedings/96/slides/slides-96-cfrg-2.pdf) ...
- 191
9
votes
1
answer
1k
views
Gaussian distribution in lattices
In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
- 879
9
votes
0
answers
487
views
Can LWE be NP-hard?
Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
- 1,005
9
votes
0
answers
171
views
Differences between “NewHope” and “NewHope-simple”
The well-known paper described a key exchange (KE) scheme named "NewHope" on USENIX 2016. The authors then proposed "NewHope-Simple" - a PKE/KEM scheme. They also submitted "NewHope for NIST" - ...
- 177
8
votes
1
answer
598
views
NewHope and NIST's Post-quantum standardization
Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules.
Is being a ring-based KEM ...
- 1,235
8
votes
1
answer
1k
views
Are LPN and LWE problems equivalent?
Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem ...
user4936
8
votes
2
answers
220
views
Cardinality of the group of units in a cyclotomic ring?
In the NTRU key generation, one samples a polynomial from $K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1)$ and tests if it is invertible. What are the chances of this to happen? In other words:
Let $q$ be a ...
- 524
8
votes
1
answer
264
views
LWE: error and float operations
Background
I'm trying to make sense of the error in implementations of LWE and R-LWE. In LWE and R-LWE error is added to vectors in lattices to make it computationally infeasible to recover any ...
- 214
8
votes
0
answers
214
views
How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?
The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
- 315
7
votes
1
answer
1k
views
Help in understanding exactly how lattices are used as one-way functions for hashing
In my long-distance cryptography course, an assignment covers lattice-based cryptography. It is hard, and I am lost. There is no one to help me.
Thus far, I have understood that:
Lattices are a ...
- 73
7
votes
1
answer
1k
views
Discrete Gaussian Sampling role in Lattice-Based Crypto?
I'm reading up on how post-quantum cryptography works, and stumbled upon the notion of discrete Gaussian sampling. However, I can't understand where it fits in the greater picture - currently it feels ...
- 337
7
votes
1
answer
474
views
Irreducible polynomial in Ring-LWE
In Ring-LWE polynomials are chosen from the ring $R_q=\mathbb{Z}_q[x]/(x^n+1)$, where $n$ is a power of two.
As far as I understand, to create a ring the polynomial $x^n+1$ has to be irreducible (see ...
- 1,235
7
votes
2
answers
681
views
LWE: Round a continuous Gaussian to a true Discrete Gaussian
Short version: how is it possible to round a continuous Gaussian into a true discrete Gaussian (usually denoted $\mathcal{D}_{\mathbb{Z},\alpha q}$)? The goal is to obtain a reduction from continuous ...
- 1,096
7
votes
1
answer
764
views
Find collision in Ajtai's hash function using short vector
Background
What is Ajtai's hash function?
Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given ...
- 73
7
votes
1
answer
2k
views
What is the difference between Module-LWE and Ring-LWE?
Recently, the CRYSTALS lattice-based cryptographic suite has been published, which is based on "module lattices". What is Module-LWE? How is it different from Ring-LWE?
- 436
7
votes
3
answers
2k
views
What is a purpose of reducing lattice basis?
This may be too broad question but it is not. I have been studying lattices for few months now, more specifically I studied:
Lattice problems ($SVP$, $CVP$ and etc.)
Lattice cryptography in post ...
- 302
7
votes
1
answer
258
views
Is LPN not as important as LWE and SVP?
I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
- 438
7
votes
1
answer
623
views
What's the purpose of the smoothing parameter in lattice-based cryptography?
I see nearly all the lattice-based crypto papers talk about the smoothing parameter $\eta$. And I believe even some parameters are chosen with respect to that. However, I do not quite understand what'...
user4936
7
votes
1
answer
253
views
IND-CCA2 post-quantum key exchange
QUIC requires that servers reuse keys so that session resumption works. That breaks many post-quantum key exchange systems.
I am looking for a post-quantum key exchange algorithm with the following ...
- 4,763
7
votes
1
answer
332
views
Lattice attacks against Multilinear Maps [CLT13]
I am currently studying an article on a construction of Multilinear maps. There are some attacks on the scheme presented by the authors and I got stuck at the one in section 5.1.
I will try to ...
- 626
7
votes
0
answers
362
views
Does there exist trapdoor permutation from lattices?
It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
user4936
6
votes
1
answer
804
views
Relation between decisional SIS and leftover hash lemma in lattices
The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\...
- 990
6
votes
1
answer
644
views
Hardness of Short Interger Solution in Lattices
Short Integer Solution ($SIS_{n,m,q,\beta}$) is defined as:
Given a matrix $A \in \mathbb{Z}_{q}^{n \times m}$, find a non-zero vector $x \in \mathbb{Z}^{m}$ such that $A \cdot x = 0\mod q$ and $||x|| ...
- 879