1
$\begingroup$

I'm currently trying to get an overview of post-quantum cryptography. Now I'm struggling with correlations and adjustments of the PQ-world and the Modern-world of cryptography.

My Questions:

  1. Can you give me a brief overview of new important assumptions in the PQ-world (e.g. something similar to the factorization or discrete logarithm assumption)?

  2. Can you give me an overview about new models / adjustments to current models (e.g. random oracle vs. quantum random oracle)?

A short explanation would be nice, too. But for me it is important to get an overview, so that I don't forget anything relevant. Thank you in advance!

$\endgroup$

1 Answer 1

3
$\begingroup$

Can you give me a brief overview of new important assumptions in the PQ-world (e.g. something similar to the factorization or discrete logarithm assumption)?

The factorization and discrete logarithm problem are mathematical "problems" that are used to create the base security for the RSA and DH algorithms. You could think that the algorithms that rely on these problems as "families" of algorithms. In that case DH and ECDH would be part of the same family as they use the same mathematical problem, even though they use separate domains to achieve their goal.

Similar families are known for Post Quantum Cryptography:

  • Lattice-based (e.g. CRYSTALS-Kyber and CRYSTALS-Dilithium);
  • Code-based (e.g. Classic-McEliece);
  • Isogeny based (e.g. SIKE);
  • Multi-variate based (e.g. Rainbow);
  • Hash-based (e.g. SPHINCS+);

Can you give me an overview about new models / adjustments to current models (e.g. random oracle vs. quantum random oracle)?

The Random Oracle Model (ROM) cannot reflect the ability for performing quantum analysis. Therefore a new model called the Quantum-accessible Random Oracle Method can be used instead. This covers the ROM with the new abilities provided by quantum computing, and algorithms can be proven using QROM that cannot be covered by ROM.

Note that neither models provide proofs in the standard model, i.e. algorithms that are proven secure are only secure in that specific model. That's to be expected; RSA and ECDSA cannot be proven secure in the standard model either, as we cannot prove that factorization or solving the discrete logarithm problem is actually hard.


You can find more information in the paper "Random Oracles in a Quantum World" by ENISA which author list includes e.g. Tanja Lange. The ENISA paper references the paper "Random Oracles in a Quantum World" by main author Dan Boneh. Tanja has posted a series of videos on PQC families on YouTube if you want to dive deeper into the mathematics behind the different families.

$\endgroup$
2
  • $\begingroup$ So there are no other "new" models or adjustments to modern concepts, except ROM/QROM? $\endgroup$
    – Titanlord
    Apr 26, 2022 at 12:40
  • 2
    $\begingroup$ Well, I'd look into the FO-transform, the FS-transform, OTS (One-Time signature) and FTS, but they are not so much models but structures used to obtain the security. The whole of chapter 3 of the ENISA paper is on topic here: SECURITY NOTIONS AND GENERIC TRANSFORMS. $\endgroup$
    – Maarten Bodewes
    Apr 26, 2022 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.