Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
573
questions
48
votes
3
answers
8k
views
Polynomial-time Quantum Algorithms for Lattice Problems
A new paper, by Yilei Chen, whose title is Quantum Algorithms for Lattice Problems (https://eprint.iacr.org/2024/555) appeared on eprint and it claims to solve hard lattice problems, such as the ...
- 1,276
3
votes
4
answers
711
views
Why Module-LWE and not Ring-LWE?
I am trying to understand the NIST-submissions for post-quantum cryptography a bit better, and I noticed that the submissions from the CRYSTALS-family in particular is based on Module-LWE.
I ...
- 457
0
votes
0
answers
34
views
Reaching the bound of Boneh and Durfee Attack
According to the paper, theoretically,we can get $\delta=0.292 \lt 1-\frac{1}{\sqrt{2}}$,but how to set the lattice and implement it in sagemath? I generated some data
by
...
- 23.9k
0
votes
0
answers
186
views
Is the cryptography scheme over lattice still secure？ [duplicate]
In https://eprint.iacr.org/2024/555, the author proposed a quantum algorithm to solve LWE problem. How serious is its impact on the existing scheme over lattice.
1
vote
1
answer
65
views
LWE Decryption: Generating errors for (c1, c2) that match binary message m
In the encryption process, the ciphertexts c1 and c2 are added to errors e1 and ...
CommunityBot
- 1
1
vote
1
answer
102
views
Degree of inverse of f in NTRU?
In NTRU, we know that $f$ is a ternary polynomial in the ring $$R=\frac{\mathbb{Z}_q[x]}{x^n-1}.$$
Here $f$ has $d+1$ coefficients 1 and $d$ coefficients $-1$ and rest are zero.
For computing the ...
- 23.9k
1
vote
0
answers
42
views
The correctness of NTT algorithm
When directly invoking the ntt and invntt function in Dilithium's code with any polynomial $a \in R_q$, I get a unexpected running result: $NTT(a) \neq iNTT(NTT(a))$.
And in the test code of Dilithium(...
- 92.6k
2
votes
2
answers
93
views
Probabilistic proof of multiplying two elements from non-prime finite field
I was reading this paper, and there, they use the ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$ for all their operations. And that looks like a construction of finite field $\mathbb{F}_{\...
- 147
1
vote
1
answer
71
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 ...
CommunityBot
- 1
2
votes
1
answer
48
views
How does linearity work with SWIFFT?
I read that SWIFFT is a linear hash function, but I don't understand what this means. The obvious interpretation is that if you have inputs $X1, X2$ each of which is an array of 16 64-dimensional ...
- 13k
3
votes
1
answer
124
views
High Hamming Weight Attack on Kyber
I was reading LAC (https://eprint.iacr.org/2018/1009.pdf). They mention about high-hamming weight attacks on the Centered Binomial Distribution (CBD). To counter this, they propose CBD with fixed ...
- 23.9k
2
votes
1
answer
55
views
The necessity for lattice reduction in LWE
I am trying to understand how exactly lattice reduction and LWE are linked.
The attacks on LWE I have seen all use lattice reduction in some way or another, dual attacks, uSVP type and so on.
Naively, ...
- 23.9k
1
vote
1
answer
68
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 ...
CommunityBot
- 1
0
votes
1
answer
33
views
Instantiation of norm bound in SIS
Recall Short Integer Solution:
$\textbf{SIS}_{n, q, \beta, m}$: Given $\textbf{A} \in \mathbb{Z}^{n\times m}_q$, $\vec{b} \in \mathbb{Z}^{n}$, find $\vec{z} \in \mathbb{Z}^{m}$ of norm $||z|| \le \...
- 390
0
votes
1
answer
43
views
Finding security constraints for different input domains of Ajtai functions
I know that the normal construction for Ajtai hash functions is as follows:
Pick $n, m, q \in \mathbb{Z}^+$ such that $n \log q < m < \frac{q}{2n^4}$ and $q = O(n^c)$ for some $c>0$, and some ...
- 13k
2
votes
1
answer
40
views
Initial approximation in CKKS Bootstrapping
In this CKKS bootstrapping paper https://eprint.iacr.org/2018/153 the authors use a Taylor expansion to approximate the complex exponential function within a small range. More precisely, for the input ...
CommunityBot
- 1
0
votes
1
answer
46
views
The proof of Claim 5.2 in the "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography"
When I'm reading this paper "On lattices, learning with errors, random linear codes, and cryptography" by O. Regev. I have trouble understanding the proof of claim 5.2.
"Hence, it is ...
- 23.9k
2
votes
1
answer
43
views
How to measure the denseness of Mod-LWR samples in some space?
I tried to understand how dense the Mod-LWR samples are in some space. I tried to see from a view similar to LWE, i.e. using GV-bound(maybe LPN is better example because GV-bound is for codes). But I ...
- 13k
1
vote
1
answer
98
views
Ring-LWE lattice cryptography and FFT Trick for $X^n+1$
in reference here the FFT trick for $X^n+1$ is discussed with reference to the Number Theoretic transformation. On page 5, the Chinese Remainder Theorem is used to define the mapping.
So far so good. ...
- 13k
3
votes
1
answer
74
views
How to reconstruct low order bits of $t$ of CRYSTALS-Dilithium from a small number of signatures?
In FIPS 204 (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf): "The vector $\textbf{t}$ is compressed in the actual public key by dropping the $d$ least significant bits from each ...
- 13k
15
votes
1
answer
1k
views
Impact of Ryan and Heninger's CRYPTO 2023 paper on post quantum cryptosystems
From Schneier's blog, which seems to have been written in response to a somewhat recent Quanta magazine article:
The winner of the Best Paper Award at CRYPTO this year (2023) was a significant ...
- 13k
2
votes
1
answer
71
views
Definition of Dual Lattice: $\vec{v}\in span_{\mathbb{R}}(\mathcal{L}(\mathbf{B}))$
Consider the definition of the dual lattice for a lattice $\mathcal{L}(\mathbf{B}_{m\times n})\in\mathbb{R}^{m}$ where $\mathbf{B}\in\mathbb{R}^{m\times n}$ and $n\leq m$ [sp2 Seminar, Luxembourg 2019,...
CommunityBot
- 1
0
votes
1
answer
89
views
Difference between Decryption-failure and Plaintext-checking oracles
I am reading this paper, which in the introduction, tells about two main types of key recovery SCAs :
Reaction_type SCAs, which uses a decryption failure oracle
Message-recovery-type SCAs, which uses ...
CommunityBot
- 1
2
votes
1
answer
116
views
Algorithm to solve SVP (shortest vector problem) using LLL reduction
I'm trying to write a C++ program to solve the shortest vector problem. The program is given a basis of a vector space V and needs to find the shortest non-zero vector in V.
Right now I'm using the ...
CommunityBot
- 1
2
votes
1
answer
232
views
Avoid CKKS Bootstraping
CKKS is a levelled scheme, because the rescale $\lfloor\frac{x}{\Delta}\rceil$ operation requires truncating a modulus to be efficiently evaluated, and rescale is (usually) needed after every ...
CommunityBot
- 1
0
votes
1
answer
46
views
What does it mean the "Distinguisher" in LWE decision version?
As we know in block ciphers, the distinguisher means that despite thousands ciphertexts (and plaintexts), allows an attacker to distinguish the encrypted data from random data. This attack is ...
- 13k
3
votes
1
answer
218
views
ISIS problem in the case of $m=n$
The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $q$, a matrix $A\in \mathbb{Z}^{n\times m}_q$, a vector $b\in \mathbb{Z}^{n}_q$, and a real $\beta$, find an ...
CommunityBot
- 1
3
votes
2
answers
97
views
A Smudging Lemma in Lattice
I saw a paper LLW21 in EUROCRYPT 2021 that used this lemma, but there was no proof or references.
How should this lemma be proved ？
- 13k
1
vote
1
answer
102
views
Decision LWE vs Search LWE: Which one is harder?
Sometimes if we have an attacker who's able to solve decision-LWE problem then we can use them (as a sub-routine) to solve (search) LWE problem, i.e., $\mathsf{sLWE} \leq \mathsf{dLWE}$.
Conversely, ...
- 13k
3
votes
2
answers
132
views
Connection between (noisy) CVP and LWE
What's actually the difference between a (noisy) CVP and LWE? It seems to me that both are the same.
With the definition of LWE:
$$A * s + e = b$$
solving for secret vector s is the same than solving ...
- 13k
1
vote
1
answer
127
views
Centred Binomial Distribution and its effects on security in Kyber
I want to concretely understand how exactly choice of error distribution effect the security of KEM in the context of Lattice Based Cryptography.
For example, I would like to know the concrete ...
- 23.9k
1
vote
2
answers
120
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-...
- 438
3
votes
1
answer
78
views
Ring LWE distribution definitions
This may be a stupid question but I've been stuck on parsing these definitions for a while.
I am reading the paper "On Ideal Lattices and Learning with Errors Over Rings" by Lyubashevsky, ...
CommunityBot
- 1
2
votes
2
answers
175
views
CRYSTALS-Kyber Compress and Decompress function role
I was reading CRYSTALS-Kyber design. They have used compress_q(x,d) to scale an element of $\mathbb{Z}_q$ to $[ 0,1,...,2^d-1 ]$. The definitions of ...
- 23.9k
1
vote
1
answer
68
views
Do you know any library for implementing lattice-based schemes? [closed]
Good afternoon! I'm trying to write a code for a lattice based scheme (based on the SIS problem).
I'm looking for a library that may help me in this task without taking care of the implementation of ...
- 181
0
votes
0
answers
125
views
Approximate SIVP worst-case hardness: proper mathematical formulation used for cryptographic purposes
Is the following a correct formulation for the assumed worst-case hardness of $SIVP_\gamma$?
For every PPT algorithm $A$
for every $n\in\mathbb{N}$ there exists a basis $B_{n,A}=\{v_1,\dots,v_n\} \in ...
1
vote
1
answer
122
views
Matrix multiplication circuit
I am trying to understand which operations are computable by an $\texttt{NC}^1$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector ...
CommunityBot
- 1
2
votes
0
answers
48
views
What's the lattice dimension of the uSVP for attacking CRYSTALS-Dilithium-128?
I am trying to understand the process of transitioning from a NIST standard to the attacks based on of the Unique Shortest Vector Problem (Unique-SVP). Specifically, I am working with Crystals ...
- 324
2
votes
1
answer
180
views
Do we know that LWE is harder than Ring LWE?
The plain, normal-form, decisional LWE problem over $\mathbb{Z}/q\mathbb{Z}$ is: given a uniformly random $n\times n$ matrix $A$ and vector $b\in \mathbb{Z}/q\mathbb{Z}^n$, decide if $b=As+e$ for ...
- 13k
0
votes
1
answer
98
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.
...
CommunityBot
- 1
2
votes
1
answer
93
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 ...
6
votes
1
answer
298
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 ...
- 48.5k
1
vote
0
answers
89
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 ...
- 111
2
votes
2
answers
2k
views
GSW Homomorphic Encryption
In GSW homomorphic encryption scheme proposed here. The integers are over $Z_q$ where $q$ is a modulus parameter of the scheme. It is not clearly mentioned in paper if the ordinary representation of $...
0
votes
0
answers
51
views
Is BGV encryption using different secret keys indistinguishable?
Assume that the same message is encrypted using two different keys within the BGV encryption scheme. Can we assume that the resulting ciphertext are indistinguishable?
I.e., given $c_1 = \text{Enc}(...
- 92.6k
1
vote
0
answers
52
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
0
answers
35
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 ...
- 33
1
vote
1
answer
132
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 ...
- 420
0
votes
0
answers
17
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 ...
- 327
1
vote
1
answer
143
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 &...