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
4 votes
Accepted

Where does the 8 come from? Generic Search Problem with Bounded Probabilities

As the paper states, you should look directly at HRS16, Theorem 1. The proof there seems fairly straightforward, but it seems to depend on theorem 7.2 of Zhandry2012. This itself appears to depend on ...
Mark's user avatar
  • 12.5k
4 votes

Do we need the quantum random oracle model (QROM)?

All models are wrong, but some are useful - George Box The random oracle model (ROM) has proven the test of time insofar as it has proven an accurate/useful assessment of an adversaries capabilities ...
Daniel S's user avatar
  • 22.8k
4 votes

CRYSTALS-Dilithium - How do the supporting algorithms work?

These algorithms are described in the beginning of section 2.4 (and by the way, you might want to use an updated version -- I believe this one is the latest). Decompose works basically like writing a ...
swineone's user avatar
  • 623
3 votes
Accepted

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

I did not try to implement the algorithm myself but those values are powers of $\zeta = 1753 \in \mathbb{Z}_q$ (as hinted by the name) in the Montgomery form where $q = 8380417$ and the elements of $\...
honzaik's user avatar
  • 392
3 votes
Accepted

Meaning of Dilithium-1024x768 or Dilithium2

1024 and 768 refer to the dimension of the base "generator" matrix $A$, these numbers are multiples of 256, which is the size of the module ring. If the terminology is a bit confusing so far,...
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
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
Accepted

What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?

The hardness of SIS (or more precisely, the hardness of the module version of SIS: MSIS) is the assumption used to demonstrated the Strong Unforgeability of Crystal Dilithium under Chosen Message ...
Daniel S's user avatar
  • 22.8k
2 votes
Accepted

Dilithium signature scheme and timing attacks – Does the running time actually depend on the secret key?

The running time does not depend on the secret key. All multiplications, additions, and modular reductions can be implemented to be constant-time. Diving in to the details: The probability of the <...
e-sushi's user avatar
  • 17.9k
2 votes

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

Conceptually what is happening with this algorithm is simple, so I will describe that first. To simplify things, I will simply write $a\bmod b$ rather than $a\bmod^+b$ or $a\bmod^{\pm}b$. I'll mention ...
Mark's user avatar
  • 12.5k
1 vote

How to reconstruct low order bits of $t$ of CRYSTALS-Dilithium from a small number of signatures?

While this doesn't fully answer your question (and is only mildly more interesting than a comment), I think the Dilithium authors just assume the adversary knows $\mathbf{t}_0$. See for example ...
Mark's user avatar
  • 12.5k
1 vote

Are rejected Dilithium commitments secret?

I can't make this into a full attack, but $\mathbf{w}_1$ (using the notation of the Dilithium spec) gives non-trivial information about the secret. It seems to me like recovering $\mathbf{y}$ from $\...
Sam Jaques's user avatar
  • 1,135
1 vote

Basic explanation of Falcon and Dilithium

I don't know where to find examples for Dilithium and Falcon, but I found a toy-kyber code here: https://cryptopedia.dev/posts/kyber/. Hope it will help.
James's user avatar
  • 11

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