Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
497
questions
1
vote
1
answer
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$ ...
- 249
2
votes
1
answer
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. ...
- 381
1
vote
0
answers
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 ...
- 259
0
votes
1
answer
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 ...
- 11
2
votes
0
answers
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. ...
- 528
1
vote
0
answers
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 ...
- 149
2
votes
0
answers
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,005
1
vote
0
answers
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 ...
- 185
1
vote
0
answers
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 ...
- 347
1
vote
1
answer
76
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,005
1
vote
1
answer
63
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
60
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 ...
- 347
0
votes
1
answer
62
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?
- 415
2
votes
1
answer
82
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
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 ...
- 415
1
vote
1
answer
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 ...
0
votes
1
answer
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 ...
- 65
2
votes
1
answer
140
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 ...
- 835
1
vote
1
answer
37
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 + \...
- 31
2
votes
1
answer
185
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 ...
- 347
2
votes
1
answer
120
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?
- 41
3
votes
1
answer
235
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$...
- 31
2
votes
2
answers
225
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 ...
- 33
1
vote
0
answers
56
views
Current research problems in Lattice based Crypto [closed]
I am looking for research problems in lattice based Crypto. Can anybody help?
user96171
4
votes
2
answers
262
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 ...
- 41
1
vote
0
answers
115
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?
...
- 41
3
votes
1
answer
94
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 ...
- 249
1
vote
0
answers
229
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 ...
- 10.8k
3
votes
0
answers
190
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 ...
- 73
2
votes
0
answers
106
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 ...
- 415
2
votes
1
answer
76
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 ...
- 41
5
votes
0
answers
85
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 ...
- 10.8k
1
vote
1
answer
91
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.
- 415
1
vote
1
answer
145
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
$...
- 65
3
votes
1
answer
323
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 ...
- 325
0
votes
1
answer
119
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 ...
- 3
0
votes
1
answer
166
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 ...
- 347
24
votes
3
answers
5k
views
What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?
In An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor, the author claims they give a polynomial-time quantum algorithm for solving the Bounded Distance ...
- 777
3
votes
1
answer
134
views
Lattice-based cryptography: secret from Gaussian distribution chi
In a lecture, by Chris Peikert (link 40:20), he showed more efficient cryptosystems that have the secret be drawn from the Gaussian error distribution $\chi$.
In the lecture he said "some ...
- 155
1
vote
0
answers
151
views
Finding a basis for q-ary lattices
For $A\in \mathbb{Z_q}^{n\times m}$, where $m \geq n$, consider the given two q-ary lattices
\begin{align}
\Lambda_q^{\bot}{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: A\mathbf{x} = \mathbf{0}\text{ ...
2
votes
1
answer
418
views
SIS vs LWE Problem
The Ajtai one way function is defined by
$$f_A(x)= Ax \; mod\; q $$ where the x $\in \{0,1\}^m$ and A $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ is one way function ( Ajtai 96)
While the Regev One way ...
2
votes
2
answers
108
views
Constraints on q for q-ary lattices?
In lattice cryptography, people often work with q-ary lattices so that we can use the hardness of short integer solution (SIS) and learning with errors (LWE). I saw in some notes that sometimes we ...
- 155
1
vote
0
answers
138
views
Sentinel ("trick") values for lattice attack on DSA with biased k (MSB)
I'm studying lattice attack using this sage script. There are 2 options in script: LSB and MSB. The most interesting option for me is MSB. It recovers private key with less then 100 signatures ...
- 11
2
votes
2
answers
386
views
Question about coefficient of ECDSA in lattice attack
Update: I made my lattice attack worked finally. As the actual reason is quite complicated I decide to write an answer below to describe how it worked so anyone with similar question might get ...
- 49
4
votes
1
answer
207
views
Prove that a small Ring-LWE secret is unique
I just want to know whether my proof is correct, which is about proving that if the Ring-LWE secret is small, then it is unique. Before giving my proof, here is a fact:
Fact 1: $\Pr [\Vert r \Vert_\...
3
votes
0
answers
123
views
q-ary lattices - proof of dual upto scale
Two lattices are defined as following:
\begin{align}
\Lambda_q^{\bot}{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: A\mathbf{x} = \mathbf{0}\text{ mod }q\} \\
\Lambda_q{(A)} & = \{\mathbf{x} \in \...
- 259
2
votes
0
answers
362
views
Schnorr RSA factoring (round 2)
Introduction
Earlier this year Claus Peter Schnorr claimed to have "broken RSA". The original paper was discussed in Does Schnorr's 2021 factoring method show that the RSA cryptosystem is ...
- 121
3
votes
1
answer
230
views
SIS without the modulus
Consider the following modification to the Short Integer Solution (SIS) problem:
Let $n$ be an integer and $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$ be functions of $n$. Sample ...
- 141
0
votes
0
answers
62
views
Is my proof about uniqueness of ring-LWE secret correct?
Suppose that $n$ is a power of two, $q=3\pmod 8$, prime and $R=\mathbb{Z}[X]/(X^n+1)$. Denote $\Vert\cdot\Vert$ as the infinity norm in $R_q=R/qR$ on the coefficients of elements in $R_q$. The ...
1
vote
1
answer
211
views
Lattice in Sage: Generate matrix A from a basis S such that AS = 0 (mod q)
In Sage, there is a function: gen_lattice() that can generate a basis $$S \in \mathbb{Z}^{m \times m}_q $$ of a lattice $$\Lambda^\bot_q(A)$$, where $$A \in \mathbb{Z}^{n \times m}_q$$ is a random.
...
- 103