As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [lattice-crypto]

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

48 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 ...
540 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 ...
1k 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 ...
804 views

1k views

### How to find the value of a vector modulo a basis in lattice-based cryptography

In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance: $\psi \leftarrow \psi' \mod B$ Taken from page 69 of ...
206 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 ...
1k views

164 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$, ...
117 views

### How does the 'Flatten' function reduce the coefficients of a vector/matrix?

Seen here, at the bottom of page 5, $\operatorname{Flatten}(\vec{a})$ is defined as: $\operatorname{Flatten}(\vec{a})=\operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1}(\vec{a}))$ For an n-...
703 views

519 views

### Bit decomposing a polynomial in BGV cryptosystem

I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a ...
1 vote
129 views

### NTRUEncrypt fails on complex algebra

I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the ...
1 vote
87 views

### value bound of r⋅e for LWE Decryption correctness

For LWE decryption, Someone told me that If we can bound r⋅e by q/4 then we can retrieve M by checking if this is closer to <...
1 vote
107 views

### How long time per operation to crack Kyber1024 compared to AES256 for quantum computers?

How long time does quantum computers take per operation when search the key of Kyber? Grover's algorithm weakens 256-bit AES to 128-bit security, quantum computers at most take 2^128 operations to ...
1 vote