Questions tagged [post-quantum-cryptography]
This tag refers to public-key algorithms based on problems that quantum computers can't solve efficiently. Existing algorithms such as RSA, Diffie-Hellman, and ECDSA are known to be breakable using Shor's algorithm on quantum computers. Symmetric-key algorithms generally don't fall under this category.
763
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
4
votes
1
answer
257
views
Attacks exploiting decryption failures in KYBER
I am going through the portion mentioned under the heading Original KYBER analysis inside Section 5.5 titled Attacks exploiting decryption failures.
$${\sf Pr}[\|v\|> k\sigma \sqrt{m}]< k^m e^{\...
- 151
1
vote
1
answer
39
views
Bound for Zhandry's result in Quantum random Oracle Model using the inequality of Markov brothers
In the proof of Theorem 3.2 in the paper 'Secure Identity-Based Encryption in the Quantum Random Oracle Model' by Zhandry, the author utilized the inequality by Duffin and Schaffer [DS41] (Markov ...
- 33
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?
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
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
0
answers
35
views
Difference in the CCA security bound of KYBER KEM in IEEE S&P Version and NIST Submission
I was going through the KYBER CCA security bounds. I noticed one intriguing discrepancy in the CCA bound mentioned in IEEE EuroS&P version (https://eprint.iacr.org/2017/634.pdf) and KYBER NIST ...
- 43
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
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
19
views
Can FRI in STARK be used in Spartan?
Can FRI in STARK be applied to multilinear polynomials? I am reading the paper ''Spartan: Efficient and General-Purpose zkSNARKs without Trusted Setup'' which mentions that Spartan requires a ...
- 73
7
votes
2
answers
420
views
Post-Quantum secure KEM with CCA security without using PKE
As we know, one of the most common ways to make a post-quantum key encapsulation mechanism (KEM) is as follows:
First, we choose a public key cryptography (PKE) so that it is resistant to chosen ...
- 53
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
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 ...
0
votes
1
answer
127
views
PQC Implementation of ML-KEM and ML-DSA
I am trying to implement the NIST Post-Quantum Cryptography algorithms ML-KEM and ML-DSA (derived from CRYSTALS-Kyber and -Dilithium as specified in NIST FIPS-203 and NIST FIPS-204 respectively using ...
0
votes
1
answer
89
views
Do quantum computers break hashcash?
Hashcash is a mechanism to prove that the sender of a message is really intending to send that message instead of just performing a denial of service attack. It makes denial of service attacks harder ...
- 1,613
3
votes
1
answer
91
views
What are the recommended parameters for NTRUEncrypt?
I'm looking into NTRU for the first time and I am confused by the variants and the set of parameters. I'd like to use a secure NTRU-based cryptosystem to have a (plausibly) quantum secure PKE offering ...
- 33
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
0
votes
0
answers
22
views
Unknown specific generator on a non-invertible semigroup homomorphic signature valid?
There's a quantum polynomial time algorithm to solve DLPs in semigroups, without inverses, so apparently there's nothing to research with those semigroups.
I don't know if this is an area of research ...
- 565
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
0
votes
0
answers
39
views
Linear attack on Stickel's key exchange scheme by Shpilrain
I tried to solve the system of equations
$$xa=ax$$
$$yb=by$$
$$xy=u$$
where $a,b,u$ are known invertible matrices and x and y are unknown matrices.
I tried Mathematica and Python but couldn't get it ...
- 1
0
votes
0
answers
67
views
Is sha256 quantum secure? [duplicate]
I've been reading about the security implications of quantum computing on cryptographic algorithms and came across some discussions regarding SHA-256. I understand that SHA-256 is currently considered ...
4
votes
0
answers
101
views
Why Dilithium has options starting from security level 2 and not 1?
I am a newbie to PQC, so forgive my gaps in understanding. Most of the NIST PQC standardization selections have 3 levels of security 1, 3 and 5. It is not the case for Dilithium. IS there any specific ...
- 41
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
2
votes
2
answers
339
views
The post-quantum public keys are long. Is it secure to map sha512 to a public key?
Context
After reading that for all post-quantum public key cryptography era of short keys and signatures is gone, I wonder how it would be possible to reduce cryptographic overhead of data transfer. ...
- 135
0
votes
1
answer
83
views
SPHINCS+ signature calculation and FORS public key
I was trying to understand the SPHINCS+ document from https://sphincs.org/data/sphincs+-r3.1-specification.pdf and have the below doubts.
Consider the example of SPHINCS+-128s , the value of n,h,d,log(...
- 81
1
vote
1
answer
89
views
ADRS in WOTS+ signature scheme
I am trying to understand the sphincs+ from [1] and have a fair understanding of WOTS+ scheme from [2]
However, in the OTS scheme defined in [1] , it seem to use ADRS for storing chain address, hash ...
- 81
2
votes
1
answer
72
views
The explicit authentication in PQ3
I've found the main part of the PQ3 protocol used in iMessage introduced in Apple's blog https://security.apple.com/blog/imessage-pq3/ is like combining the Signal protocol with a post-quantum KEM ...
- 21
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
0
votes
0
answers
56
views
X25519Kyber768Draft00 Key Exchange still in use, even after GPO/Registry to disable
I am trying to find out if there is another place to disable the Post-Quantum key exchange options other than what has been published Chrome/MS for browsers. The X25519Kyber768Draft00 Key Exchange ...
- 1
0
votes
1
answer
176
views
Kyber and Classic McEliece as Public Key Encryption algorithms
Can Crystal Kyber and Classic McEliece be used as public key encryption (PKE) algorithms?.
Is there any problem with using these KEM algorithms as PKE for some reason, e.g., doing some holomorphic ...
- 33
1
vote
1
answer
71
views
Showing special soundness for Dilithiums underlying $\Sigma$-protocol
I'm trying to prove the security of Dilithiums underlying $\Sigma$-protocol using the following theorem.
Let $\Sigma=\left(\mathcal{P},\mathcal{V}\right)$ be a $\Sigma$-protocol on an effective ...
- 253
0
votes
2
answers
83
views
Qbits vs RSA vs Time
So I'm writing a section for my Rats of NIMH fanfiction where the Rat Republic using Quantum computers to wreck havoc on the US economy for the war effort.
Well, the issue is that I like to pretend to ...
- 101
2
votes
0
answers
72
views
Inequalities in collision search on the separation between the classical and quantum random oracle (ROM vs QROM)
I'm trying to read the separation between the classical and quantum random oracle through a paper "Random Oracles in a Quantum World" by Dan Boneh, Ozgur Dagdelen, Marc Fischlin, Anja ...
- 33
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
2
votes
1
answer
231
views
Is there a PQ-TLS that is close to practical?
Are there any cryptographic protocols available for HTTP such as TLS or QUIC with practical or near-practical quantum computer resistance?
- 21
1
vote
0
answers
54
views
Recovering dilithium secret keys implies solving MSIS
I'm currently looking at different ways to break Dilithium and found this post:
What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?
...
- 253
2
votes
1
answer
222
views
Why did NIST Post Quantum Standardization have 2 schemes?
NISTs Post Quantum Standardization process selected Kyber as the KEM scheme.
I'm a bit confused over why NIST would standardize for a 'scheme' and not just a 'cipher'. Does Crystals-Dilithium use a ...
- 123
3
votes
2
answers
543
views
The advantages of using KEM compared to applying traditional PKE approach
I am studying a thesis on the design of a key encapsulation mechanism (KEM). In section 2.6 (page 18) of this thesis, the following explanation is given about the difference between KEM and common ...
- 53
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
60
views
SampleNTT in Kyber [duplicate]
I was going through Kyber specification mentioned here - https://csrc.nist.gov/pubs/fips/203/ipd
The SampleNTT is an algo used for matrix A calculation that takes XOF(p,i,j) as input.
If the input is ...
- 81
1
vote
1
answer
114
views
USeHint and MakeHint in Dilithium
My understanding of Dilithium is below
To sign, signer generates random vector y with coefficients under a given threshold. He calculates:
...
- 81
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
198
views
In x25519kyber768 what is the use of the server kyber keys if only the client public kyber key is used for encapsulation in kem?
In x25519kyber768 what is the use of the server kyber keys if only the client public kyber key is used for encapsulation of the kyber shared secret in kem?
1
vote
0
answers
39
views
CRYSTAL-KYBER for Cloud-native storage [duplicate]
I'm trying to use CRYSTAL-KYBER encryption to protect Cloud-native storage against both normal and quantum attacks. I've read Cloud-native-security-whitepaper and found out that ...
- 51
3
votes
1
answer
292
views
Confusion in the security level offered by KYBER
I was looking at security level offered by KYBER. I have attached the table for the reference. I am little bit confused regarding the security level offered by KYBER.
By definition,
Level 1 in the ...
- 151
11
votes
4
answers
8k
views
How will the world learn that Q-Day has arrived?
I wonder how the world will come to know that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm have arrived. The day when this happens has been referred to as "...
- 289