Score:1

Models and assumptions in the post quantum world

tl flag

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!

Score:3
in flag

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.

Titanlord avatar
tl flag
So there are no other "new" models or adjustments to modern concepts, except ROM/QROM?
Maarten Bodewes avatar
in flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.