Skip to main content

Questions tagged [lattice-crypto]

Lattice-cryptography is the study and use of lattice problems applied to cryptography.

154 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
pg1989's user avatar
  • 4,646
13 votes
0 answers
695 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 ...
CoryG's user avatar
  • 559
11 votes
0 answers
98 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 ...
Daniela's user avatar
  • 111
11 votes
0 answers
667 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 ...
Jonghyun Kim's user avatar
9 votes
0 answers
785 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}...
Sam Jaques's user avatar
  • 1,202
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" - ...
Zachary's user avatar
  • 177
9 votes
0 answers
458 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 ...
user avatar
8 votes
0 answers
287 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 ...
caesar's user avatar
  • 315
6 votes
0 answers
99 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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
5 votes
1 answer
100 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, ...
cryptolearner's user avatar
5 votes
0 answers
230 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 ...
Shara's user avatar
  • 171
5 votes
0 answers
92 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 ...
M.Z.'s user avatar
  • 155
5 votes
0 answers
274 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 $(-\...
Naruto999's user avatar
  • 436
5 votes
0 answers
120 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, ...
user avatar
5 votes
0 answers
692 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 ...
user222134's user avatar
5 votes
0 answers
467 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, ...
Rohit Khera's user avatar
5 votes
0 answers
3k 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 ...
preethi's user avatar
  • 889
4 votes
0 answers
377 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 ...
Maarten Bodewes's user avatar
  • 93.2k
4 votes
0 answers
87 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 ...
MeV's user avatar
  • 149
4 votes
0 answers
398 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)...
OneUser's user avatar
  • 133
4 votes
0 answers
242 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 ...
Paul's user avatar
  • 243
4 votes
0 answers
255 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 ...
Miruna Rosca's user avatar
4 votes
0 answers
153 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^...
redcode's user avatar
  • 205
4 votes
1 answer
236 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?
Nathan Aw's user avatar
3 votes
0 answers
54 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 ...
Tarick Welling's user avatar
3 votes
0 answers
128 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 ...
Marco's user avatar
  • 31
3 votes
1 answer
234 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 ...
Don Freecs's user avatar
3 votes
0 answers
69 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 ...
cryptobeginner's user avatar
3 votes
0 answers
238 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 ...
zbo's user avatar
  • 75
3 votes
0 answers
201 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 \...
Zoey's user avatar
  • 261
3 votes
0 answers
228 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 ...
mostlycryptic's user avatar
3 votes
0 answers
165 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 ...
a196884's user avatar
  • 381
3 votes
0 answers
190 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 + ...
filter hash's user avatar
3 votes
0 answers
89 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 ...
Severin's user avatar
  • 31
3 votes
0 answers
58 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 < ||...
Bean Guy's user avatar
  • 742
3 votes
0 answers
144 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 ...
Bean Guy's user avatar
  • 742
3 votes
0 answers
139 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 ...
Alex Ideal's user avatar
3 votes
0 answers
261 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 ...
gorte's user avatar
  • 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?
user47167's user avatar
3 votes
0 answers
196 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. ...
Bartolinio's user avatar
3 votes
0 answers
130 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 ...
Olivier's user avatar
  • 31
3 votes
0 answers
127 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
abdul rahman taleb's user avatar
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 ...
fakub's user avatar
  • 181
3 votes
0 answers
158 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 ...
oRinga's user avatar
  • 73
3 votes
0 answers
107 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 ...
Hilder Vitor Lima Pereira's user avatar
3 votes
0 answers
348 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 ...
Hamidreza's user avatar
  • 1,029
3 votes
0 answers
63 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 ...
dmnte's user avatar
  • 51
3 votes
0 answers
259 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 (...
Leafar's user avatar
  • 325
3 votes
0 answers
85 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 ...
user avatar
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 ...
cygnusv's user avatar
  • 5,002