Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
33 views

Meaning of history-free reduction [closed]

I am reading the article "Random Oracles in a Quantum World" by Boneh et al. What does "history-free reduction" mean exactly?
votunglinh's user avatar
0 votes
1 answer
56 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(...
Gappu's user avatar
  • 31
1 vote
1 answer
81 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 ...
Gappu's user avatar
  • 31
2 votes
1 answer
49 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 ...
RIN's user avatar
  • 21
3 votes
0 answers
114 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 ...
Joe's user avatar
  • 81
0 votes
0 answers
22 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 ...
Chris S's user avatar
0 votes
1 answer
88 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 ...
Anas Ahmad's user avatar
1 vote
1 answer
43 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 ...
limeeattack's user avatar
0 votes
2 answers
74 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 ...
qwerty keyboard's user avatar
2 votes
0 answers
59 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 ...
Dai Chi DO's user avatar
1 vote
0 answers
80 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 ...
Gappu's user avatar
  • 31
2 votes
1 answer
125 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?
Hat's user avatar
  • 21
1 vote
0 answers
44 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? ...
limeeattack's user avatar
1 vote
1 answer
134 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 ...
keithRozario's user avatar
3 votes
2 answers
317 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 ...
User0258's user avatar
8 votes
2 answers
599 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 ...
swineone's user avatar
  • 870
2 votes
0 answers
98 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\...
Sam Jaques's user avatar
  • 1,202
0 votes
0 answers
59 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 ...
Gappu's user avatar
  • 31
1 vote
1 answer
73 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: ...
Gappu's user avatar
  • 31
0 votes
0 answers
193 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.
guangyu liao's user avatar
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 ...
Hilder Vitor Lima Pereira's user avatar
1 vote
1 answer
115 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?
Shekhar Sivaraman's user avatar
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 ...
LilLee's user avatar
  • 51
3 votes
1 answer
172 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 ...
VIKAS SRIVASTAVA's user avatar
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 "...
Mark S's user avatar
  • 289
2 votes
1 answer
320 views

Core-SVP Hardness of Kyber

This question is with reference to the python file model_BKZ.py provided in the GitHub repository https://github.com/pq-crystals/security-estimates/blob/master/...
VIKAS SRIVASTAVA's user avatar
0 votes
2 answers
50 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 \...
user avatar
2 votes
1 answer
76 views

Kyber - Compression and Decompression Implementation Example

I have a question about the implementation of the functions $$Compress_q(x,d) = \left\lfloor (2^d/q)\cdot x\right\rceil mod^{+}2^d$$ and $$Decompress_q(x,d) = \left\lfloor (q/2^d)\cdot x\right\rceil$$ ...
TreeBook1's user avatar
  • 117
0 votes
0 answers
33 views

NTT implementation using matrix multiplication

I am trying to implement the NTT as done in this paper, but I keep getting the wrong result even when doing the math by hand. Is formula 9 of the paper wrong ? (I suspect that I am the wrong one but ...
José Miguel's user avatar
1 vote
1 answer
67 views

Does encrypting a billion short and similar jsons with known structure make encryption less secure?

Let's say we have a billion short individual json files with same regular structure: {"name": "<name>", "id": <id>}. Each ...
aackmann's user avatar
4 votes
0 answers
123 views

What are the binding properties of post-quantum KEMs?

Performing a key exchange with post-quantum KEMs is very different to ECDH, which will likely cause vulnerabilities in protocols during the migration to post-quantum cryptography. One example is that ...
samuel-lucas6's user avatar
2 votes
1 answer
217 views

Ring Learning With Errors : why is it called ring and referred it as Ring LWE

I am curious about the structure of the quotient ring in Ring LWE. So $R=\mathbb Z_q[x]/(x^n+1)$, where q is prime, $x^n+1$ is an irreducible polynomial and $n$ is a power of 2. So, this structure ...
user479610's user avatar
3 votes
1 answer
82 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 ...
Jong Hyeok Lee's user avatar
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 ...
kodlu's user avatar
  • 22.6k
3 votes
1 answer
124 views

The weakening of PQC as a result of lack of KEX?

As far as I can tell we don't have any good key exchange post-quantum candidates. SIKE was broken some time ago. It is possible to reach an authenticated shared secret by having the public key holder ...
Squoomsquoom's user avatar
0 votes
1 answer
49 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 ...
R_Jalaei's user avatar
  • 141
3 votes
2 answers
172 views

Quantum attack on CTR

I'm reading the article named "Characterizing the qIND-qCPA (in)security of the CBC, CFB, OFB and CTR modes of operation". An attack on CTR mode is presented in the article. The proof of thm ...
Georgy Firsov's user avatar
0 votes
2 answers
132 views

Are security assumptions based on quantum computers too strict? Causing cryptographers to tie their own hands

Have security assumptions based on quantum computers de facto constrained the emergence and application of many new cryptographic schemes (e.g., fully homomorphic encryption)? It seems to me that, in ...
WAN Lipeng's user avatar
1 vote
1 answer
74 views

How zetas are computed in CRYSTALS-Kyber?

As shown below it explains how generate zetas table and use it. But curious thing is that how KYBER_ROOT_OF_UNITY constant is generated ? I've tried multiple ways to generated it and cannot explain ...
Ali ÜSTÜN's user avatar
1 vote
1 answer
116 views

Why are the primes all the same size in pqRSA?

pqRSA is MP-RSA with 4096-bit primes to build up a modulus of up to 1TB. If the objective is to make processing the modulus as expensive as possible for the quantum computer why not use just two 4096-...
user avatar
1 vote
0 answers
33 views

Bounding the commitment min-entropy of NTRU version of BLISS

I've read [DDLL13] paper and want to understand how the lemma 3.4 is changed for NTRU version of BLISS. In the naive construction of BLISS, the commitment entropy is bounded in Lemma 3.4 as below: $$ \...
dkzlfk12's user avatar
6 votes
2 answers
907 views

Kyber 512 Security Level Issue

So I read parts of the following article: https://blog.cr.yp.to/20231003-countcorrectly.html But I quite dont understand it. NIST assumes Kyber 512 is just as hard as AES128 nowadays, in presence of ...
user112982's user avatar
1 vote
1 answer
321 views

Recursive NTT for Kyber

since the NTT is a variant of the DFT respectively FFT, it seems possible to implement a recursive algorithm for the NTT of Kyber with a divide-and-conquer concept. This is the reason for my question ...
TreeBook1's user avatar
  • 117
1 vote
1 answer
100 views

Is it safe to derive a Falcon512 key pair from a XOF output?

I'm working on a program that requires multiple key pairs from multiple algorithms to be derived from a single 128-byte master seed. However, I couldn't find an implementation for Falcon512 that ...
Zola Gonano's user avatar
6 votes
1 answer
303 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 ...
Ymi's user avatar
  • 175
2 votes
1 answer
231 views

NTT - Transformation of Polynomials in Kyber

In Kyber with $q=3329$, we end up with a field that das 256th roots of unity, when we apply the chinese remainder theorem (CRT) for such a field, it may look like, according to a post here: $$\mathbb{...
TreeBook1's user avatar
  • 117
1 vote
1 answer
62 views

How to write information in the 32-byte addresses of SLH-DSA?

Dear community, I have a technical question regarding the use of the addresses in section 4.2 of FIPS 205, the NIST standard of SPHINCS+. Taking for example the tree address, we want to copy an ...
Emilien's user avatar
  • 13
1 vote
1 answer
219 views

Is it safe to derive Ed25519 and Kyber private keys from the same seed?

I am designing a Hybrid Key exchange library using x25519 and Kyber, and the scheme I have in mind is as follows: Alice sending a file/message to Bob: ...
Zola Gonano's user avatar
1 vote
1 answer
152 views

Parse Algorithm in Kyber Specification

In the Kyber specification there is an algorithm "Parse", which receives a byte stream as input and from this the NTT representation $\hat{a} = \hat{a}_0+\hat{a}_1X + ... + \hat{a}_{n-1}X^{n-...
TreeBook1's user avatar
  • 117
0 votes
1 answer
147 views

How does FORS: Forest of Random Subsets work?

I saw a post named "How does signing with FORS work in SPHINCS+?" but in the post it seems like no one had explain how does the FORS works. SK: Secret Key, PRF: Pseudo-Random Function I'm ...
a15600712's user avatar

1
2 3 4 5
15