# Questions tagged [lattice-crypto]

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

431 questions
Filter by
Sorted by
Tagged with
52 views

### When will $R_q=\mathbb{Z}[X]/\langle X^n+1\rangle$ be a field? [closed]

When will $R_q=\mathbb{Z}[X]/\langle X^n+1\rangle$ be a field?
1 vote
84 views

### Encryption and decryption for LWE

For https://asecuritysite.com/public/lwe_ring.pdf#page=9 , could anyone explain how the encryption and decryption for LWE work ? When I do more reading on https://summerschool-croatia.cs.ru.nl/2015/...
• 111
1 vote
70 views

### Coefficient Growth

In this survey, I don't understand the necessary of coefficient (paragraph 4.1.2) growth and the choice of $X^d\pm 1$ or $X^d \pm X^{d/2} +1$, since later introduces $q$ which doesn't mention the ...
• 171
27 views

### Comparison of Complete NTT and Incomplete NTT Multiplication

is the complete NTT is the fastest algorithm to multiply polynomials or there are hybrid versions that are faster than complete NTT multiplication?
• 171
72 views

### Statistical Distance and Learning with Rounding

Given an integer $b$ modulo a prime $q$, one can define a `rounding’ function $\lfloor b\rceil_p$ for a prime $p$, $p<q$, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$...
• 381
1 vote
90 views

### Breaking RSA with P,Q LSB bits using LLL Lattice reduction

This question is someway correlated to Breaking RSA with P,Q LSB bits but more specific. I would like to use LLL to fully reconstruct P,Q given some LSB bits of P and Q in an arbitrary base B. Let's ...
• 31
1 vote
48 views

### Type 1 Trapdoor Sampling in LWE

In the BGN-like LWE cryptosystem, section $2.2$, we sample a $m \times m$ trapdoor matrix $T$ that is full rank such that $TA = 0 \pmod q$. Suppose that $q$ is prime so we are in a finite field: if $T$...
128 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$, ...
• 113
96 views

### How to choose the large noise when using noise flooding technique in FHE?

In LWE based multi party FHE schemes, the parties should choose a much larger noise when perform joint decryption. In this paper, the author just said that using noise flooding technique to avoid the ...
• 419
1 vote
108 views

• 151
61 views

### Paper "How to Meet Ternary LWE Keys": What is t and how is it used

I have read again and again this paper from A. May, but, probably because I am new to this field, I don't succeed in understanding the MEET-LWE part. In particular, in part 5 it states to choose a &...
• 51
1 vote
56 views

### Errors for $\mathsf{LWE}$

Why do we take Gaussian-like errors in $\mathsf{LWE}$? Why for example we don't take uniform errors?
• 365
62 views

### Solving $\mathsf{SVP}_{\gamma}$ in worst-case

What does it mean to solve $\mathsf{SVP}_{\gamma}$ in worst-case? Does it mean that the problem is solvable for any lattice we choose?
• 365
34 views

### Reference Implementation of RLWE-Based schemes?

Now RLWE-based Encryption scheme is so popular because of its post-quantum property and application in Homomorphic Encryption. I am trying to get more familar with RLWE-based Encryption by ...
• 49
1 vote
79 views

### Why there is so high computational cost of multiplication in Microsoft Seal?

I was doing some Microsoft Seal testing on my macbook pro (i7) and got following results Coefficient mod $q = 100$ bits and Polynomial degree $n= 8192$ Ciphertext-Plaintext multiplication takes 0.211 ...
• 239
35 views

### What is minimum size of polynomial modulus in Seal implementation of BFV?

Is there a way to get flexible parameters in Seal for batching? The issue is that for polynomial mod $n=4096$, the function I am computing has a multiplicative depth of $3~4$, to handle noise growth I ...
• 239
168 views

### What is the effect of low rank dual sublattices on the dual lattice attack on LWE?

In the dual lattice attack of Espitau, Joux and Kharchenko (On a dual/hybrid approach to small secret LWE), the authors propose distinguishing (and subsequently recovering secret values) of LWE ...
• 12k
2k views

### Current Consensus on Security of Lattice Based Cryptography?

In an edit to an answer by user forest, it was mentioned that there has been a new attack developed for lattice-based cryptography. I thought lattice-based cryptography is a fairly well established ...
21 views

### Using Coppersmith for a second trivariate polynomial

I have a trivariate polynomial whose roots I am interested. The polynomial has monomials in $\{X^4,X^2,X^2Y,X^2Z,1\}$. What is the best way to generate the lattice and apply $LLL$ so that I can get a ...
• 882
1 vote
152 views

### How lattices and LWE are connected?

I am a last-year master student in pure mathematics and I am working on my thesis. I am working on a connection between lattice-based encryption and Ring LWE and between Ring LWE and Homomorphic ...
1 vote
67 views

• 725
1 vote
54 views

### RLWE with invertible elements

Let $R = \mathcal{O}_K$ be the ring of ingtegers of $K$, where $K$ is an algebraic number field, and $q$ a modulus. Let $\chi$ be some error distribution used to sample an element $e$. A primal RLWE ...
• 381
48 views

### Paper "How to Meet Ternary LWE Keys": Why can Odlyzko's hash function not be used to construct the mitm lists recursively?

In Alexander May's Paper "How to Meet Ternary LWE Keys", Alexander May writes the following about combining representation techniques with Odlyzko's locality sensitive hash function (Page ...
48 views

### Randomness space of encryption function

I was reading the definition of Fujisaki-Okamoto transform, and I found this: What does it mean the "randomness space" of the function Enc in the PKE setting?
• 365
62 views

### The significance of duals in RLWE

In an algebraic number field, an ideal $I$ in the ring of integers $\mathcal{O}_K$ has dual $I^\vee = \{x\in\mathcal{O}_K\text{ : }T_{K/\mathbb{Q}}(xy)\in\mathbb{Z}\text{ for all }y\in I\}$, where \$T_{...
• 381