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.
646
questions
4
votes
1
answer
91
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 ...
- 159
1
vote
0
answers
26
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 ...
- 11
1
vote
2
answers
247
views
In Learning with errors, what is the relation between the size(or standard deviation) of errors and security?
I want to understand how the hardness of Learning With Errors problem varies as size of the error term changes.
For example, assuming that the other parameters are the same,
LWE with errors sampled ...
- 171
0
votes
1
answer
47
views
Rainbow What happened to signatures in the NIST standardization process?
The rainbow signature was not seen in round 4 of the NIST PQC standardization process. Was Rainbow not shortlisted?
- 117
2
votes
1
answer
37
views
For what 'rounding constant' exists in Round5?(NIST PQC Round 2 Algorithm)
I am reading a paper Round5.
This public key encryption scheme is based on Ring-LWR but I found it is a little bit different from typical LWR-based PKE scheme.
In the key generation algorithm of ...
- 171
1
vote
1
answer
47
views
LWE encryption: Errors for encrypted messages
I am following this paper Encryption from Learning with Errors for the generation of errors e1 and e2 to retrieve the ciphertext u and v as described below.
...
- 31
1
vote
1
answer
42
views
How is Crystal Kyber CPA-secure algorithms converted into a CCA-secure algorithm
In Crystal Kyber specification, page no10, there are 3 algorithms namely KYBER.CCAKEM for making the CPA-secure Kyber into CCA-secure one.
Q1: How is the shared key K being generated in KYBER.CCAKEM....
- 33
1
vote
0
answers
49
views
Quantum-Safe MAC: HMAC and CMAC
If understood right, CMAC is not quantum-safe because it relies on AES-128 (which isn't considered as quantum-safe), while HMAC is, because it relies on SHA3 (which is considered as quantum-safe). Did ...
- 153
5
votes
0
answers
119
views
+50
Are rejected Dilithium commitments secret?
On 6 March, Yi Lee sent over the NIST mailing list an announcement of their submitted paper that found a flaw in the original security proof for Dilithium. In their manuscript, they fix the proof on ...
- 1,115
0
votes
1
answer
47
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
80
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
55
views
Is Falcon (PQ signing algorithm) slower than ECDSA in terms of computing time?
FALCON is a cryptographic algorithm for digital signature, but is it slower than actuals algorithms (ECDSA)?
1
vote
1
answer
42
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.
- 33
1
vote
1
answer
58
views
Why predicting an error in Crystal Kyber is considered to be hard?
Hi I have started studying on crystal kyber recently. Gained some knowledge regarding its algorithm and how it works. My doubt is why it is tough for attacker to extract secret vector from pk itself ...
- 11
1
vote
2
answers
121
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 ...
1
vote
3
answers
129
views
Why can't we just increase the bit length to counteract shor's algorithm?
I know that it sounds like a very stupid question but if Shor's algorithm has a complexity of roughly $n^3$ why cant we just increase the bit size until the time for the algorithm to run is ...
4
votes
3
answers
3k
views
Why did post-quantum key exchanges go extinct?
On July 5, 2022, NIST chooses one KEM (Key Encapsulation Mechanism) as a PQC standard and 4 KEMs as four-round candidates. Why aren't there any key exchanges?
Similarly, KEMs are usually studied in ...
- 113
0
votes
1
answer
68
views
How is MLWE used for key generation in Kyber?
I've been reading about Crystal kyber, and i read that the in the key generation process, the public key pk is computed using secret key s in such a way that the ...
- 33
-2
votes
1
answer
62
views
What is secp256k1 and can we have a post quantum cryptography with that? [closed]
Please detail secp256k1 and its role in a public key cryptography. Please explain can we use it into a post-quantum cryptography and how can we do it?
- 109
5
votes
4
answers
231
views
What is the significance of the results of the NIST PQC competition?
I hope this is not offtopic.
Since NIST has rather recently announced the winners of its PQC competition I was wondering how significant this development is. Does that mean that CRYSTALS-Kyber will ...
- 617
2
votes
1
answer
72
views
WRT Shor resistant crypto: which is more likely
In NIST’s ‘competition’ to obtain new public key crypto which resists Shor’s algorithm (aka ‘post quantum cryptography’), two algorithms to make it into the third and fourth rounds have been ...
1
vote
1
answer
43
views
How effective is increasing elliptic curve modulo sizes for quantum resistance?
From info provided by Google:
Lattice based key pair and signature sizes are roughly 12/2 kb and 9 kb, which is much larger than 256-bit ECC key sizes.
The number of q-bits need to break n-bit ECC ...
- 13
2
votes
1
answer
77
views
What advantages does FrodoKEM have over other PQCs?
What are the advantages of FrodoKEM over other NIST PQC candidates? Also, have any critical vulnerabilities been discovered so far?
- 117
4
votes
1
answer
57
views
sUF-CMA security of Lyubashevsky's ID and signature protocol
I have been working on the post-quantum safe ID/signature-schemes of Vadim Lyubashevsky (https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf).
I am in particular studying the security ...
- 159
1
vote
1
answer
89
views
KEM security definition - IND-CCA vs IND-CCA2
When researching about PQ KEM's I have come across two different definitions of indistinguishability under (adaptive) chosen ciphertext attack. IND-CCA (https://eprint.iacr.org/2017/604.pdf page 10, ...
- 162
3
votes
1
answer
176
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 ...
5
votes
1
answer
66
views
Covering codes for digital signatures
An encryption scheme should be injective in the sense that each ciphertext should only be associated with at most one message, in order that decryption is unambiguous. An efficient signature ...
- 18.3k
12
votes
4
answers
5k
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?
- 181
0
votes
1
answer
43
views
What is the best method to compose a set of matrices into one and then unambiguously decrypt it?
I am presented with the following problem:
Given a set of matrices $M = \{A^i_{m,n} : 0 < i < 101 \}$ design a procedure to compose all of them into one encrypted matrix $E_{m,n}$ and later ...
- 189
2
votes
0
answers
43
views
What is the exact assumption behind OW-CPA of NTRU?
As shown in this paper the IND-CPA of NTRU is based on both the decision key cracking problem and the decision ciphertext cracking problem. However, I often see claims (such as in this paper) that the ...
- 228
2
votes
1
answer
79
views
"Shifting" a dual-Regev keypair away from a trapdoored instance
This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality:
$\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair
...
- 124
3
votes
1
answer
116
views
Why is the best way to solve LWE (and Cryptographic related Systems) with SVP (approx)?
Community,
I'm new into lattice based cryptography, and I'm interested about the security of cryptography schemata like Kyber and why the focus of solving this problem lead into solving approx. SVP.
...
- 65
3
votes
2
answers
323
views
Break Lattice-Based Cryptography with Variational Quantum Algorithm (only 25 k. Qbits for Kyber1024)?
I am currently writing a seminar paper on Kyber and other lattice-based methods. I was so excited about the lattice-based methods that I also currently searched quantum algorithms to solve the methods....
- 65
3
votes
0
answers
162
views
What does break with "usual" classical security reductions in quantum setting?
OK, so I know that this is somewhat really basic in "post-quantum discourse", but unfortunately I did not find any textbooks/entry level papers specific to the topic of reductions in the ...
- 589
3
votes
1
answer
76
views
Do ideal non-cyclotomic lattices provide better compression in lattice-based cryptography?
Let $f \in \mathbb{Z}[x]$ be an irreducible polynomial of degree $N$ and $q \in \mathbb{N}$. Consider the rings $R := \mathbb{Z}[x]/f$ and $R_q := R/q$. Obviously, an element of $R_q$ can be ...
- 327
1
vote
1
answer
106
views
Usage of tweakable hash functions in SPHINCS+
In the SPHINCS+ paper(https://sphincs.org/data/sphincs+-paper.pdf) part 3.2, it explains that they are not using l-trees as a direct consequence of the use of tweakable hash functions.
I have read the ...
- 23
2
votes
1
answer
272
views
What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?
I am trying to understand the post quantum based signature scheme Dilithium. I know what the hard problems are in the scheme, but I am having trouble in understanding the utilization of short integer ...
1
vote
1
answer
94
views
How does signing with FORS work in SPHINCS+?
I was reading the SPHINCS+ paper and got confused in the signing with FORS (forest of random subsets) part.
I understand how we can sign a message using FORS but I couldn't understand how we choose ...
- 23
1
vote
1
answer
168
views
Quantum computer threats to modern cryptography
I am having a university assignment that requires me to study on the threats that quantum computer poses to modern cryptography.
At the moment, I know that modern symmetric encryption will reduce ...
- 115
18
votes
1
answer
5k
views
Will IBM's Condor quantum processor run Shor's Algorithm to crack a 256-bit Elliptic Curve key?
Yesterday IBM announced that they have a 433 bit quantum computer, called Osprey. There is nothing in the press releases I can find that says whether it can or cannot run Shor's Algorithm.
They also ...
- 333
35
votes
2
answers
8k
views
Is AES-128 quantum safe?
I've been reading lately some contradicting messages with regards to the quantum-safe resistance of AES128. First, there are blog posts by Ericsson people like these ones:
Can quantum attackers break ...
- 675
1
vote
1
answer
69
views
Basis matrix of NTRU lattice
In NTRUEncrypt, we choose polynomials $\mathbf f,\mathbf g$ (with suitably small coefficients) such that $\mathbf f$ admits inverses $\mathbf f_p, \mathbf f_q$ with respect to the moduli $p,q$. The ...
2
votes
1
answer
99
views
Dense sphere packings and lattice-based cryptography
It is known that there are two popular applications of lattices: dense sphere packings and lattice-based cryptography. I didn't find any information on the Internet about possible interaction of these ...
- 327
1
vote
1
answer
87
views
Forward-Secure AKE based on post-quantum KEM?
I am looking for authenticated key exchange protocols (AKE) based on a generic key encapsulation mechanism (KEM) and providing full/perfect forward secrecy. Optionally, the protocols should offer ...
- 11
0
votes
1
answer
46
views
MITM against NTRU
In MITM attacks against the NTRU cryptosystem, we exploit the fact that in the ring of truncated polynomials of degree $n-1$ it holds that $$fg=h\mod q$$ for our secret and public keys $f,h$. The ...
1
vote
1
answer
77
views
value bound of r⋅e for LWE Decryption correctness
For LWE decryption, Someone told me that If we can bound r⋅e by q/4 then we can retrieve M by checking if this is closer to <...
- 121
1
vote
0
answers
46
views
Is it possible to derive Private key from RSA public key with sufficiently powerful Quantum computer? [duplicate]
Is it possible to derive private key directly from public key alone using a powerful Quantum computer.
2
votes
0
answers
106
views
Post Quantum Cryptography - Verifying if there are no backdoors in these selected algorithms: crystals-kyber, crystals-dilithium, falcon, sphincs+
I was looking through https://csrc.nist.gov/projects/post-quantum-cryptography/selected-algorithms-2022
How can one begin to mathematically verify if there are no backdoors to these selected post ...
- 2,197
3
votes
1
answer
474
views
What asymmetric encryption to use that is safe against quantum computers?
i am currently searching for a post-quantum, asymmetric encryption since I need to keep a few files safe for the next decades.
AES 256 is what I am using currently, but I would like to leverage the ...
1
vote
1
answer
137
views
Encryption and decryption for LWE
For https://asecuritysite.com/public/lwe_ring.pdf#page=9 , could anyone explain how the encryption and decryption for LWE work ?
When I do more reading on https://summerschool-croatia.cs.ru.nl/2015/...
- 121