Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
65 questions
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 ...
- 639
4
votes
2
answers
720
views
What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?
The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
- 315
11
votes
1
answer
2k
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 ...
- 609
9
votes
1
answer
1k
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\...
- 1,039
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
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
13
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 ...
- 961
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
1
answer
898
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 ...
- 83
8
votes
1
answer
2k
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
6
votes
1
answer
243
views
Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-QuantumWorld
In this paper (Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World), author describe password authenticated key exchange scheme on page 9 and 10 (see Fig. 1 on ...
- 207
6
votes
1
answer
2k
views
How to estimate the hardness of SIS instances?
The Short Integer Solution (SIS) problem is to find, given a matrix $A \in \mathbb{F}_q^{n \times m}$ with uniformly random coefficients, a vector $\mathbf{x} \in \mathbb{Z}^m \backslash \{\mathbf{0}\}...
- 1,460
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
3
votes
1
answer
359
views
Is LWE easy when the matrix $A$ is sparse?
Recall that the LWE problem is the following.
LWE problem. Let $q$ be a prime, let $\chi$ be a distribution of small elements over $\mathbb{Z}/q$, and let $n,m$ be two integers (dimensions of vectors ...
- 155
2
votes
2
answers
242
views
How would low-precision Gaussian sampling impact the security of BLISS?
For digital signature, I implemented BLISS in my cryptographic suite, and wrote the Gaussian sampler based on Lattice Signatures and Bimodal Gaussians. But unlike the reference implementation and ...
- 9,795
2
votes
1
answer
227
views
Why does lattice KEX not require sampling with high precision?
I was reading the NewHope paper, and I see that they are using Binomial distribution and not a discrete Gaussian distribution as was used by BCNS. I also remember hearing somewhere that lattice key ...
- 819
2
votes
1
answer
135
views
NTRUEncrypt fails on quaternion algebra
This is a follow-up of my previous two questions (1 and 2), might be relevant to check them out first for a full context. I am trying to re-create results from this paper. The basic algorithm is ...
- 219
1
vote
1
answer
1k
views
Do q-ary lattices have parallelogram kind of structure?
An $m$-dimensional lattice is defined by a basis $A \in \mathbb{R}^{m \times n}$ is the set of points $\{Az : z \in \mathbb{Z}^n\}$. A picture of these points would be like a nice parallelogram kind ...
- 1,464
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 ...
25
votes
3
answers
7k
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 ...
- 807
18
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 ...
- 448
16
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,716
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
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
11
votes
2
answers
3k
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 \...
- 919
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?
- 919
9
votes
0
answers
504
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
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
7
votes
2
answers
2k
views
How to find the value of a vector modulo a basis in lattice-based cryptography
In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance:
$\psi \leftarrow \psi' \mod B$
Taken from page 69 of ...
- 683
6
votes
1
answer
1k
views
The equivalence of SIS and ISIS(Inhomogeneous SIS)
I would like to know whether these two problems are equivalent or not, namely:
$SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \...
- 63
6
votes
1
answer
889
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|| ...
- 919
6
votes
2
answers
2k
views
What is the direct connection between LWE and GapSVP?
Learning with Errors Problem (LWE): Given a polynomial number of random noisy linear equations $b_i$ in the form of pairs
$$
(a_i, \quad b_i = \langle s, a_i \rangle + e_i)
$$
where $a_i \in \mathbb{...
- 101
6
votes
2
answers
2k
views
MLWE (and RLWE) to LWE reductions proof
In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
- 143
5
votes
1
answer
339
views
LWE with identity sub-matrix and reused sampled from [MP12]: why is it secure?
I studied this paper a while ago, but now I'm confused by the paper Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller by Micciancio and Peikert. Page 24 and 25, they present an algorithm that ...
- 1,511
5
votes
1
answer
318
views
ISIS problem in the case of $m=n$
The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $q$, a matrix $A\in \mathbb{Z}^{n\times m}_q$, a vector $b\in \mathbb{Z}^{n}_q$, and a real $\beta$, find an ...
- 483
5
votes
1
answer
215
views
Why is does the protocol of Ding et al. produce biased bits and does it relate to passive security?
I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 9):
We remark that a work of Ding et al. DXL14 proposes a different
reconciliation method ...
- 322
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
4
votes
1
answer
258
views
Prove that a small Ring-LWE secret is unique
I just want to know whether my proof is correct, which is about proving that if the Ring-LWE secret is small, then it is unique. Before giving my proof, here is a fact:
Fact 1: $\Pr [\Vert r \Vert_\...
- 135
4
votes
1
answer
341
views
Finding the exact solution of an LWE instance with a sparse matrix
I already asked a question about the feasibility of LWE when the matrix A is sparse or small here.
Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$
elements over $\mathbb{Z}/q$, ...
- 155
4
votes
2
answers
463
views
How to determine the concrete security of lattice cryptosystems?
I am currently reading about lattice cryptography and am interested in the cryptosystems based on the LWE problem. I understand the reductions from lattice problems to dLWE. Then we base our belief in ...
- 41
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
3
votes
2
answers
443
views
How is the matrix A related to the lattice space L in SIS?
Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard ...
- 93
3
votes
1
answer
294
views
NTRUEncrypt fails on sedonion algebra
This question is a direct follow-up (hopefully - the last) of my previous one; please see it for full information. I would like to further generalise NTRU cryptosystem on higher-order algebras. ...
- 219
3
votes
1
answer
136
views
How does the 'Flatten' function reduce the coefficients of a vector/matrix?
Seen here, at the bottom of page 5, $\operatorname{Flatten}(\vec{a})$ is defined as:
$\operatorname{Flatten}(\vec{a})=\operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1}(\vec{a}))$
For an n-...
- 93
3
votes
1
answer
2k
views
Understanding Unique-SVP and Kannan's Embedding
I am trying to understand the Kannan embedding technique. But I am confused about the formation of the B' and the finding of the short vector inside that basis. How does this basis matrix in the ...
- 31
3
votes
1
answer
852
views
Trapdoors for lattices
I refer to an article https://eprint.iacr.org/2011/501. I focus on (a bit modified) Algorithm 1 which runs as follows (in my understanding):
For given $n, m\in \mathbb N$, $q=2^k$ and a distribution $\...
- 133
3
votes
0
answers
235
views
Hardness of $SIS$ and its reduction to an NP-complete problem
Short Integer Solution ($ SIS_\gamma^{(q,n,m,\beta)}$): Given a matrix $A\in Z_{q}^{n×m}$, find $x \in Z^m $, such that $Ax=0\mod q$ and $||x|| \le \beta$
Is $SIS\in NP$ ?
If $SIS \in NP$, then it ...
- 919
3
votes
1
answer
424
views
Gap problem for Learning With Errors
Informally, a "Gap problem" arises when solving the computational (or search) version using an oracle for the decisional version. This definition of Gap Problem was introduced by Okamoto and ...
- 5,032
2
votes
1
answer
118
views
Ring-LWE lattice cryptography and FFT Trick for $X^n+1$
in reference here the FFT trick for $X^n+1$ is discussed with reference to the Number Theoretic transformation. On page 5, the Chinese Remainder Theorem is used to define the mapping.
So far so good. ...
- 177
2
votes
1
answer
271
views
Classification of attacks against lattices
I'm interested about the cryptanalysis side of lattice-based cryptography, and was wondering whether there is a survey paper or something that gives some classification of attacks against lattices, ...
user4936