Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
643 questions
1
vote
1
answer
49
views
Effect of multiplying message by $q/2$ LWE
I have recently started learning about the LWE problem, and I am wondering about how multiplying the message bit $\mu \in \mathbb{Z}_2$, affects the encoding of this message.
The LWE-based ...
1
vote
0
answers
37
views
CRYSTALS-Kyber Central Binomial Distribution reference inplementation in c
In lines 8 to 10, why it does not get input bytes as it is (i.e., line 8)? It first does some changes (line 9 and 10).
Do authors do this changes as we cannot work with binary form of a variable ...
- 586
2
votes
2
answers
32
views
Security of Ring-LWE and Module-LWE encryption scheme
Regev-05 encryption under plain LWE consists in using a public key $\mathsf{pk} = (\mathbf{A}, \mathbf{b} = \mathbf{A}^\top\mathbf{s}+\mathbf{e})$, where $\mathbf{A}\in \mathbb{Z}_q^{n\times m}$ is ...
- 509
2
votes
1
answer
55
views
Modulus in Lattice-Based Cryptography？
The common modulus methods are standard modulus (the result is confined to the range $[0, q-1]$) and centered modulus (the result is confined to the range $[- \lfloor q/2 \rfloor, \lceil q/2 \rceil)$)....
- 115
2
votes
1
answer
33
views
Understanding Canonical-embedding vs Coefficient-embedding in Ideal Lattices: Relation to NTT?
I'm trying to understand the relationship between different representations of ideal lattices, particularly the canonical embedding and coefficient embedding. While studying these concepts, I noticed ...
- 85
4
votes
0
answers
74
views
What is a Lattice trapdoor?
In "A New Approach for Non-Interactive Zero-Knowledge from
Learning with Errors" , Brent Waters uses lattice trapdoors to build hidden bit generators. Can someone explain to me what a ...
0
votes
2
answers
54
views
Can the message space for Ajtai Hash be extened?
I have a question regarding the Ajtai hash function. Typically, the message space for this function is the binary space $\{0, 1\}^m$. However, I am considering extending the message space to $\{-1,0, ...
- 115
1
vote
1
answer
69
views
Is there an efficient algorithm to compute the inverse of a small-norm element in a special polynomial ring？
The paper "Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs" presents a corollary stating that in a polynomial ring $...
- 115
0
votes
1
answer
37
views
Is $A \in \mathbb{Z}_q^{m \times m}$ is a one-way function?
In lattice-based Cryptography, Ajtai [1996] demonstrated the family of one-way functions. For a uniformly chosen matrix $A \in \mathbb{Z}_q^{n \times m}$ and $x \in \{0,1\}^m$, $A \cdot x \mod q$ is a ...
- 919
0
votes
0
answers
24
views
Proof of random-self-reucibility of LWE (worst- to average-case) in Regev paper, Lemma 4.1
I'm reading proof of [Regev'arXive2401.03703, lemma 4.1, page 30].
I can't figure out how Oded Regev estimates acceptance probability of the average-case distinguisher by Chernoff bound
Thorem (...
- 586
6
votes
1
answer
125
views
Do the specific powers of two $2^{23}$ and $2^{13}$ in the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$ have any special purpose in its design?
I recently started exploring Post-Quantum Cryptography, particularly Lattice-based Cryptography, and came across the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$, which is used in schemes like ...
- 85
1
vote
0
answers
74
views
Why are matrix-secrets used on lattice based signatures?
I was wondering why in the Fiat-Shamir with aborts paradigm on lattices such Lyuba12, matrices S and E are used to generate the public key ($AS + E = B$ or $AS = B$).
And not just vectors like on ...
- 11
2
votes
1
answer
51
views
How does lattice reduction produce $s$ and $e$ from public parameters of an LWE instance?
It has been shown that by embedding $A$ and $t$ from an LWE instance $A$, $t=As+e$ inside a lattice, we can find a vector from the reduced lattice that contains $s$ and $e$.
For example, in the ...
- 91
2
votes
1
answer
52
views
How does the size of the parameter $n$ in $Kyber$ affect the success of lattice reduction of LWE instances?
I'm learning about using lattice reduction to find the secret $s$ of an LWE instance. When testing it on code, I have noticed that when $n$ is 32 or lower, I am able to retrieve $s$ successfully, but ...
- 91
0
votes
1
answer
59
views
Why consider/formulate Shortest Vector Problem as a Promise Problem and not as a Decision Problem?
We know (search) approximate Shortest Vector Problem ($\mathsf{SVP}_{\gamma}$): Given an arbitrary basis $\mathbf{B}$ of some lattice $\mathcal{L}=\mathcal{L}(\mathbf{B})$, find a shortest non-zero ...
- 586
2
votes
2
answers
139
views
Is the variant of LWE-based encryption scheme secure?
Suppose that there exists a SIS instance generator $Gen_{SIS}(n,m-1,q)\to(A\in\mathbb{Z}^{n\times m}_q,s\in\{0,1\}^{m-1})$, where $(s,1)$ is the short integer solution for the SIS instance $A$, s.t. $...
- 456
2
votes
2
answers
184
views
How is it that a matrix of polynomials can be represented as a circulant matrix for purposes like lattice reduction?
When using lattice reduction on polynomial matrices, I have seen examples where a matrix can be represented as a circulant matrix before lattice reduction. Is there an explanation on why this works?
...
- 91
2
votes
2
answers
103
views
Understanding LWE's Correctness Proof
In this paper, on page 33, we are presented with Claim 5.2 which is supposed to show that for the selected parameters in LWE, namely:
$\alpha(n)=o(1/(\sqrt{n}\log ...
- 31
3
votes
0
answers
84
views
Why RLWE is typically implemented using unsigned integers?
Every RLWE implementation I know uses unsigned integers even when it needs to represent signed values. Why?
3
votes
1
answer
101
views
Choosing $x^n+1$ as an irreducible polynomial in $\mathbb{Z}[x]$ instead of $x^n-1$ for ring $\mathbb{Z}[x]/\langle f(x)\rangle$ of Ring-LWE
In the note of ["Ring-SIS and Ideal Lattices by Noah Stephens-Davidowitz (for Vinod Vaikuntanathan’s class", footnote 3], it has written:
3 The ring $\mathbb{Z}[x]/(x^n + 1)$, ideal ...
- 586
2
votes
1
answer
61
views
I have the best basis possible for a lattice. How well can I solve CVP?
Let's suppose I've given a lattice $L$. I'm allowed to spend as much pre-computation as I want to produce a poly-sized advice string, and I use it to find the best basis possible for the lattice.
Then ...
- 1,614
2
votes
1
answer
44
views
Why are only primal and dual attacks dealt with among the various attacks on LWE?
As we see in https://estimate-all-the-lwe-ntru-schemes.github.io/docs/, only dual and primal attacks are the most important attacks against LWE and NTRU schemes. On the other hand, many attacks such ...
- 161
2
votes
0
answers
35
views
When can radix-3 NTT faster than radix-2 NTT?
I am a beginner in Lattice based cryptography and now I am encountering some cryptography algorithms using NTT.
And I am trying to change the NTT in algorithms and I am going to make an appoche to use ...
- 21
1
vote
0
answers
43
views
How to batch-prove the knowledge of Module-SIS secrets
If the prover wishes to prove knowledge of Module-SIS secrets $\mathbf{s}_i$ satisfies $\mathbf{A}_i \cdot \mathbf{s}_i = \mathbf{u}_i\ \text{mos}\ q, i \in \{1,2,\cdots,N\}$ where $R_q$ is a ...
- 115
3
votes
0
answers
57
views
If $\Vert cs\Vert$ is short in a lattice signature, how large can $s$ be?
I would like a result of the following form:
"Let $s\in \mathcal{R}_q^n$ where $\mathcal{R}_q = \mathbb{Z}_q[x]/(x^d+1)$. If $\Vert s\Vert > q$, then (with all but negligible probability) for ...
- 1,614
1
vote
0
answers
22
views
SIVP to SIS: Why we must use uniformly random input for an hypothetical oracle in reduction?
I'm reading a handout about worst-case to average-case reduction by Peikert and Banerjee: https://github.com/cpeikert/LatticesInCryptography/blob/main/lec11.pdf
In the reduction from SIVP to SIS, we ...
- 83
0
votes
1
answer
38
views
Is it possible to prove with high certainty part of a preimage must exist to produce an LtHash output?
Given a H calculated using the LtHash algorithm, is it possible to prove a section of the preimage must have been part of the specific original preimage?
i.e. given H = lt(A | X | B) give proof that X ...
1
vote
1
answer
42
views
Conditional distribution of an integer error vector, taken from an appropriate discrete Gaussian, given its syndrome [GPV'STOC2008]
I'm reading lemma 5.2 of [GPV'STOC2008, page 18] about conditional distribution of an integer error vector $\mathbf{e}\in\mathbb{Z}^{m}$, taken from an appropriate discrete Gaussian $\mathbf{e}\sim D_{...
- 586
3
votes
0
answers
184
views
Estimate security parameter $n$ for Ajtai commitment
Let $x$ be a binary string of length $m \approx 2^{20}$, $A_{n \times m}$ be a random matrix with entries independently and uniformly drawn from $\mathbb{Z}^*_{q}$, and $q$ be a $128$-bit prime number....
- 57
0
votes
0
answers
27
views
A few questions about smooth paramter in lattice signature
I was recently studing lattice signature and reading the GPV08 paper.
For my comprehension, given a continuous guassian distribution, the smooth parameter decides a bound that, by placing the same ...
0
votes
0
answers
34
views
How to get a sample from $D_{q\mathbb{Z}+c,r}$？
In the paper Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures, the preimage sampling boils down to only n times sampling of $D_{q\mathbb{Z}+c,r}$. How can we obtain a sample ...
- 51
10
votes
1
answer
234
views
Relationship between LWE, SIS, and ISIS
Suppose I have a short-secret LWE instance $As+e=b\mod q$. If I treat this as a single matrix, it becomes an ISIS problem:
$$ \begin{pmatrix} I &A\end{pmatrix}\begin{pmatrix} e \\ s\end{pmatrix}=b\...
- 1,614
1
vote
2
answers
74
views
A problem about fundamental region of a lattice
This lemma is from Peikert and Carter's handout of lecture 2. $\mathbf{\tilde{B}}$ is the Gram-Schmidt orthogonalized matrix of $\mathbf{B}$. I want to prove this lemma.
My idea is to prove it by ...
- 83
1
vote
1
answer
64
views
Gaussian width in lattice setting
In the lattice setting (like LWE, RLWE) , the Gaussian function is often defined as
$$
\rho_{\Sigma}(x) = e^{-\pi x^T\Sigma^{-1}x}
$$
The discrete Gaussian distribution $\mathcal{D}_{\Lambda, \Sigma}$ ...
- 11
2
votes
1
answer
105
views
Smaller module ranks of MLWE imply more algebraic structure?
In CRYSTALS-Kyber, they mentioned that the module rank $k$ should not be too small, they argued "having a smaller $k$ implies more algebraic structure, making the scheme potentially susceptible ...
- 75
2
votes
2
answers
403
views
Why is the public key included in the private key in Kyber KEM?
We know that CRYSTALS-KYBER's KEM (key encapsulation mechanism) key generation algorithm is:
Output:
Public key pk $\in B^{12\cdot k\cdot n/8+32}$,
Secret key sk $\in B^{24\cdot k\cdot n/8+96}$
$z \...
- 21
2
votes
1
answer
59
views
In GPV08 lattice signature, why the fact that the bijective from quotient group to the set of syndromes holds?
I was recently reading the lattice-based signature scheme GPV08 (full paper), and the following statement confuses me alot (which is in the section 5.1, page 17&18):
Throughout the paper, we use ...
0
votes
0
answers
62
views
Is there split-radix (mixed-radix) number theoretic transform?
Can I use multiple radices (for example, radix-2 and radix-4) for one NTT? If so, what would the twiddle factors be?
1
vote
0
answers
37
views
How to compute the vector $\mathbf{v}$ in verifiable encryption scheme?
In the subsection 6.3 of Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General, if the module p of encryption scheme is co-prime to the module q of commitment scheme,...
- 51
3
votes
1
answer
307
views
Questions about LWE in NIST standards
LWE instances have the form $\vec{a}_i,b_i = \langle\vec{a}_i,\vec{s}\rangle+e_i\bmod q$ for some integer $q$ and for $i=1,\dots,m$.
My questions are about the NIST proposed standards. In the ...
- 1,025
1
vote
1
answer
106
views
A question about smoothing lemma and proof
I'm a beginner on lattice-based cryptography and currently reading a handout of Prof. Vinod Vaikuntanathan.
The first question
In section 2.4 Smoothing Lemma and Proof, I cannot figure out why the ...
- 83
3
votes
1
answer
162
views
Compare Saber and Kyber, about their techniques of message bit layout in encryption
I'd like to discuss message bit layout in the Saber and Kyber's IND-CPA encryptions.(Details of these two schemes follows behind these question paragraphs). From my understanding, both Saber and Kyber ...
- 75
2
votes
1
answer
78
views
Centered Binomial Distribution vs Fixed Weight Ternary Sampler
Fixed weight ternary polynomial vector sampler randomly selects a polynomial from ${R_q[x]}/{(x^n+1)}$ with coefficients $-1,1,0$. Notable KEMs that uses fixed weight ternary samplers include NTRU, ...
- 151
5
votes
1
answer
127
views
Noise flooding in Lattices
I noticed that in the paper [HLL24], the authors used the noise flooding technique to choose parameters and complete the proof.
But I am confused that why set $\sigma \ge 2^{\kappa+6}y$ to guarantee ...
- 51
5
votes
1
answer
428
views
In lattice, does converting a "bad" basis to a "good" basis constitute a hard problem?
In lattice, a "good" basis are the set of "almost" orthogonal set of vectors which have small norms and a "bad" basis are those basis which are in certain sense hardest ...
1
vote
0
answers
48
views
Doubts regarding the ternary vector sampler in SMAUG-T KEM
SMAUG-T is an efficient post-quantum key encapsulation mechanism (KEM). It is the winner of Korean PQC Competition.
SMAUG-T uses a Hamming Weight Sampler $HWT_h$ to sample secret polynomial vectors $s,...
- 151
1
vote
0
answers
39
views
What is the difference between PLWE (Polynomial Learning with Errors) and RLWE (Ring Learning with Errors)？ [closed]
Recently, I have been studying lattice-related concepts, and I want to understand the differences between PLWE and RLWE, such as how their security compares, as well as their structure and value ...
- 11
0
votes
0
answers
28
views
Issue building RLWE based program
I've successfully built a LWE based program now moving onto building a RLWE based python program using: https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/ as a ...
0
votes
0
answers
21
views
Tutorial of lattice estimator to compute a specific function with BGV
I recently try to go into lattice estimator https://github.com/malb/lattice-estimator
I did find the document of it, but unfortunately, can not follow.
May I ask how to run the lattice estimator to ...
- 371
2
votes
1
answer
103
views
About the notion of "full rank" in lattices
I'm a newer to the lattice theory, so there is a basic notion about "full rank" confusing me.
In some papers focusing on the lattice theory, they always use the full rank lattice (the number ...
- 456