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
8 votes

Why did post-quantum key exchanges go extinct?

I do not see any post-quantum key exchange that creates a shared secret with the contributions of both parties, like in Diffie-Hellman. Actually, in Kyber, the shared secret is a function of ...
poncho's user avatar
  • 148k
8 votes

Why did post-quantum key exchanges go extinct?

Principally because NIST did not make key exchanges a necessary part of the process. If we look at the NIST PQC FAQ "NIST provided APIs and security definitions for Public Key encryption, KEM, ...
Daniel S's user avatar
  • 23.9k
8 votes
Accepted

What are the public key and output sizes for the four remaining PQC KEM candidates?

Throughout this answer the following conventions are used: CT = Ciphertext or transmitted output of the encapsulation algorithm PK = Public key or transmitted output of the key generation algorithm ...
SEJPM's user avatar
  • 46.1k
6 votes

Grover algorithm for public key cryptography - FrodoKEM

I am wondering if one can apply Grover algorithm on a key encapsulation mechanism in order to crack the shared key. Here's how Grover's algorithm works (simplified): you take a 'fitness' function (...
poncho's user avatar
  • 148k
6 votes
Accepted

Differences between NewHope-CPA-KEM and NewHope-CCA-KEM

Well, it turns out that a straight-forward implementation of LWE key exchanges is vulnerable to chosen ciphertext attacks, in the case that one side reuses the same private value $a$ multiple times. ...
poncho's user avatar
  • 148k
5 votes
Accepted

CRYSTALS-KYBER versus FrodoKEM, what makes each of them different than the other?

There are a few cosmetic differences but the principal difference is the matrix $A$ in the LWE problem. In Frodo it is consciously unstructured, but in Kyber it has some symmetry. Specifically in both ...
Daniel S's user avatar
  • 23.9k
5 votes

Key Exchange vs Key Encapsulation

Key exchange: I'll use ECC as an example. Alice and Bob generate ephemeral key pairs and sign their ephemeral public key with their static private key, and then send their signed ephemeral public key ...
SamG101's user avatar
  • 613
5 votes

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

I don't understand your concern. It sounds like you are assuming that public (and private) keys in lattice-based key exchange are static? I don't believe this is the case though. So if your bank (or ...
Mark Schultz-Wu's user avatar
  • 13.4k
5 votes
Accepted

Core-SVP Hardness of Kyber

This code is attempting to model the size of the logarithms of the norms of the Gram-Schmidt vectors associated with a BKZ reduced basis under the Geometric Series Assumption where before reduction ...
Daniel S's user avatar
  • 23.9k
4 votes

Security of RSA-KEM against cube root attack

Q1: The random selection should be $\sqrt[3]{n}<m<n$ due to cube-root attack? Suppose $n$ is 2048 bits long. Then $\sqrt[3] n < 2^{700}$. If $m$ is uniformly distributed in $\{1, 2, \dots, ...
Squeamish Ossifrage's user avatar
4 votes
Accepted

Can a KEM shared secret be used directly as a symmetric key?

The algorithms you mentioned use a secure hash function to derive this convenient 32-byte shared secret, but it is not necessarily true that all KEMs will do so. The answer to your three general ...
forest's user avatar
  • 15.3k
4 votes
Accepted

Using XOR to derive a data key for ECIES

As written, it makes an additional security assumption on the symmetric cipher; that the attacker can't flip bits in the key (and modify the ciphertext) to gain some advantage. That is likely true ...
poncho's user avatar
  • 148k
4 votes

Confusion in the security level offered by KYBER

I think you are looking at the wrong metric. You need to look at the number of classical gates (second row from the bottom). NIST in https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/...
honzaik's user avatar
  • 452
3 votes

Forward-Secure AKE based on post-quantum KEM?

It is possible to generically add FS to any AKE. BN11 describes a compiler. The caveat is that if you permit ephemeral key revelation in your security model (as is usually permitted in the Canetti-...
rozbb's user avatar
  • 430
3 votes

Why did post-quantum key exchanges go extinct?

As others have mentioned, in lattice-based key exchange the derived secret is a function of contributions of both parties. In fact, the standardized algorithms are very "diffie-hellman-like" ...
Mark Schultz-Wu's user avatar
  • 13.4k
3 votes

Error Correcting Codes Post Quantum Finalists

I want to investigate ECC/fault detection in hardware (or more accurately their lattice counterparts), specifically with one of the NIST finalists. Does anyone have any insights into this sector of ...
poncho's user avatar
  • 148k
3 votes
Accepted

How does TLS with PQC use key encapsulation?

As there don't seem to be any PQC alternatives for Diffie-Hellman (DH / ECDH), DH must have been replaced by key encapsulation using an ephemeral key pair. I don't believe that is correct; a ...
poncho's user avatar
  • 148k
3 votes
Accepted

Key transport vs key encapsulation?

Key encapsulation or key wrapping is the encryption of a key with another key. There may be a symmetric key or asymmetric key pair that encapsulates the key destined for transportation; this key can ...
Maarten Bodewes's user avatar
  • 93.1k
3 votes
Accepted

Doing RSA-KEM with RSA-OAEP

If what you have is a machine that computes RSAES-OAEP and not a machine that computes $x \mapsto x^e \bmod n$, you don't really have the tools to do RSA-KEM. You're better off doing what you were ...
Squeamish Ossifrage's user avatar
3 votes
Accepted

Why did NIST Post Quantum Standardization have 2 schemes?

I'm not sure what you mean by “scheme” and “cipher”: the exact definition of what is considered different schemes or different cipher can vary. But whatever your definition is, not all schemes are ...
Gilles 'SO- stop being evil''s user avatar
3 votes
Accepted

Kyber and Classic McEliece as Public Key Encryption algorithms

Yes and no. Kyber and Classic McEliece refer to specific protocols which are KEMs, so in an obvious and boring sense neither one works as a PKE since a KEM does not take a message as an input. But, ...
Sam Jaques's user avatar
  • 1,202
2 votes

Use RSA keys to derive AES key

With RSA-KEM,* the sender knows a modulus $n$ and a public exponent $e$, and the receiver knows the private exponent $d \equiv e^{-1} \pmod{\phi(n)}$. To send a message $m$, the sender picks $0 \leq ...
Squeamish Ossifrage's user avatar
2 votes

How does TLS with PQC use key encapsulation?

CSIDH can serve as a drop-in replacement for the (EC)DH key-exchange protocol while maintaining security against quantum computer. Moreover, OQS modified openssl library to use the liboqs. The TLS was ...
jmr's user avatar
  • 95
2 votes
Accepted

Does CCA security require rejection?

It's hard to say for certain whether "mauled ciphertexts are undetectable" in a KEM -- this is presumably a security property, so one would need a formal security definition and proof (and ...
Mikero's user avatar
  • 13.4k
2 votes
Accepted

Kyber-CCA-KEM - Deterministic implicit rejection

Let me assume that you want to use the following decapsulation algorithm: On input $sk$ and $c$: let $m' = \mathrm{Dec}(sk,c)$ if $m' = \bot$ or $\mathrm{Enc}(pk,m';G(m')) \neq c$, then return $H(sk,...
xagawa's user avatar
  • 2,156
2 votes
Accepted

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

You can usually compress the key generation of a few primitives to the generation of a suitably long secret random seed. Then use a PRG to derive as many seeds as needed. Each resulting seed then ...
Marc Ilunga's user avatar
  • 3,308
2 votes

What scheme is the best for combining two shared secrets?

As a rule of thumb, when you're combining two values, there's a risk if a simple relationship between the values can be observed in the combination. In your first two schemes, if ...
Gilles 'SO- stop being evil''s user avatar
2 votes
Accepted

CRYSTALS-Kyber Compress and Decompress function role

One way to interpret the "discarding low order bits" remark is to think of ciphertexts under various moduli as corresponding to binary floating point values in the range $[0,1)$. The ...
Daniel S's user avatar
  • 23.9k
1 vote
Accepted

Are RSA-KEM key exchange material cyphertexts indistinguishable from random noise?

The RSA function is a permutation from x to c=(x^e)%N. Assuming the plaintext integer x is ...
Richard Thiessen's user avatar
1 vote
Accepted

Two way key transport?

There is some security value insofar as in a one-pass scheme the encapsulator has to trust that the decapsulator has securely generated their public/private key pair. It's not clear how much ...
Daniel S's user avatar
  • 23.9k

Only top scored, non community-wiki answers of a minimum length are eligible