Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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
1 answer
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
1 answer
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 ...
0 votes
1 answer
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?
2 votes
1 answer
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
0 answers
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
1 answer
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$...
4 votes
1 answer
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
2 votes
1 answer
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
2 answers
108 views

LWE with a binary matrix A

In LWE, we know that given reasonable public parameter $A\in \mathbb{Z}_q^{n\times \lambda}$, secret $s\in \mathbb{Z}_q^{\lambda}$ and noise $e\in \mathcal{X}^{n}$, random $r\in \mathbb{Z}_q^{n}$, $(A,...
1 vote
0 answers
51 views

Montgomery algorithms for Lattice based schemes [closed]

Why most of Lattice based scheme use Montgomery Multiplication algorithm?
0 votes
0 answers
35 views

The special case of NTRUEncrypt when N = q

I've found this task in the "Introduction Mathematical Cryptography by Jeffrey Hoffstein": The guidelines for choosing NTRUEncrypt public parameters (N, p, q, d) in-clude the assumption that ...
  • 1
0 votes
0 answers
23 views

The proof of the NTRUMLS key generation parameters are valid

I'm reading "An Introduction to Mathematical Cryptography" by J.Hoffstein. I'm stuck with the task on NTRUMLS(blue rectangle): I was wondering if there was a mistake in the assignment. The ...
  • 1
2 votes
1 answer
102 views

LWE problem with a sparse matrix

Is the LWE problem easy when the matrix $A$ is sparse? Recall that the LWE problem is the following: Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$ elements over $\mathbb{Z}/q$, ...
  • 113
0 votes
1 answer
43 views

Proving these two distributions are the same for LWE reduction

As part of a reduction I'm trying to construct, I want to show that the two terms described at the bottom are identically distributed, but I'm not sure if this is correct and I cannot seem to prove ...
  • 311
1 vote
0 answers
82 views

Which quantum resistant digital signature algorithm would you use and why (If you had to pick one now)? [closed]

Context: Many widely used public-key cryptographic schemes have been designed based on the difficulty of factoring and similar problems. That includes RSA, the Diffie-Hellman Key Exchange, ECDH, ...
2 votes
0 answers
44 views

Noise flooding with Renyi divergence

According to this question, I found papers that deal with noise flooding with Renyi divergence. However, the answer is still unclear to me on how to use Renyi divergence on the noise flooding ...
  • 21
1 vote
1 answer
97 views

Why lattice based cryptographic schemes usually are not bandwidth efficient?

The question is mainly stated in the title. I am new to lattices and I have a basic understanding of them but not something in depth. I was watching a presentation of of a VSS (Verifiable Secret ...
  • 671
3 votes
1 answer
64 views

In reduction from search LWE to decsion LWE why sampling needs to repeat a polynomial number of times?

I've been reading through MIT's lecture notes on learning with errors here, and I'm trying to understand the reduction from Search LWE to Decision LWE, as described there in Section 2.7, "...
  • 311
1 vote
1 answer
72 views

Why do we need the leftover hash lemma for this hybrid proof (Learning with Errors)?

I've been reading about Learning with Errors here. On p. 7 there's a proof for the security of the PKE scheme, that goes through the leftover hash lemma, in order to prove that: $$ (pk, Enc(0))\equiv (...
  • 311
3 votes
1 answer
65 views

How to solve LWE/RLWE under partial information about $s$

For LWE/RLWE, it's difficult to find $s$ from $\left(A, b = As + e\right)$. But if the partial information of $s$ is leakaged, such as partial $s$ or parity of $s$, how easy would it become to solve ...
1 vote
2 answers
61 views

Why use negacyclic convolutions for polynomial multiplication instead of regular convolutions?

When multiplying polynomials from $\mathbb{Z}_q[X] / (X^n-1) $, the discrete NTT is used because: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \...
2 votes
1 answer
156 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 ...
2 votes
2 answers
142 views

Example of bad basis for lattices (worst-case for LLL)

Summary. Given some dimension $n$ (say $n=50$), is it possible to describe explicitly a lattice $L$ and a basis $B$ of $L$ such that $$ \frac{ \| LLL(B)_1 \| }{ \lambda_1(L) } > 1.02^n $$ where $...
  • 151
2 votes
1 answer
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
1 answer
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
2 votes
2 answers
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
0 votes
0 answers
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
0 answers
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
0 votes
0 answers
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
4 votes
1 answer
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
12 votes
1 answer
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 ...
0 votes
0 answers
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
1 answer
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
1 answer
67 views

On the definition of Gap SVP

I am confused on the definition of GAP SVP. The problem states that for a fixed $\gamma \geq 1$, given a basis $B$ of a lattice and a $d>0$, GAPSVP asks to determine if $\lambda\leq d$ or $\lambda &...
1 vote
1 answer
140 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$ ...
  • 239
2 votes
1 answer
34 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. ...
  • 381
1 vote
0 answers
30 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 ...
  • 249
0 votes
1 answer
94 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 ...
  • 11
2 votes
0 answers
95 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. ...
  • 412
1 vote
0 answers
66 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 ...
2 votes
0 answers
67 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
0 answers
30 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
0 answers
42 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
1 answer
64 views

Reducing a lattice basis with too many basis vectors

Suppose I have a basis $B$ of an $n$-dimensional lattice $L\subseteq\mathbb{Z}^n$ and $B$ has $n$ vectors. Now I take another $v\in \mathbb{Z}^n\setminus L$ and I define a new lattice $L'=L+\mathbb{Z}...
1 vote
1 answer
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
3 votes
0 answers
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 ...
0 votes
1 answer
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
2 votes
1 answer
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
2 votes
1 answer
79 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 ...
  • 365

1
2 3 4 5
9