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
166 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
38 votes
0 answers
5k 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
69 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
36 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
128 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
7k 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
289 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
1 answer
33 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
63 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
32 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
117 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
208 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
74 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.5k
3 votes
1 answer
118 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
45 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
157 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
129 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
68 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
113 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
849 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
302 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
298 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
220 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
61 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
196 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
138 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
129 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
0 votes
1 answer
184 views

Hybrid key exchange in TLS 1.3

In Hybrid key exchange in TLS 1.3, they mention that with a hybrid approach, we concatenate the shared secret from each method (say KEM like Kyber768 + classical ECDH X25519 = X22519Kyer768). ...
Moo's user avatar
  • 147
3 votes
1 answer
154 views

Implementation of centered binomial distribution in Kyber Key Encapsulation Mechanism?

In the implementation of centered binomial distribution of crystals-kyber, the authors load 24-bits of buffer to a 32 bit integer and then they and the answer with 0x00249249. The complete operations ...
Muhammad Awais's user avatar
2 votes
1 answer
119 views

Use zk-STARK for post-quantum signature scheme?

Could you not use zk-STARK for a post-quantum signature scheme? Your private key is a random symmetric encryption key, your public key is the hash of the encryption key. To sign you run an algorithm ...
LightTunnelEnd's user avatar
1 vote
0 answers
34 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 ...
kerf's user avatar
  • 33
0 votes
2 answers
231 views

NIST PQC: minimum number of digital signatures

I've been checking the NIST PQC documents to find the requirements about the minimum required numbers of signatures to be generated with a signature scheme: NIST call for proposals Call for ...
radix's user avatar
  • 101
0 votes
0 answers
39 views

can ownership proofs be added to circuits to make them zk-snark resistant to quantum proof forgery attacks?

According to my previous question the proofs cannot be broken by quantum computation, you cannot obtain the witness of the generated zk-snark proof. link to my previous question. Now if the concern is ...
dreamer's user avatar
0 votes
1 answer
86 views

can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible?

can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible? I understand the concern that ZK-snarks and some of their cryptography may be broken by quantum ...
dreamer's user avatar
1 vote
0 answers
87 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, ...
Sam Jaques's user avatar
  • 1,137
1 vote
0 answers
28 views

How to convert Lattice based signature to R1CS statements?

How can we convert a lattice-based signature (like based on Fiat Shmair with abort e.g. Dilithium) to R1CS?
Kanchan Bisht's user avatar
1 vote
2 answers
204 views

What's the purpose of implicit rejection

In IND-CCA encryption, one way to ensure semantic security is to return an error symbol on malformed ciphertext. Some post-quantum KEM algorithms however doesn't do this - instead, they return a "...
DannyNiu's user avatar
  • 9,207
14 votes
5 answers
10k views

Does Grover's algorithm really threaten symmetric security proofs?

By Shannon's theorem of perfect security, if I give you a ciphertext 'LOUPL', you can do a brute-force attack and then you would find plaintexts like 'HELLO', 'APPLE', 'SPOON', but you can't ...
Victor Espinoza's user avatar
0 votes
0 answers
38 views

What are the implications for the proof when we substitute matrix multiplication with a bitwise XOR operation in Definition 5.1 (LWE degree-k PRF)?

In the paper located at https://eprint.iacr.org/2011/401.pdf, suppose we replace matrix multiplication with bitwise XOR operations in Definition 5.1 to create an LWE degree-k PRF. I'm seeking ...
DP2040's user avatar
  • 73
2 votes
2 answers
1k views

What is meant by software and hardware implementations of cryptograpic schemes? How to do it?

I have read many cryptographic papers or articles where I have came across about the software and hardware implementation for the cryptographic algorithms. I want to know how its been done. Is there ...
Ganesh's user avatar
  • 21
0 votes
0 answers
95 views

Kyber and Dilithium usage limits?

What are the theoretical usage limits of Kyber and Dilithium? Are there any sources to back this up? Maximum number of encryptions/signatures allowed per key, etc.?
Joe's user avatar
  • 73
1 vote
1 answer
45 views

PRNG to Obtain Random Subset (PORS) Success Probability

PORS (PRNG to ORS) is a secure variant of the HORS few-time signature scheme. In PORS, instead of using a hash function, it uses a message (and salt) as a seed of PRNG and query it until obtains k ...
Emma's user avatar
  • 11
1 vote
1 answer
84 views

Can someone explain in simple terms how coding part and the algorithm itself, of dilithium pqc signature algorithm resemble here?

I am stuck here and can't map the coding part to the algorithm. $$\underline{\text{Power2Round}_q(r, d)}\\ r := r \bmod^+ q\\ r_0 := r mod^\pm 2^d\\ \textbf{return}\big((r-r_0) / 2^d, r_0\big) $$ What ...
Muhammad Awais's user avatar
1 vote
1 answer
72 views

How have the authors performed uniform random sampling for the secret values s1 and s2 in dilithium?

I am currently trying to understand and implement the design of post quantum algorithm signature algorithm Dilithium. I have read the document several times and they have just used uniform random ...
ijaz khalid's user avatar
2 votes
1 answer
126 views

Post-quantum EU-CMA security from OWF-only

In the paper: "Universal One-Way Hash Functions and their Cryptographic Applications". The following is proven: "If 1-1 one-way functions exist, then the one-way based signature scheme ...
Ilk's user avatar
  • 233
2 votes
1 answer
247 views

In dilithium (post quantum signature algorithm), how have the authors precomputed the table of zetas for NTT?

I am trying to understand the design rationale of in place NTT in Dilithium. I know that how the splitting of polynomials is done but I cant seem to map this approach to the precomputed table of zetas ...
ijaz khalid's user avatar

1
2 3 4 5
15