Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
614
questions
2
votes
0
answers
29
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
305
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
43
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
42
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
32
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
262
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 ...
- 972
1
vote
1
answer
83
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 ...
- 48
3
votes
1
answer
128
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
60
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
3
votes
0
answers
60
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 ...
- 31
5
votes
1
answer
401
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
45
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
29
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
23
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
13
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 ...
- 361
2
votes
1
answer
77
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 ...
- 434
2
votes
0
answers
57
views
How do lattice based LWE protocols match their keys after generating them?
I am trying to implement a cryptographic protocol based on the following paper explaining the creation of the Swoosh lattice-based NIKE. They also provide a Rust and Jasmine implementation which I ...
- 21
2
votes
0
answers
54
views
Can this lattice problem reduce to SIS problem and/or LWE problem?
The standard SIS problem present as below.
SIS Problem. Let $A\in\mathbb{Z}_q^{n\times m}$ be an $n\times m$ matrix with entries in $\mathbb{Z}_q$ that consists of $m$ uniformly random vectors $\...
- 434
0
votes
0
answers
49
views
CKKS encoding. Why not just use fft
I am studying the ckks scheme from this blog post. In the vanilla encoding part we want to encode a complex vector of size N to a complex polynomial of degree N-1. This of course is possible if we ...
1
vote
0
answers
32
views
Understanding FHE bootstrapping: value of $q$ fed to lattice estimator
I am implementing OpenFHE. In the implementation I'm generating the modulus chain as shown in the example here. I am trying to run Lattice estimator for the same parameters in this example.
I wanted ...
- 19
0
votes
0
answers
24
views
Urgent help with R-LWE Parameters Choice
I am trying to understand CKKS bootstrap algorithm and wanted to understand how is p (plaintext modulo) and q (ciphertext modulo) related in determining the size of the modulus chain. Suppose my ring ...
- 19
-1
votes
1
answer
105
views
Urgent help with LWE Estimator
I am trying to estimate LWE parameters. I know of the GitHub library for LWE estimator but it has no instructions for installation and also provides no guidance for running simple examples. I have ...
- 19
2
votes
1
answer
113
views
Not able to reproduce the security estimates in Kyber through leaky-LWE-estimator
Kyber has provided refined estimate for classical attacks in the Section 5.2 entitled "Beyond core-SVP hardness". Kyber utilized leaky-LWE-estimator https://github.com/lducas/leaky-LWE-...
- 151
2
votes
0
answers
58
views
Is correctness condition of ABE scheme of [BGG+'Eurocrypt2014] right?
I'm reading page 16 of [BGG+'Eurocrypt2014, Section 4]. The ABE in this paper is one of the best lattice-based ABE scheme so far and the techniques used in it inspired other cryptographic primitives ...
- 520
2
votes
0
answers
36
views
Relation between spectral norm and Euclidean norm of a matrix in [BGG+'Eurocrypt2014]
I'm reading [BGG+'Eurocrypt2014] paper and I doubt that maybe there be a typo in
relation between spectral norm and Euclidean norm of a matrix. Here is the part of the paper
I think we must have $\|\...
- 520
2
votes
1
answer
181
views
Trapdoor for SIS
I am new to lattice cryptography. May I ask why, if one has a trapdoor for SIS, i.e., can compute a short $x$ that satisfies $Ax=0$, then one can have a trapdoor for $Ax_{2}=y$?
TIA
- 361
1
vote
0
answers
61
views
Difference between TFHE and CKKS?
What are the differences in parameters while implementing CKKS vs TFHE?
For example modulus size, ring dimensions, bit security. Any pointers to literature would be appreciated
- 19
0
votes
0
answers
19
views
Is there any bound on the size of ring dimension for Torus FHE?
I see that all implementations of TFHE in opensource supports 2^10 to 2^12 size of ring dimensions. Is there any specific reason (crypto) behind choosing the value or can we choose higher dimensions (...
- 19
1
vote
1
answer
71
views
Reject sampling of lattice ZKP, why need factor of M
I am watching the video https://www.youtube.com/live/N5nKGtugxYY?si=ejLqW8Pk0jD9lVMn&t=2098
Or particularly this slide:
May I ask why does the reject sampling output by $f(x)/g(x)*M$ probability? ...
- 361
1
vote
1
answer
55
views
Decryption of LWE-based Inner-Product Fuctional Encryption of Agrawal-Libert-Stehle Crypto 2016
In below image, we have LWE-based inner-product functional encryption for short integers
[ALS'Crypto2016].
Is the encryption correct? Why do they get $\mu\in\{\color{red}{-K+1},\ldots,0,K+1\}$? When ...
- 520
1
vote
1
answer
64
views
lattice RLWE encryption and decryption process
I am here trying to solve an issue that I face a lot during solving RLWE.
The issue is that I am not able to retrieve the original message after the decryption process.
I use the following encryption ...
- 33
1
vote
0
answers
98
views
ECDSA biased nonce with biased middle bits
The paper "Biased nonce sense" (https://eprint.iacr.org/2019/023.pdf) covers key recovery for MSB and LSB, the latter case being handled by doing modular inverse of 2 to the power of the ...
- 11
1
vote
1
answer
56
views
Question of section 1.3 Intuition for Aborting in "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures"
When I'm reading this paper "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures" by Lyubashevsky. I have trouble understanding section 1.3 Intuition for Aborting....
- 15
1
vote
1
answer
110
views
How to choose the distribution of error and secret vectors in LWE-based KEMs
The general construction of a LWE-based PKE looks like the following:
KeyGen :
Secret vector, sk :$ s \leftarrow \chi_s^m$
Public Key, pk: ($A \leftarrow \mathbb{Z}_q^{m \times m}, t = As + e)$ where $...
- 151
3
votes
1
answer
38
views
How to determine approximate factor (i.e. modulus-to-(bound of)noise ratio) of LWE in advaned primitives is sub-exponential or polynomial?
In advanced primitives like circuit (policy) ABE [BGG+'Eurocrypt2014] or IPFE [ACGU'Asiacrypt2020, appedix A] based on lattices, parameters setting is quite puzzling and vague (for me).
(Parameter ...
- 520
1
vote
1
answer
60
views
Literature on Batching in FHE
From what I understand, the folklore way to batch Ring-LWE style cipher texts is to use the Chinese remainder theorem. I am wondering if there are any different approaches/optimizations to this style ...
- 27
2
votes
0
answers
116
views
Can this problem reduce to the SIS problem or LWE problem?
The description of the graceless problem is as below.
Given a full rank square matrix $A=(R\cdot S+E)\in\mathbb{Z}_q^{n\times n}$,where:
$q>2^\lambda$ is a prime;
$R\leftarrow\mathbb{Z}_q^{n\times ...
- 434
0
votes
1
answer
45
views
Gadget Matrix Ring Setting
What would be the analogue of the gadget matrix in the ring setting? Would it be the same matrix? Do the trapdoor algorithms work exactly the same way?
Thanks
- 27
0
votes
1
answer
78
views
Questions about SIS hard problem
The definition of $\mathrm{SIS}_{q,n,m,\beta}$ problem is as below.
Let $A\in\mathbb{Z}_q^{n\times m}$ be an $n\times m$ matrix with entries in $\mathbb{Z}_q$ that consists of $m$ uniformly random ...
- 434
5
votes
1
answer
202
views
Shortest Vector Problem as Dihedral Hidden Subgroup Problem
I’m a mathematician trying to get into cryptography. I have a somewhat silly question, but I can’t seem to find a proper answer anywhere. I am interested in whether or not there is a way to directly ...
- 101
1
vote
0
answers
119
views
Math of Hint usage in Dilithium
For Dilithium, I understand that
$$\text{HighBits}(\mathbf{Ay}) = \text{HighBits}(\mathbf{Ay} - c\mathbf{s_2}) = \text{HighBits}(A_z - c\mathbf{t})$$
The first term of the equation is performed on the ...
- 81
9
votes
2
answers
689
views
Is NTRU broken?
Today a new paper appeared on ePrint, "Improved Provable Reduction of NTRU and Hypercubic Lattices". It claims that:
this is the first provable result showing that breaking NTRU lattices ...
- 880
2
votes
0
answers
108
views
Direct quantum reduction from GapSVP to SIS
Looking through Chen's recent paper, if we forget about complex Gaussians and just build uniform superpositions over hypercubes, we could create the state
$$\sum_{v\in L}\vert v\rangle \sum_{y\in\...
- 1,212
0
votes
0
answers
74
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
...
- 1
0
votes
0
answers
196
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.
- 51
62
votes
4
answers
11k
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
vote
1
answer
113
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 ...
- 161
2
votes
2
answers
110
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
2
votes
1
answer
54
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 ...
- 147
0
votes
2
answers
56
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 \...
user105855