# Questions tagged [lattice-crypto]

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

146 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 ...
672 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 ...
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 ...
661 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 ...
572 views

605 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 ...
453 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,  and , for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
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 ...
331 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 ...
79 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 ...
112 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, ... 239 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 ...
254 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 ...
149 views

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 ...
57 views

236 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 ...
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?
195 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. ...
120 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 ...
362 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)...
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 ...
157 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 ...
92 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 ...
343 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 ...
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 ...
243 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 (...
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 ... 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 ...
40 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, ...