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
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
  • 21.9k
3 votes
1 answer
98 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
42 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 Salahi's user avatar
3 votes
2 answers
93 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
117 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
50 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
110 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
32 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
774 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
274 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
1 vote
1 answer
98 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
290 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
190 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
1 vote
1 answer
60 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
161 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
114 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
0 votes
1 answer
101 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
148 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
139 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
104 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
33 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
226 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
36 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
84 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
81 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,125
1 vote
0 answers
25 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
191 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,080
14 votes
5 answers
9k 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
  • 63
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
82 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
44 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
79 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
56 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
123 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
195 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
9 votes
3 answers
3k views

Could tropical cryptography become another candidate for post-quantum cryptography?

According to Wikipedia, tropical cryptographic protocols are built upon tropical algebras, i.e., a semiring $(\mathbb{R} \cup \{\infty\}, \oplus, \otimes)$ where $x \oplus y = \min \{x,y\}$ and $x \...
Iqazra's user avatar
  • 193
1 vote
0 answers
58 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 ...
Lev Knoblock's user avatar
1 vote
1 answer
51 views

Composition of ciphertexts in post quantum schemes Kyber and Frodo

I took a look at the Kyber and Frodo procedures and found that the ciphertext consists of two components. In Kyber these are the lines 5-7 in algorithm 2 $c := (\mathbf{u},v)$ and in Frodo line 8 of ...
Zpeed78's user avatar
  • 95
-7 votes
1 answer
56 views

In the context of a blockchain-based digital currency, I have some questions regarding the functionality and operations of a particular system

Could you clarify where the stack object is typically generated? Is it created on the sender's device or the recipient's device? If I send funds to a multipay stack that was created on another device ...
Hcomber's user avatar
0 votes
2 answers
328 views

Are there any full alternatives to RSA that are quantum-resistant

By full alternatives I mean things that can do everything RSA can, namely establish secure security without privately sharing information prior. Something which AES can't do. In other words, I'm ...
blademan9999's user avatar
2 votes
3 answers
449 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 ...
user110127's user avatar
1 vote
0 answers
188 views

Quantum-safe algorithm for hiding cryptocurrency transaction amount [closed]

I have a decentralized coin system that I am trying to develop. Each coin can be split up into 1,000,000 units. I've been looking for a quantum-safe and practical (efficient) algorithm to send ...
rapt's user avatar
  • 91
1 vote
1 answer
111 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.
Mjf T's user avatar
  • 21
0 votes
0 answers
60 views

Bound for quantum adversary in CRYSTALS-Kyber

In Kyber the following estimation is given for a quantum adversary: Theorem 4. For any quantum adversary $A$ that makes at most $q_{RO}$ many queries to quantum random oracles $H$ and $G$, and at ...
P_Gate's user avatar
  • 403
3 votes
1 answer
248 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 ...
Rohit Khera's user avatar
1 vote
1 answer
90 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 ...
faust's user avatar
  • 13
0 votes
1 answer
218 views

What if LWE is not as secure as we think?

LWE schemes are currently being deployed. LWE has no quantum polynomial time algorithms as far as we know. Despite this what is the consequence if LWE can be broken on a classical computer? Do we ...
Turbo's user avatar
  • 908
1 vote
0 answers
50 views

Error to create PQ certificate in C - x509 certificate routines:X509_PUBKEY_set:unsupported algorithm

I'm learning OQS OpenSSL and I'd like to create a certificate with dilithium in C, using liboqs and OQS OpenSSL. This is my code (based on https://stackoverflow.com/questions/256405/programmatically-...
r4mpz0's user avatar
  • 33
0 votes
0 answers
72 views

Digital signature with challenge and respond with PQC

Can ECDSA signature signing and verification process replaces password hashed based login system? The title of this question won't be exactly right. This is a question that I asked long time ago. I ...
Hern's user avatar
  • 159

1
2 3 4 5
15