# 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
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,646
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 ...
• 559
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 ...
• 111
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 ...
• 477
785 views

• 436
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, ...
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 ...
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, ...
• 678
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 ...
• 889
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 ...
• 93.2k
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 ...
• 149
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)...
• 133
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 ...
• 243
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 ...
153 views

• 149
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 ...
• 31
58 views

• 341
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 ...
• 167
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?
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. ...
• 247
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 ...
• 31
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$ ...
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
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 ...
• 73
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 ...
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 ...
• 1,029
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 ...
• 51
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 (...
• 325
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 ...
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 ...