Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
48
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 ...
- 589
4
votes
2
answers
540
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
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
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
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
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
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
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
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
6
votes
1
answer
224
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 ...
- 177
2
votes
2
answers
223
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 ...
- 8,291
2
votes
1
answer
144
views
LWE problem with a sparse matrix
Is the LWE problem easy when the matrix $A$ is sparse?
Recall that the LWE problem is the following:
Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$ elements over $\mathbb{Z}/q$, ...
- 83
2
votes
1
answer
291
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 ...
- 23
2
votes
1
answer
112
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 ...
- 189
1
vote
1
answer
504
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,354
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
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
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
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
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
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
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
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
6
votes
2
answers
941
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?
- 123
5
votes
1
answer
260
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
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{...
- 91
5
votes
2
answers
1k
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 ...
- 643
5
votes
1
answer
206
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 ...
- 302
5
votes
1
answer
1k
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,400
4
votes
1
answer
290
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
222
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,096
4
votes
2
answers
407
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
207
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_\...
4
votes
1
answer
164
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$, ...
- 83
3
votes
1
answer
117
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
703
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
1
answer
381
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 ...
- 4,882
3
votes
1
answer
262
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. ...
- 189
2
votes
0
answers
209
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 ...
- 879
2
votes
1
answer
194
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 ...
- 769
2
votes
0
answers
160
views
SampleLeft function in lattice trapdoors
We have SampleLeft function in lattice trapdoors as
Algorithm $\textbf{SampleLeft}(A,M_1,T_A,u,\sigma)$:
$\textbf{Input}$: a rank $n$ matrix $A$ in $\mathbb{Z}^{n×m}_q$ and a matrix $M_1$ in $\...
- 394
2
votes
1
answer
519
views
Bit decomposing a polynomial in BGV cryptosystem
I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a ...
- 85
1
vote
1
answer
129
views
NTRUEncrypt fails on complex algebra
I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the ...
- 189
1
vote
1
answer
87
views
value bound of r⋅e for LWE Decryption correctness
For LWE decryption, Someone told me that If we can bound r⋅e by q/4 then we can retrieve M by checking if this is closer to <...
- 121
1
vote
1
answer
107
views
How long time per operation to crack Kyber1024 compared to AES256 for quantum computers?
How long time does quantum computers take per operation when search the key of Kyber? Grover's algorithm weakens 256-bit AES to 128-bit security, quantum computers at most take 2^128 operations to ...
- 341
1
vote
1
answer
836
views
What is the intuition of canonical-embedding in homomorphic encryption based on RingLWE?
In the cryptosystem based on Ring-LWE, the noise amount is measured by canonical-embedding norm.
What is the intuition behind canonical-embedding?
- 1,545
1
vote
1
answer
137
views
Explanation of the tables found in Kyber round1 code?
The precomp.c file in Kyber NIST round 1 submission has three tables, could you please let me know how to generate these three tables? If I want to understand how ...
- 11