Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
81 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 $...
user avatar
  • 141
2 votes
0 answers
37 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 &...
user avatar
  • 21
1 vote
1 answer
47 views

Errors for $\mathsf{LWE}$

Why do we take Gaussian-like errors in $\mathsf{LWE}$? Why for example we don't take uniform errors?
user avatar
  • 345
0 votes
1 answer
25 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?
user avatar
  • 345
0 votes
0 answers
19 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 ...
user avatar
  • 33
1 vote
0 answers
55 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 ...
user avatar
0 votes
0 answers
17 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 ...
user avatar
4 votes
1 answer
144 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 ...
user avatar
  • 9,596
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 ...
user avatar
0 votes
0 answers
13 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 ...
user avatar
  • 872
1 vote
1 answer
64 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 ...
user avatar
1 vote
1 answer
40 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 &...
user avatar
1 vote
1 answer
78 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$ ...
user avatar
2 votes
1 answer
32 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. ...
user avatar
  • 349
1 vote
0 answers
29 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 ...
user avatar
  • 249
0 votes
1 answer
63 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 ...
user avatar
  • 11
2 votes
0 answers
88 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. ...
user avatar
  • 390
1 vote
0 answers
45 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 ...
user avatar
2 votes
0 answers
50 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 ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
1 vote
0 answers
32 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 ...
user avatar
1 vote
1 answer
56 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}...
user avatar
1 vote
1 answer
48 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 ...
user avatar
  • 349
2 votes
0 answers
39 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 ...
user avatar
0 votes
1 answer
46 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?
user avatar
  • 345
