Hot answers tagged

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
  • 22.8k
14 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
  • 22.8k
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
  • 12.5k
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
  • 22.8k
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,080
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,203
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,649
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's user avatar
  • 12.5k
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's user avatar
  • 12.5k
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's user avatar
  • 12.5k
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's user avatar
  • 12.5k
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's user avatar
  • 12.5k
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
  • 22.8k
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's user avatar
  • 12.5k
2 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
  • 391
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's user avatar
  • 12.5k
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,136
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
  • 146k
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
  • 774
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,163
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
  • 22.8k
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

How zetas are computed in CRYSTALS-Kyber?

If the prime is $p=1073692673,$ then the nonzero elements of the field $\mathbb{F}_p$ form a multiplicative group of order $$p-1=1073692672=2^{14}\cdot13\cdot71.$$ The roots of unity in this field ...
kodlu's user avatar
  • 22k
1 vote
Accepted

Hybrid Approaches: ECIES-Kyber768

Is this approach a good idea? I believe your encryption method is to use Kyber to generate a shared secret (using the decryptor's public key), and send that shared secret through a KDF, and then use ...
poncho's user avatar
  • 146k
1 vote
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
  • 140k
1 vote
Accepted

Authenticated Key Exchange of Kyber.AKE

In section 5, the paper states "party $P_1$ knows the static (long-term) key of party $P_2$". You should interpret this as meaning that by unspecified means, $P_1$ is assured that $P_2$ ...
Daniel S's user avatar
  • 22.8k
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
  • 22.8k
1 vote

Questions on difference distribution in Kyber

I like to think of the the compression and decompression function operating on the numerators of fractions in the range $[0,1)$ (wrapped around) whose denominators are either $2^d$ or $q$. The ...
Daniel S's user avatar
  • 22.8k

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