# Questions tagged [lattice-crypto]

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

544 questions
Filter by
Sorted by
Tagged with
93 views

### Unable to retrieve the binary string using LWE and Lattice-based decryption

I am new to this encryption scheme, so I may not be exactly sure of its implementation. I have a list of (u, v) ciphertext pairs to decrypt, each of them are 1-bit. ...
1 vote
45 views

### Why the refresh (modulus and key switching) is required in BGV after addition?

I am reading the BGV paper. On page 18, after addition, the protocol will also refresh (modulus and key switching), may I ask why is this required? It seems to me that I can still use the same secret ...
1 vote
60 views

### Definition of Dual Lattice

1- Can someone explain why we have the definition of dual of a lattice like $\Lambda^*=\{\vec{v}\in span(\textbf{B}): \langle \vec{v},\vec{x} \rangle \in \mathbb{Z}, \forall \vec{x} \in \Lambda\}$. 2-...
1 vote
61 views

### Sigma parameter from Trapdoors for Lattices

In the document Trapdoors for Lattices, section 5.4 Gaussian Sampling, they introduce the parameter $\sqrt{\Sigma_{\bf G}}$, which is related to the lattice $\Lambda^\perp(\bf G)$. They use it as a ...
77 views

### Arithmetic in Cyclotomic Number Rings with Shoup's Number Theory Library (NTL)

I wish to do arithmetic on elements in an integer subring of a cyclotomic number field, i.e, in $\mathcal{O}_K = \mathbb{Z}(\zeta) \cong \mathbb{Z}[X] / <\phi_m(x)>$ where $\zeta$ is a root of ...
265 views

### NTRU Cryptosystem: Why "rotated" coefficients of key f work the same as f

In the NTRU cryptosystem, we can use a randomly generated polynomial f that is inversible under modulo p and q to encrypt and decrypt our plaintext. While studying this system, I attempted to ...
1 vote
67 views

### Understanding Gentry's initial FHE construction based on ideal lattices

I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
2k views

1 vote
24 views

### Where do we put known bits of nonce when performing lattice attack on ECDSA?

I have read so many papers and posts about lattice attacks on ECDSA but none of them used an example of different MSB values for k but instead they all used fixed MSB. So here i am trying to ...
1 vote
31 views

### Is there a many-to-one reduction from GapSVP to GapCVP?

I was wondering if by now any poly-time Karp reduction between GapSVP and GapCVP (exact or approximate) exist. I know of the Cook reduction between these problems, but I couldn't find anything about ...
1 vote
124 views

### Is there an efficient way to check if a lattice has a point with all non-zero components?

Given a basis $\{v_1,\dots,v_k\}$ for a $q$-ary lattice $L$ in ${\mathbb Z}_q^n$, is there an efficient (deterministic/randomized) way to find a point in $L$ with all non-zero components, or decide ...
15 views

### [error reducing techinique in lattice based commitment]

I am aware there are many techniques to reduce the error of lattice-based homomorphic encryption. But is there any technique to deal with lattice-based homomorphic commitment, e.g., More Efficient ...
1 vote
124 views

### True Lovàsz condition and definition of a LLL-reduced basis

I am studying the Shortest Vector Problem and I have some troubles understanding the actual Lovàsz condition used in the LLL algorithm. On the one hand, the original LLL article, the Springer book &...
91 views

1 vote
51 views

### Can lattice attack work MSB or LSB are unkown but 16 bytes of private key are known?

I have been reading about lattice attack on ECDSA when partial bits of nonce are known for amount of signatures, So i went through some source code trying to understand how it works. First of all, ...
2k views

### Is lattice encryption susceptible to Grover's algorithm?

So Grover's algorithm, also known as the quantum search algorithm, can find an entry, with a high probability, in an unstructured database. Well can't we consider the basis of a lattice problem an ...
38 views

### What are the implications for the proof when we substitute matrix multiplication with a bitwise XOR operation in Definition 5.1 (LWE degree-k PRF)?

In the paper located at https://eprint.iacr.org/2011/401.pdf, suppose we replace matrix multiplication with bitwise XOR operations in Definition 5.1 to create an LWE degree-k PRF. I'm seeking ...
1 vote
88 views

### Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

I came upon the following hash function (pseudo-code): ...
78 views

### $\epsilon$ parameter choice in lattice-based schemes

I am trying to implement Pei10 and BB13, but I am confused about what concrete parameters to use. In Pei10, Algorithm 1 takes a rounding parameter $r = \omega(\sqrt{\log n})$ as parameter, but it does ...
64 views

### Discrete Gaussian distribution on a lattice vs. the periodic Gaussian function on a lattice

Gaussian distribution on lattices generally seems esoteric (at least for me, for now). My question is: Does Gaussian distribution on a lattice mean to add a Gaussian noise on a single point of a ...
1 vote
In the paper GM18, they say that the sampling algorithm, SampleG, is shown in Figure 2. It takes as input a modulus $q$, an integer variance $s$, a coset $u$ of $\Lambda^{\perp}(g^T )$, and outputs a ...