# Questions tagged [lattice-crypto]

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

63 questions
Filter by
Sorted by
Tagged with
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 ...
• 629
675 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
2k 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 ...
• 609
1k views

• 1,460
685 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 ...
• 43
323 views

### Is LWE easy when the matrix $A$ is sparse?

Recall that the LWE problem is the following. LWE problem. Let $q$ be a prime, let $\chi$ be a distribution of small elements over $\mathbb{Z}/q$, and let $n,m$ be two integers (dimensions of vectors ...
• 155
134 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 ...
• 219
220 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 ...
• 819
239 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 ...
• 9,682
1 vote
991 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,444
11k views

### Polynomial-time Quantum Algorithms for Lattice Problems

A new paper, by Yilei Chen, whose title is Quantum Algorithms for Lattice Problems (https://eprint.iacr.org/2024/555) appeared on eprint and it claims to solve hard lattice problems, such as the ...
6k views

### What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

In An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor, the author claims they give a polynomial-time quantum algorithm for solving the Bounded Distance ...
• 797
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 ...
• 448
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,696
8k views

### Kyber and Dilithium explained to primary school students?

Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?
• 371
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?
3k views

• 919
2k 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?
• 143
214 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 ...
• 322
281 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
310 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$, ...
• 155
317 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,501
545 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
248 views

• 133
2k views

### Understanding Unique-SVP and Kannan's Embedding

I am trying to understand the Kannan embedding technique. But I am confused about the formation of the B' and the finding of the short vector inside that basis. How does this basis matrix in the ...
290 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. ...
• 219
232 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 ...
• 919
125 views

### Question about the description from ring SIS to SIS in the survey paper: A Decade of Lattice Cryptography

I am currently reading "A Decade of Lattice Cryptography" At page 30, section 4.3.2, it descrip left multiplication by any fixed ring element a It mention something about curcilant matrix ...
• 361