Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
130
questions with no upvoted or accepted answers
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
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
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
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
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
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
5
votes
0
answers
85
views
Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?
I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge.
Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to ...
- 10.8k
5
votes
0
answers
157
views
How did Kyber's authors compute the error probability $\delta$?
I'm studying the specification of Kyber that was submitted to NIST PQC Round 3. However, I cannot figure out how they compute the error probability $\delta$ for Kyber 512, 768 and 1024. I have read ...
- 171
5
votes
0
answers
72
views
Relation between LPN and GAPSVP?
I have a question regarding the relationship between the (search) LPN problem and the GapSVP problem.
I have read a related problem that explains the main theorem in Reg05: the GapSVP problem can be ...
- 145
5
votes
0
answers
199
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 $(-\...
- 436
5
votes
0
answers
546
views
Lattices with hidden short vectors and an algorithm for a special case of the SVP
For the purpose of testing algorithms for lattice basis reduction or finding short vectors, it would be useful to have examples of lattices where short vectors are hidden, that is, a nontrivial ...
- 51
5
votes
0
answers
428
views
ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc
While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
- 616
5
votes
0
answers
2k
views
How babai nearest plane algorithm solves approximate CVP
Babai's nearest plane algorithm solves approximate-CVP (Closest Vector Problem) where the approximation factor is $2(\frac{2}{\sqrt{3}})^n$.
Let $b_1,...,b_n$ be a basis and $t$ be the target. This ...
- 879
4
votes
0
answers
278
views
Which parts of CRYSTALS-Kyber and CRYSTALS-Dilithium are compatible?
The papers CRYSTALS-Kyber and CRYSTALS-Dilithium both have been written by quite different authors. It seems that at least the key generation is very different from each other. CRYSTALS mainly seems ...
- 90.2k
4
votes
0
answers
78
views
LWR parameter estimation
I am trying to estimate parameters for LWR $(n,q,p)$ instance using the LWE estimator. My $q,p$ are $283,256$-bit prime numbers and I am trying to find required $n$ for 128 bit security.
For this, I ...
- 139
4
votes
0
answers
173
views
What is the difference between discrete-then-gaussian and gaussian-then-discrete?
In lattice cryptography, we always face the probem of discrete gaussian sampling. To the beginners, it is a bit complex. However, gaussian sampling from a continous space is much easier to understand, ...
- 293
4
votes
0
answers
108
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
0
answers
233
views
Is the ring learning with errors problem still hard if the errors are drawn from some subspace?
Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear ...
- 243
4
votes
0
answers
253
views
Worst case to average case in Ring LWE
I am currently trying to understand this Ring LWE article and I have a question. I don't understand how to apply Lemma 5.11 in order to get the worst case to average case reduction in Lemma 5.12, as ...
- 41
4
votes
0
answers
144
views
How to recover $e$ from $f_A(e) = Ae \mod q$ when knowing trapdoor
I have a silly question, but I don't know a solution, so I need to question.
Assume, with a algorithm $TrapGen(1^\lambda)$, it generates $A\in\mathbb{Z}_q^{n\times m}$ with a basis $B \in\mathbb{Z}_q^...
- 205
4
votes
1
answer
230
views
Lattice-based cryptography prone to side channel attack?
Is lattice-based cryptography still prone to side channel attacks? What are some mitigation strategies, if any?
- 41
3
votes
0
answers
51
views
Why was A doubled in size
Why was the dimension of A doubled in kyber?
LWE encryption uses a public matrix A of dimension K but kyber uses a double matrix A resulting in $A ^{ k * k * n }$
When deriving the results of the ...
- 185
3
votes
1
answer
128
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 ...
- 396
3
votes
0
answers
60
views
Paper "How to Meet Ternary LWE Keys": Why can Odlyzko's hash function not be used to construct the mitm lists recursively?
In Alexander May's Paper "How to Meet Ternary LWE Keys", Alexander May writes the following about combining representation techniques with Odlyzko's locality sensitive hash function (Page ...
- 347
3
votes
0
answers
190
views
The decryption correctness of RLWE based Encryption
I get stuck in the proof of decryption correctness in RLWE based Cryptosystem. To state where I am , let me show the full scheme first. The image is from chapter 3.2 of this paper.
And the decryption ...
- 73
3
votes
0
answers
123
views
q-ary lattices - proof of dual upto scale
Two lattices are defined as following:
\begin{align}
\Lambda_q^{\bot}{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: A\mathbf{x} = \mathbf{0}\text{ mod }q\} \\
\Lambda_q{(A)} & = \{\mathbf{x} \in \...
- 259
3
votes
0
answers
160
views
Is there a source(book, thesis, paper) that explains Lattice basis reduction algorithms (LLL, HKZ) and provides an in depth analysis of the same?
I want to give a slight background about me: I've Bachelors in Computer Engineering and I've been interested in Cryptography since my college days and have been following the field ever since. I'm ...
- 151
3
votes
0
answers
133
views
Coppersmith attack on NTRU and non-commutativity
In this paper, Coppersmith and Shamir used lattice reduction to attack NTRU. At the very end of the paper, they note that developing non-commutative variants of NTRU would be wise, in light of their ...
- 381
3
votes
0
answers
151
views
How to use Rényi divergence for noise flooding
Let $\chi_\sigma$ be a discrete (or continuous) Gaussian distribution with standard deviation $\sigma$.
Then, it is known that for $y \in \mathbb{Z}$, a statistical distance between $\chi$ and $\chi + ...
- 149
3
votes
0
answers
88
views
Gram-Schmidt coefficients in LLL algorithm
To my understanding the LLL lattice reduction algorithm starts with a set of integer vectors $\{b_1, \dots, b_2\}$, which span a lattice, and tries to generate a new basis of shorter vectors of the ...
- 31
3
votes
0
answers
57
views
It is possible to prove this in zero knowledge?
Let $\mathcal{R}_q = \mathbb{Z}_q/\langle x^n + 1 \rangle$, with $n$ a power of $2$. Suppose that we sample $\mathbf{r} \leftarrow \mathcal{R}_q^m$ uniformly at random with the property that $0 < ||...
- 712
3
votes
0
answers
103
views
Why ideal lattices?
An ideal lattice is a lattice $\mathcal{L}(A)$ generated by a block matrix
$A = \left[ A^{(1)} \mid \dots \mid A^{(m/n)} \right]$ whose blocks $A^{(i)}$ are constructed from a vector $a^{(i)}$ and a ...
- 712
3
votes
0
answers
104
views
parameter choosing for SIS based scheme in lattice based cryptography
In SIS based scheme, there is a matrix $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, and $n$ is the security parameter. I want to ask that why $n=1$ is also okay for the scheme (in "A ...
- 321
3
votes
0
answers
210
views
Block size of BKZ algorithm and related security of CRYSTALS-Kyber
Security of lattice-based schemes in the NIST Posto-Quantum Project often relies on the complexity of dual attack. Complexity of this attack depends on the running time of lattice basis reduction ...
- 167
3
votes
0
answers
73
views
Lattice Based Cryptography domain
Some cryptosystems operate on the domain of the form $\mathbb{Z}_q[x]/\langle x^n-1\rangle$ and others operate on $\mathbb{Z}_q[x]/\langle x^n+1\rangle$.
What's the security impact of the two forms?
- 87
3
votes
0
answers
192
views
CVP over $\Bbb Z_{q}$ - is the problem still hard?
I'm reading about the CVP problem, and all the papers I've read so far handle the case where the CVP matrix and vector are over $\Bbb R^{n}$ (or over $\Bbb Z^{n}$), and the distance is a real number.
...
- 247
3
votes
0
answers
117
views
Adaptation of Stern Zero-Knowledge protocol from coding to lattices
I'm currently working on Zero-Knowledge-proofs in lattice context, for which there exist two major frameworks. One of those two is the adaptation of Stern protocol from code-based-crypto.
There is in ...
- 31
3
votes
0
answers
320
views
Comparison of NTRU-based schemes and LWE-based schemes
What advantages and disadvantages can be distinguished in NTRU-based and LWE-based schemes relative to each other? In what cases which scheme gives advantage?
UPD: I'm interesting in two things: 1)...
- 123
3
votes
0
answers
60
views
Hardness or negligibility of finding small non-trivial addition coefficients for random values to sum to zero
In my cryptographic scheme, I would like to rely on the hardness or negligibility of the following problem or situation, respectively. Note the original motivation: it shall be impossible to find two ...
- 181
3
votes
0
answers
154
views
In Lattice Cryptography, why is it hard to find short vectors if given long vectors?
In lattice cryptography it seems like giving out long vectors for a lattice that can be drawn from much shorter vectors (generating an identical lattice) is somehow useful for public-private key ...
- 73
3
votes
0
answers
80
views
Size of $q$ in reductions from lattice problems to R-SIS
The Short integer solution problem is parameterized by four values:
$n$, the dimension of the vectors that must be added
$m$, the number of samples (dimension of the solution)
$\beta$, upper-bound ...
3
votes
0
answers
337
views
Short integer solution lattice problem with q=2
For large values of $q$, we know that there are worst-case lattice problems which reduce to the average-case short integer solution (SIS) problem. Does this means that for $q=2$, the SIS problem is ...
- 990
3
votes
0
answers
62
views
show how LWE errors can have a greater impact on result
Hi weve been given the following question in one of our classes but have not been taught anything about it and is worded strangely. It is to show how the LWE problem works by showing how small errors ...
- 51
3
votes
0
answers
229
views
In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$
In the NTRU cryptosystem, it is suggested to take $N$ prime.
I want to understand why.
In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (...
- 325
3
votes
0
answers
84
views
Construct new SIS solutions from given ones
Assume we have a lattice SIS problem
$A x = 0$, with $\Vert x \Vert < \beta$ and we are given $k$ solutions $x_1, \dots, x_k$ by, say an oracle.
Is it then hard or easy to construct from there a ...
user27950
3
votes
0
answers
1k
views
The Inhomogeneous Short Integer Solution (ISIS) problem with a clue
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 ...
- 4,882
2
votes
0
answers
42
views
Hardness of LWE with Uniform Secrets and Error Distributions
I have seen various papers discussing the security of the Learning with Errors problem with very small uniform secrets and errors but I have not found any papers on the general LWE problem with ...
- 21
2
votes
0
answers
38
views
Learning with rounding: uniformity
Naively, when one applies rounding to a uniform random value one anticipates that the change is uniformly distributed. In lattice-based cryptography, is there a formal notion or proof of equivalence ...
- 20.1k