2 votes
1 answer
57 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_{...
user avatar
  • 349
2 votes
1 answer
71 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 ...
user avatar
  • 345
1 vote
1 answer
85 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 ...
user avatar
0 votes
1 answer
72 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 ...
user avatar
  • 33
2 votes
1 answer
66 views

Trapdoor recovery from lattice-based preimage sampling

[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 ...
user avatar
  • 803
1 vote
1 answer
35 views

Can I find GCK-solution with add-form of few functions?

I know that it is hard that find a small $x$ when we know $(A,Ax), Ax=f(x)$ if is GCK on the cyclic lattice. Then is it hard to find small x_i when we know $(A,X)$ that $$X \leftarrow A_1\cdot x_1 + \...
user avatar
2 votes
1 answer
94 views

How can CPA-secure LWE cryptosystem be broken by an active attacker?

The LWE-cryptosystem is only CPA-secure as for example stated in A Decade of Lattice-Based Cryptography. Consider the following system described there (Section 5.2) The secret key is a uniform LWE ...
user avatar
2 votes
1 answer
95 views

What is the fastest way to check whether a given vector is the shortest in a lattice?

Given a lattice L and a vector $v_1$ claimed to be the shortest, what is the fastest way to check/verify whether $v_1$ is indeed the shortest in the lattice?
user avatar
3 votes
1 answer
170 views

Why are the parameters (such as modulus and dimension) of homomorphic encryption so large?

Compared with the common lattice-based PQC schemes, the modulus $q$ and dimension $n$ of homomorphic encryption are so large. For example, in Kyber, $n=256, n \times k = \{512,768,1024\}$, $q = 12289$...
user avatar
2 votes
2 answers
85 views

LWE - Encrypting/Decrypting messages bigger than 1 bit

I'd like to know if LWE (and its variants: RLWE and MLWE) can cipher messages bigger than 1 bit. Is it possible? I didn't find any reference yet. Could you explain it to me or give some good ...
user avatar
1 vote
0 answers
55 views

Current research problems in Lattice based Crypto [closed]

I am looking for research problems in lattice based Crypto. Can anybody help?
user avatar
  • 137
4 votes
2 answers
223 views

Testing of PQC NIST round3 submissions

I am new to this field and have some concerns regarding PQC; How does NIST do a comparison that a particular algorithm is efficient and its security can not be broken by future quantum attacks? I am ...
user avatar
1 vote
0 answers
61 views

The relationship between root hermite factor and bit-security?

The root hermite factor corresponding to an bit-security level, such as 1.0045 corresponding to 128-bit security. What is the root hermite factor corresponding to 100-bit, 160-bit, 180-bit security? ...
user avatar
3 votes
1 answer
78 views

What are Practical Primitives based on Lattices, LWE and FHE?

Lattice-based cryptography is being used for several primitives and applications. I know there are newer works for PIR, PSI, ORAM that have seen tremendous improvements due to FHE. In some cases, FHE ...
user avatar
0 votes
0 answers
23 views

How to estimate the parameter of a lattice signature scheme with lossy reduction?

The parameter of a lattice signature scheme DAZ19 with tight reduction can be choosed to make the underlying hardness problem intractable. How to estimate the parameter of a lattice signature scheme ...
user avatar
1 vote
0 answers
55 views

Key Switching Error in CKKS

I believe I am misunderstanding something about the bounds derived for the key switching error in CKKS. I will refer to the initial paper, but similar bounds have been derived in all variants I have ...
user avatar
  • 8,404
3 votes
0 answers
119 views

The decryption correctness of RLWE based Encryption

I get stuck in the proof of decryption correctness in RLWE based Cryptosystem. To state where I am , let me show the full scheme first. The image is from chapter 3.2 of this paper. And the decryption ...
user avatar
  • 33
1 vote
0 answers
62 views

Equivalence between search-LWE and decision-LWE

Are there any constraints when it comes to proving that search-LWE and decision-LWE are equivalent? Should we assume that the module $q$ is prime when switching from one version to another? Please ...
user avatar
  • 345
2 votes
1 answer
53 views

A newbie question about NTRUEncrypt: small r(x) and closest vector problem

In NTRUEncrypt with system-wide parameters $(N, p, q)$, let Bob's public key be $h(x).$ To encrypt plaintext $m(x)$ whose coefficients are small, Alice needs to generate a random $r(x),$ whose ...
user avatar
5 votes
0 answers
68 views

Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?

I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge. Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to ...
user avatar
  • 8,404
1 vote
1 answer
81 views

Why $q$ in LWE must be polynomial in $n$

I am wondering why the modulus $q$ in the LWE problem has to be polynomial in $n$. Another question is whether one can take it to be an arbitrary integer instead of a prime number.
user avatar
  • 345
1 vote
1 answer
89 views

How to prove the inequalities of q-ary lattice determinant?

for $A\in{Z_q^{n*m}}$ and $A^{'}\in{Z_q^{m*n}}$,we have $det{({\land}_q^{\bot}(A))}{\le}q^n$ and $det{({\land}_q(A^{'}))}{\ge}q^{m-n}$ if q is prime,and A,A' are non-singular in the finite field $...
user avatar
  • 33
3 votes
1 answer
304 views

How to decide if an element is a public key in NTRU encryption scheme?

First, I'm using the settings of https://en.wikipedia.org/wiki/NTRUEncrypt, with $L_f$ set of polynomials with $d_f+1$ coefficients equal to 1, $d_f$ equal to $-1$ and the remaining $N-2d_f-1$ equal ...
user avatar
  • 325
0 votes
1 answer
67 views

Volume $q^n$ of a dual q-ary lattice in MR09

Given a matrix $\mathbf{A} \in \mathbb{Z}^{n \times m}$, $m$ sufficiently large with respect to $n$ and prime $q$. The rows of $\mathbf{A}$ are linearly independent with high probability. In MR09 the ...
user avatar
  • 3
0 votes
1 answer
85 views

NTL: Solve the closest vector problem for non-square matrix using LLL/Nearest Plane Algorithm

Assume I have a matrix $A \in \mathbb{Z}^{m \times n}$, $m > n$, which forms a basis of a lattice. Given a vector target vector $t = Ax + e$, $t,e \in \mathbb{Z}^m$,$x \in \mathbb{Z}^n$, I want to ...
user avatar

1
2 3 4 5
9