# Questions tagged [lattice-crypto]

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

497 questions
Filter by
Sorted by
Tagged with
1 vote
250 views

### What are limits of Modulus Switching in BFV encryption?

I want to understand the limits of modulus switching in BFV. Lets assume $q$ represents ciphertext modulus and $t$ represents plaintext modulus. $q$ is set to a $60$ bit value and $t$ is set to $20$ ...
42 views

### Duality Results for Some Module Lattices

Let $R$ be the ring of integers of a cyclotomic field $\mathbb{Q}(\zeta_n)$, where $n$ is a power of two, and $\boldsymbol{a} \in R_{q}^{m}$, for $m\in\mathbb{Z}^+$, $q\in\mathbb{Z}_{\geq2}$ prime. ...
1 vote
31 views

### Sampling from ring of integers

There is a statement in the paper "Asymptotically Efficient Lattice-Based Digital Signatures" by Lyubashevsky and Micciancio that says that "it is important that the ring of integers of ...
215 views

### LWE-search to SVP reduction

So for my diploma thesis I'm writing about Regev's LWE cryptosystem from his original 2005 paper. I'm done with with correctness and security (only reduction from LWE-search via average-to-worst and ...
111 views

### How to extract witness from a non-interactive lattice-based proof?

I'm trying to figure out how to construct an extractor for a non-interactive lattice-based proof. Specifically, I'm curious about the Fiat-Shamir transform applied to a five-move interactive protocol. ...
1 vote
91 views

### Working the multivariate Coppersmith algorithm

I recently studied the multivariate Coppersmith algorithm. Let $f(x)$ be $n$-variate polynomial over $\mathbb{Z}_p$ for some prime $p$. Informally, the multivariate Coppersmith's theorem stated that ...
132 views

### How can BDD solve LWE if the matrix A is full rank?

I'm trying to figure out exactly how solving different generic lattice problems can solve LWE, and in particular, BDD. Everything I've found says that since an LWE sample is $(A,b=As+e\mod q$), then ...
1 vote
41 views

### How is GGH's bad basis public key safe from gram–schmidt orthogonalization?

I'm reading about lattice based cryptography. In my reading I read of gram–schmidt orthogonalization. Which allows for turning a bad basis into a good basis, or at least an orthogonal one. Now I'm ...
1 vote
57 views

### Performance of elliptic curve Diffie-Hellman vs NIST-PQC finalist KEMS

I am looking for performance measurements in cycle counts for an implementation of the elliptic curve Diffie-Hellman for curve, ed25519. Ideally, the cycle counts ...
1 vote
76 views

104 views

### How is it legal to use a rounded Gaussian for LWE?

As far as I understood, in Regev's initial paper, the error distribution was first constructed as follows: Then rounded in the following way: Using this distribution, the reduction in the theorem ...
1 vote
114 views

### Frobenius inner product polynomial rings

I'm trying to implement the zero-knowledge proof presented in this paper. The proof has a rejection step (page 14), which can be computed as follows: Where B and Z are in $R^{m \times n}$ for some ...
86 views

### How to explain that the closest vector to $0$ is $0$ in lattice?

There is a sentence in Oded Regev'lecture note that "$0$ is part of any lattice and hence the closest vector to $0$ is $0$ itself!". I'm having trouble understanding it. Can someone help me ...
[GPV] and [MP] (references below) give constructions of the trapdoor function defined by $$f_{\mathbf A} (\mathbf x) = \mathbf A \mathbf x,$$ where $\mathbf A \in \mathbb Z_q^{n \times m}$ is ...