All Questions
Tagged with lattice-crypto post-quantum-cryptography
178 questions
1
vote
0
answers
38
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
1
answer
56
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
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
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
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
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
2
votes
1
answer
106
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
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?
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
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
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
2
votes
0
answers
63
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
0
votes
0
answers
84
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 ...
2
votes
1
answer
131
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
1
vote
0
answers
77
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
24
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
130
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
48
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 ...
- 586
5
votes
1
answer
253
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
133
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
743
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
110
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,614
0
votes
0
answers
197
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 ...
0
votes
2
answers
67
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
5
votes
3
answers
313
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 ...
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 ...
- 23.7k
0
votes
1
answer
64
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 ...
- 161
6
votes
1
answer
349
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 ...
- 175
1
vote
0
answers
44
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
0
answers
115
views
Estimating BKZ block size in Kyber
In Section 5.2.1 of the Kyber documentation, it states that the BKZ block size of 413 was chosen using the tool from this paper, i.e., this tool. How was the block size derived from this? Currently, ...
- 1,614
1
vote
0
answers
61
views
Misuse Attacks on Lattice Crypto
I've been reading "Misuse Attacks on Post-Quantum Cryptosystems" (https://eprint.iacr.org/2019/525). In what scenarios are the attacks described in the paper applicable? Is it specifically ...
- 423
6
votes
4
answers
1k
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 ...
- 61
1
vote
1
answer
167
views
Post-quantum secure trapdoor function
I am looking for examples post-quantum secure trapdoor functions. Ideally, the inversion knowing the trapdoor should be "simple" in the sense that it can be computed by a circuit in NC^1.
- 21
3
votes
1
answer
395
views
KYBER.CPAPKE: IND-CCA Security of Lyubashevsky, Peikert, Regev (LPR) Encryption
The NIST Kyber KEM spec. defines an encryption scheme, KYBER.CPAPKE, that's a variant of the so called Lyubashevsky, Peikert, Regev ("LPR") encryption scheme [1]. While LPR encryption is ...
- 678
1
vote
1
answer
131
views
How does big Galois groups yield better security in NTRU Prime?
I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people.
Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how ...
- 13
5
votes
1
answer
128
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, ...
- 113
1
vote
1
answer
585
views
How long time per operation to crack Kyber1024 compared to AES256 for quantum computers?
How long time does quantum computers take per operation when search the key of Kyber? Grover's algorithm weakens 256-bit AES to 128-bit security, quantum computers at most take 2^128 operations to ...
- 371
1
vote
1
answer
44
views
LWE KEMs and message coding
In many proposed lattice PKE schemes, the plaintext is encoded or modulated in a simple fashion, e.g. using Kyber-ish notation:
key gen: $pk=(A, t=As+e)$, $\quad sk=s\quad$ ($A$ random, $s$, $e$ ...
- 430
6
votes
1
answer
793
views
Do we need the quantum random oracle model (QROM)?
I am currently studying the proof of the Dilithium signature in the quantum random oracle model (QROM). I am curious to hear if anyone have any thoughts on the importance of having proofs in the QROM ...
- 345
3
votes
0
answers
152
views
Hardness of LWE with Uniform Secrets and Error Distributions
I have seen various papers discussing the security of the Learning with Errors problem with very small uniform secrets and errors but I have not found any papers on the general LWE problem with ...
- 31
0
votes
1
answer
115
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.
...
- 31
1
vote
2
answers
178
views
LWE and Lattice-based cryptography: How to recover binary message $M$ from $(u, v)$ values?
I am given a set of $(u, v)$ values, matrix $A$, primary key vector, private key vector, error vector and prime $q$. I wanted to recover the binary value of each $(u, v)$ pairs using LWE decryption.
...
- 31
2
votes
1
answer
110
views
How & where is concepts of Good basis and bad basis used in Crystal kyber?
I've read the documentation of Crystal Kyber, but nowhere it is mentioned about good basis and bad basis.
Please explain how and where is the good basis and bad basis is used in crystal kyber.
- 43
1
vote
2
answers
235
views
Are lattice-based cryptography and error-correcting codes mathematically unsound?
From Ronald de Wolf's The potential impact of quantum computers on society:
The first is so-called post-quantum cryptography. This is classical cryptography, based on computational problems that are ...
3
votes
1
answer
716
views
CRYSTALS-KYBER versus FrodoKEM, what makes each of them different than the other?
NIST's main recommendation for encryption/decryption mechanism is CRYSTALS-KYBER. Whereas, the BSI (German equivalent) chooses FrodoKEM.
As far as my knowledge goes both these mechanisms use LWE ...
- 121
16
votes
4
answers
8k
views
Kyber and Dilithium explained to primary school students?
Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?
- 371