All Questions
Tagged with lattice-crypto post-quantum-cryptography
178 questions
62
votes
4
answers
11k
views
Polynomial-time Quantum Algorithms for Lattice Problems
A new paper, by Yilei Chen, whose title is Quantum Algorithms for Lattice Problems (https://eprint.iacr.org/2024/555) appeared on eprint and it claims to solve hard lattice problems, such as the ...
33
votes
3
answers
5k
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,958
20
votes
1
answer
1k
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,295
16
votes
4
answers
8k
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?
- 371
15
votes
1
answer
1k
views
Impact of Ryan and Heninger's CRYPTO 2023 paper on post quantum cryptosystems
From Schneier's blog, which seems to have been written in response to a somewhat recent Quanta magazine article:
The winner of the Best Paper Award at CRYPTO this year (2023) was a significant ...
- 23.7k
14
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?
- 239
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
5
answers
3k
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,685
13
votes
1
answer
3k
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 ...
- 131
13
votes
0
answers
711
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 ...
- 589
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
3
answers
1k
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,635
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
9
votes
2
answers
606
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 ...
- 1,039
9
votes
1
answer
645
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,813
9
votes
1
answer
2k
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 ...
- 357
9
votes
2
answers
744
views
Is NTRU broken?
Today a new paper appeared on ePrint, "Improved Provable Reduction of NTRU and Hypercubic Lattices". It claims that:
this is the first provable result showing that breaking NTRU lattices ...
- 880
9
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 ...
- 322
9
votes
0
answers
874
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,614
9
votes
0
answers
177
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" - ...
- 187
8
votes
2
answers
1k
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,511
8
votes
0
answers
316
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
558
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,295
7
votes
1
answer
3k
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?
- 438
7
votes
1
answer
365
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, ...
- 448
7
votes
1
answer
687
views
Decision to Search LWE when modulus $q=p^e$
I am reading Applebaum et al..
In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $q=p^e$ for prime $p$.
In the proof, they define the hybrid ...
- 165
7
votes
1
answer
302
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,813
6
votes
3
answers
2k
views
Why do Problems for Post-Quantum algorithms have to be NP-Hard?
The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.
Solving quadratic equations over finite fields
short lattice vectors and close lattice ...
- 317
6
votes
1
answer
350
views
NTRU Cryptosystem: Why "rotated" coefficients of key f work the same as f
In the NTRU cryptosystem, we can use a randomly generated polynomial f that is inversible under modulo p and q to encrypt and decrypt our plaintext. While studying this system, I attempted to ...
- 175
6
votes
4
answers
1k
views
Why Module-LWE and not Ring-LWE?
I am trying to understand the NIST-submissions for post-quantum cryptography a bit better, and I noticed that the submissions from the CRYSTALS-family in particular is based on Module-LWE.
I ...
- 61
6
votes
1
answer
796
views
Do we need the quantum random oracle model (QROM)?
I am currently studying the proof of the Dilithium signature in the quantum random oracle model (QROM). I am curious to hear if anyone have any thoughts on the importance of having proofs in the QROM ...
- 343
6
votes
1
answer
125
views
Do the specific powers of two $2^{23}$ and $2^{13}$ in the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$ have any special purpose in its design?
I recently started exploring Post-Quantum Cryptography, particularly Lattice-based Cryptography, and came across the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$, which is used in schemes like ...
- 85
5
votes
1
answer
346
views
How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem?
In Lindner & Peikert paper, the authors propose that to set the cryptosystem's parameters, one should choose $q$ to be large enough to allow for a Gaussian parameter $s \geq 8$.
My question is, ...
- 1,039
5
votes
3
answers
314
views
How to reconstruct low order bits of $t$ of CRYSTALS-Dilithium from a small number of signatures?
In FIPS 204 (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf): "The vector $\textbf{t}$ is compressed in the actual public key by dropping the $d$ least significant bits from each ...
5
votes
1
answer
253
views
Shortest Vector Problem as Dihedral Hidden Subgroup Problem
I’m a mathematician trying to get into cryptography. I have a somewhat silly question, but I can’t seem to find a proper answer anywhere. I am interested in whether or not there is a way to directly ...
- 101
5
votes
1
answer
285
views
$L^3$ Grover search of NTRU variants
I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks ...
- 214
5
votes
1
answer
239
views
What is the effect of low rank dual sublattices on the dual lattice attack on LWE?
In the dual lattice attack of Espitau, Joux and Kharchenko (On a dual/hybrid approach to small secret LWE), the authors propose distinguishing (and subsequently recovering secret values) of LWE ...
- 26.4k
5
votes
1
answer
128
views
Ring LWE distribution definitions
This may be a stupid question but I've been stuck on parsing these definitions for a while.
I am reading the paper "On Ideal Lattices and Learning with Errors Over Rings" by Lyubashevsky, ...
- 113
5
votes
0
answers
300
views
Why is it safe to generate the secret key and masking vectors using rejection sampling in CRYSTALS-Dilithium?
In CRYSTALS-Dilithium module lattice-based digital signatures, the secret key vectors $s_1, s_2$ with coefficients in $[-\eta, \eta]$ and the signature masking vector $y$ with coefficients in $(-\...
- 438
5
votes
0
answers
128
views
How does error distribution affect security in lattices?
It's easy to see that the crucial part of any lattice scheme is the added error. And different schemes seem to use different error distributions, some use Gaussian some use centered Binomial. Though, ...
user4936
4
votes
1
answer
734
views
RLWE Explanation
In RLWE,
we often choose the following polynomial ring,
where q is a prime,
and n is a power of 2, e.g. $2^k$
$$\mathbb Z_q[X]/(X^n + 1)$$
We know that ${X^{2^k}} + 1$ is an irreducible polynomial ...
- 43
4
votes
2
answers
339
views
Testing of PQC NIST round3 submissions
I am new to this field and have some concerns regarding PQC;
How does NIST do a comparison that a particular algorithm is efficient and its security can not be broken by future quantum attacks? I am ...
- 41
4
votes
1
answer
197
views
Famous ideal lattices
I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ...
In more ...
- 505
4
votes
2
answers
661
views
Why does Learning With Errors require a bunch of samples?
Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity.
LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE ...
- 1,685
4
votes
1
answer
290
views
Would LWE problem be still secure if error were like this $e=2e_1$?
In the Learning with error problem, if the error term $e$ from equation $b=<a,s>/q+e$ were of this kind $e=2e_1$, where $e_1$ is chosen according to the probability distribution for the LWE ...
- 689
4
votes
1
answer
136
views
In reduction from search LWE to decsion LWE why sampling needs to repeat a polynomial number of times?
I've been reading through MIT's lecture notes on learning with errors here, and I'm trying to understand the reduction from Search LWE to Decision LWE, as described there in Section 2.7, "...
- 413
4
votes
1
answer
568
views
What is the largest parameter broken for NTRU?
The original secure parameters for NTRU shown below are from the original HPS98 paper. This is vastly different from the current secure suggested parameters in the NIST PQC round 3 submission.
...
- 237
4
votes
1
answer
373
views
Adapting LWE Trapdoors for Ring-LWE
In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.
Theorem 5.1: There is an ...
- 516
4
votes
1
answer
611
views
Dilithium signature scheme and timing attacks – Does the running time actually depend on the secret key?
The paper “CRYSTALS – Dilithium: Digital Signatures from Module Lattices” (by Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé) introduces a digital ...
- 4,813
4
votes
1
answer
139
views
"Shifting" a dual-Regev keypair away from a trapdoored instance
This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality:
$\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair
...
- 430