Skip to main content
30 votes

Kyber and Dilithium explained to primary school students?

I'll take that challenge for Kyber, but I fear that a simplification of Dilithium could more easily lead to a dangerous understanding. I'm going to describe a cryptographic design, mini-Kyber, that is ...
Daniel S's user avatar
  • 24.1k
13 votes

Kyber and Dilithium explained to primary school students?

Despite Daniel's valiant effort I think the correct answer is no, you can not with reasonable effort explain the inner workings of post quantum cryptography to most primary school students. You should ...
Meir Maor's user avatar
  • 11.8k
10 votes

Why did NIST select Kyber and Dilithium?

NIST did consider the MATZOV attacks. If we read their Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, we see in section 4.1.1 on page 29: During the ...
Daniel S's user avatar
  • 24.1k
6 votes

Kyber PKE correctness proof, how is triangle inequality used

They must be using the $\|a\|-\|b\| \le \|a+b\|$ variant of the triangle inequality (see Wolfram MathWorld). For those of you following along, this is all at the end of page 5. They start with the ...
Mikero's user avatar
  • 13.9k
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
  • 24.1k
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
  • 24.1k
4 votes
Accepted

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
  • 467
3 votes
Accepted

KYBER.CPAPKE: IND-CCA Security of Lyubashevsky, Peikert, Regev (LPR) Encryption

. It seems like neither KYBER.CPAPKE nor its plain ring analogue are IND-CCA1/2 secure Yes, it's a true statement. You might have already noticed the CPA in the KYBER.CPAPKE name. And your ...
DannyNiu's user avatar
  • 9,509
3 votes

Matrix parsing in Kyber

Update: NIST has stated (at the fifth NIST PQC Standardization conference) that they intend to extend the official API to XOF so that an application (such as Kyber) will be able to generate (squeeze) ...
poncho's user avatar
  • 149k
3 votes

Related to ntt implementation in crystal kyber

While not an answer to your question, a little background on DFT/FFT/NTT. If you understand these well, you can write your own implementation without too much trouble. DFT/FFT In a field $\mathbb{F}$...
yoyo's user avatar
  • 420
3 votes

Kyber and Dilithium explained to primary school students?

Some popular science resources: A video game depicting lattice-based encryption (so, something close to Kyber): https://cryptris.nl/index_en.html And some more mathy explanations that goes with it (...
LeoDucas's user avatar
  • 1,253
3 votes

Explanation of the tables found in Kyber round1 code?

As you can see in the comment of the code, the tables have been computed using Pari/GP, which mean you could regenerate them using the same code. The details can be stitched together from this Kyber ...
Lery's user avatar
  • 7,749
3 votes
Accepted

Break Lattice-Based Cryptography with Variational Quantum Algorithm (only 25 k. Qbits for Kyber1024)?

While I'm not a quantum computing expert, typical estimates for RSA/DLOG are on the order of ~2k (logical) qbits, so depending on whether you mean physical/logical your numbers might be off. Their ...
Mark Schultz-Wu's user avatar
  • 13.6k
3 votes

Question on the Implementation of Kyber's NTT in the Reference

The first formula you describe is the formula to compute an NTT using what is known as the "Gentleman-Sande Butterfly" (also known as "Decimation in Frequency"). The code you quote ...
Mark Schultz-Wu's user avatar
  • 13.6k
3 votes
Accepted

High Hamming Weight Attack on Kyber

*-LWE systems are all based around the idea of adding "noise" to a constrained linear system. Any non-zero noise will prevent the linear system being directly solvable using linear algebra ...
Daniel S's user avatar
  • 24.1k
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
Accepted

Question about Theorem 2 in CRYSTALS-Kyber Paper

your understanding is correct. If you mean by "what are the parameters" the question "what are the parameters of kyber", it (mostly) doesn't matter. You have some cryptosystem $...
Mark Schultz-Wu's user avatar
  • 13.6k
2 votes

Question on the proof of correctness in CRYSTALS-Kyber

First Bullet Point: Kyber is a "LPR-type" scheme, or often called a "Noisy Diffie Hellman"-based cryptosystem. The main idea is to have Alice send a "Noisy Diffie Hellman&...
Mark Schultz-Wu's user avatar
  • 13.6k
2 votes

Compression and Decompression in CRYSTALS-Kyber

It is probably easiest to understand this without the scaling factor (the general technique works for an arbitrary lattice). Consider the simple lattice $L = \mathbb{Z}^n$. One can uniquely decompose $...
Mark Schultz-Wu's user avatar
  • 13.6k
2 votes

Compression and Decompression in CRYSTALS-Kyber

Firstly, understand that here $B_q$ does not represent the centred binomial distribution, but instead the integer value $\lceil\frac q{2^{d+1}}\rfloor$. Next it might help to think of the compress and ...
Daniel S's user avatar
  • 24.1k
2 votes
Accepted

Why do the game-hops in Kyber and related papers contain 2 steps at a time?

I'm answering my own question here, because i finally found the answer and want to preserve it for future reference. The Bos et al. paper states it more clearly. The define the R-LWE problem as a ...
0kp's user avatar
  • 346
2 votes

Kyber and Dilithium explained to primary school students?

Kyber itself is very simple to understand, at least when things are suitably simplified. The central object is the "matrix-vector" pair $$(A, As + E)$$ which is pseudorandom under a suitable ...
Mark Schultz-Wu's user avatar
  • 13.6k
2 votes

LWE KEMs and message coding

In the case of lattice-based public-key encryption, the answer is mostly "no". For security reasons, we need $n\geq 512$ (roughly). If we assume the moduli $q$ is a free parameter, then we ...
Mark Schultz-Wu's user avatar
  • 13.6k
2 votes
Accepted

Matrix parsing in Kyber

How can $\operatorname{SHAKE-128}$ be used to generate the (possibly non-terminating) bytes stream of indeterminate length required by the parse function? $\operatorname{SHAKE-128}$ has the property ...
fgrieu's user avatar
  • 143k
2 votes
Accepted

Composition of ciphertexts in post quantum schemes Kyber and Frodo

Wouldn't it be sufficient to work with only one, which "hides" the message, that is in Kyber $v$ and in Frodo $C_2$? Actually, they are both taking a similar approach to El Gamal. With El ...
poncho's user avatar
  • 149k
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,176
2 votes
Accepted

Parse Algorithm in Kyber Specification

I will try to answer as best I can, but I am no expert on the topic. Saying $\hat f$ is the NTT representation of $f$ is just saying that $\hat f=\mathsf{NTT}(f)$. The parse algorithm uses rejection ...
lamontap's user avatar
  • 940
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,383
2 votes

NTT - Transformation of Polynomials in Kyber

This is explained by the fact that in the linked post, the upper limit in the product is misquoted. Per page 5 of the original Kyber documentation we have $$X^{256}+1=\prod_{i=0}^{127}\left(X^2-\zeta^{...
Daniel S's user avatar
  • 24.1k

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