Post-Quantum Cryptography: slide deck released under CC license

[Nadim Kobeissi]

Hello everyone,

I recently finished an ambitious slide deck that aims to cover the topic of post-quantum cryptography in a way that is comprehensive and up-to-date, while remaining highly pedagogical and accessible to its target audience of senior undergraduate students, engineers, and any technical enthusiast that is interested in the topic.

The slide deck was created for the Applied Cryptography course at the American University of Beirut, and may be accessed here:

https://appliedcryptography.page/slides/#2-6

My hope is that this slide deck will serve as a strong, up-to-date foundation for anyone looking to give a two-to-three hour lecture on post-quantum cryptography.

Bonus: the slides and their LaTeX source code are available under the relatively permissive Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license. This means that you can use the slides in many contexts! Here is the source code:

https://cedarcrypt.org/nadim/appliedcryptography/src/branch/main/slides/2-6.tex

I hope that you will find these slides useful. If you have any feedback regarding the slides, I’d love to hear it!

Thanks,

Nadim Kobeissi
Symbolic Software • https://symbolic.software

[Tommaso Gagliardoni]

Nice slides! May I suggest a little edit? When citing the need of doubling symmetric keysize to account for Grover's algorithm, I think the speedup is different when considering hash collision resistance, because the BHT algorithm finds collisions in O(n/3) rather than O(n/4) as one would expect at a first glance. In other words, SHA-256 can be replaced by SHA-384 rather than SHA-512 for the same security level. This is oversimplifying a lot of things of course, including whether Grover and BHT are applicable given the lack of parallelism, or whether SHA-256 is a good hash function or not, or whether one should rather use the Challoux et al.'s algorithm from 2017, etc.
In any case, I guess the decision of whether such distinction is relevant for didactical slides or not is not simple. Ultimately, I think it depends on the intended audience: I have seen practicioners puzzled by this small incongruence when suggesting hash size parameters, and you know how much practitioners care about hash/keysize, so I think it would be useful to add this at least as a footnote.

Cheers,
Tommaso

[Ivan Mclean]

Good deck.

However I do disagree with the premise in slides 122-124, and specifically #123.

The view that breakage of digital signatures is a "recoverable disaster" seems to be based on the idea that everything is just software, and thus in-field updateable.

It completely ignores the fact that in every commercial device you can think of, all of that SW depends entirely on some foundational, immutable hardware and ROM for all of its security. (Almost every device out there performs secure boot by executing code from ROM, leveraging public keys stored in ROM or fuses, typically using some form of HW crypto accelerator for performance.)

And while we may swap out our phones every couple of years, the upgrade cadence for critical civilian and military infrastructure and equipment is significantly slower and vastly more expensive. (This is particularly ugly when you have ~$20 chips deeply embedded and sprinkled liberally throughout weapons systems, aircraft, cars, satellites and industrial infrastructure worth millions or billions of dollars)

If this foundational security (code signing, secure boot, low level HW services like debug unlock & RMA) is compromised by a working quantum computer, you can update your software until you are blue in the face, but it doesn't change the fact that your systems are irrevocably, irreparably, foundationally broken.

I'd strongly urge an update to the slides - and to this way of thinking about the role of digital signatures and the associated Q-Day impact.

Ivan

The information contained herein may be confidential and privileged attorney-client information or work product intended only for the individuals or entity to whom it is addressed. Any unauthorized use, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please notify me immediately.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/e935a1ae-657a-464b-9629-9421834794ddn%40list.nist.gov.

[Mike Ounsworth]

+1 to this point:

 

> It completely ignores the fact that in every commercial device you can think of, all of that SW depends entirely on some foundational, immutable hardware and ROM for all of its security.

> If this foundational security is compromised by a working quantum computer, you can update your software until you are blue in the face, but it doesn't change the fact that your systems are irrevocably, irreparably, foundationally broken.

 

 

The buzzword “Harvest-Now-Decrypt-Later” has gained media attention. I’d like to propose the buzzword “Trust-Now-Forge-Later” as the signatures equivalent, which covers cases like this one where choice of which roots to trust is set at manufacture-time and cannot be field-updated … or where the update mechanism itself becomes totally compromised at Q-Day.

 

---

Mike Ounsworth

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CABNwLcumeVshpFXPMa%2B17boX564duko9xc4SjA_iU5-HbiHLmA%40mail.gmail.com.

Any email and files/attachments transmitted with it are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

[Nadim Kobeissi]

Dear Ivan,

Thank you, you make an excellent point.

When I made those slides, I was short-sighted in considering only software-based signatures.

I completely understand the problem of immutable hardware and its surrounding considerations, and will modify that portion of the slide deck to better discuss this problem.

Nadim Kobeissi
Symbolic Software • https://symbolic.software

[Blumenthal, Uri - 0553 - MITLL]

> It completely ignores the fact that in every commercial device you can think of, all of that SW depends entirely on some foundational, immutable hardware and ROM for all of its security.

> If this foundational security is compromised by a working quantum computer, you can update your software until you are blue in the face, but it doesn't change the fact that your systems are irrevocably, irreparably, foundationally broken.

 

 

The buzzword “Harvest-Now-Decrypt-Later” has gained media attention. I’d like to propose the buzzword “Trust-Now-Forge-Later” as the signatures equivalent, which covers cases like this one where choice of which roots to trust is set at manufacture-time and cannot be field-updated … or where the update mechanism itself becomes totally compromised at Q-Day.

 

Majority of the readers thing of “sign/trust now” as “authenticate now, and it’s pointless to forge today’s session after 10 years”.

 

Yes, software/firmware updates is probably the only exception to the above – though again, installing firmware with forged signature of 2025 on a computer in 2035 does not sound extremely plausible (albeit not as impossible as spoofing my TLS session of last year 😉).

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB57390353486FB6E636AE71BE9F57A%40CH0PR11MB5739.namprd11.prod.outlook.com.

[Mike Ounsworth]

Uri,

 

> Majority of the readers thing of “sign/trust now” as “authenticate now, and it’s pointless to forge today’s session after 10 years”.

 

Right, exactly. Hence “Trust Now” not “Sign Now”. Emphasis on the fact that this applies to cases where you have to make some long-term root-of-trust decision now.

 

 

> though again, installing firmware with forged signature of 2025 on a computer in 2035 does not sound extremely plausible

 

I have an ePassport with a 10 year life that begs to differ.

I have customers with satellites in orbit who would beg to differ.

I have HSM hardware on a 10-year replacement cycle that would beg to differ.

Etc.

Even if these things have field-updatable trust stores, this A) introduces extra security concern compared with immutable trust stores, so immutable is a defensible design choice, and B) you have to assume that all things are able to obtain an update before Q-Day, which is also not guaranteed.

 

 

---

Mike Ounsworth

[Nadim Kobeissi]

Hello everyone,

After being emailed by what feels like every cryptographer on the Earth, I’ve pushed the following fixes:

https://cedarcrypt.org/nadim/appliedcryptography/commit/5b02c92e7e69fe22d2b7922140f8bcf57f201365ad6656dddb4bb8cec4a2353b

I didn’t address every comment by everyone, but only what I felt was important/relevant/within the scope that makes most sense for the intended audience of senior undergraduate students/curious engineers.

Thanks, everyone!

Nadim Kobeissi
Symbolic Software • https://symbolic.software

[Hugo Scolnik]

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/1A563580-38EA-489B-AB57-C4DFD0AB553C%40symbolic.software.

Thank you for sharing the interesting slides. What I would like to see are references to PQC algorithms based on non-commutative algebras that are both fast and NP-hard.

Best

--

 Hugo D.Scolnik Ph.D.
Consultant Full professor
Computer Science Department
School of Sciences
University of Buenos Aires
www.dc.uba.ar

[John Jiang]

Thanks for the great summary and overview. Slide 12 suggests that hash functions and symmetric cryptography are equally weakened by Grover's. If that's the case, wouldn't increasing (key) sizes cure all? Why do we need FIPS 204 and 205 (ML-DSA and FN-DSA)? I'm no cryptographer and am puzzled.

My expertise is on the quantum side. I'd say

1. The estimate of the Q date on slide 14 and 15 is too conservative. Or my estimate is too optimistic for reasons explained below.

2. I'd disagree with the explanation of how quantum computing works on slide 3 although it agrees with what the majority of physicists say.

First, quantum computers are the destination of high performance computing instead of a nice option. Hardware development will speed up. One reason is that shrinking transistor sizes of semiconductor chips has reached the limit. To go smaller, the only choice is to use (electrons in) single atoms instead of transistors to hold data. The newer types of qubits, neutral atoms and ion traps, are a lot more promising than the superconductor types, which use large sized pseudo particles and can only be good for demonstration and prototyping.

Second, people have had a wrong understanding of how quantum computing works and have had no systematic ways of developing quantum algorithms. Had people known how to develop algorithms, quantum computers would have been in higher demand, and faster hardware progress (with more investment) would have made.

Citing the superposition, entanglement and parallelism characteristics of qubits on slide 3 is not wrong. But they don't explain anything. If one or a few electron qubits possess these characteristics, don't transistors with quadrillions of electrons possess the same? The deeper reason is that ideal qubits are controllable and noise free. We can control individual electrons trapped in atoms or ions. Quadrillions of electrons are mostly controllable in the neat lattices of semiconductor crystals. But shrinking the size of a transistor below 2nm, the neat lattice is no longer there, and the electrons are no longer well controlled.

Semiconductor chips operate at room temperatures and have unavoidable thermal noise. Qubits have to be chilled to sub-Kevin temperatures. Noise and the resulting errors are the factor that keeps the available hardware devices from reaching their theoretical ideal. A noise free hardware device can carry infinity bits of data. An ideal qubit is such a device in theory. In Shor's algorithm, you can see that qubits can carry rational numbers e.g. 1/r and compute them. In Grover's, you can see that the tiny fraction of Hash(x*)/sqrt(N) can be kept by qubits and added up.

Hope I'm not side-tracking too much on the hardware side. But I hope to contribute to a better understanding of how quantum hardware works.

Y. John Jiang

[Nadim Kobeissi]

Hi everyone,

First, thanks for all your kind words regarding my slide deck! I certainly had to brush up on a lot of specialized topics in cryptography before I was able to finish it.

I’ve been receiving many comments regarding the deck (mostly in private) with opinions and feedback. I just wanted to note the following:

- I completely welcome these comments, keep them coming.

- However, I won’t address every single one of them, because:

    a. Some are basically purely opinions and can be debated,

    b. Some are too specific and esoteric to be relevant for slides meant for a general introductory session in an undergraduate course,

    c. Some may contain details that again are not worth adding for an introductory session that’s already stretching very long (2 hours+ for 130+ slides!),

    d. Etc.

This doesn’t mean that I’m not reading/ignoring your comments! I just need to filter the feedback and only make the additions and changes that are relevant for the purposes of this slide deck. If I address all your comments, I’ll end up with a 300-page deck that is at once targeting undergraduate students and highly specialized PQ researchers, and that honestly may not flow very well.

So, yes, keep them coming, but don’t expect all of the comments to be integrated or to receive a reply. Thanks.

Nadim Kobeissi
Symbolic Software • https://symbolic.software

[Q R]

Hi Nadim and thank you for the slides.

Here are some items for consideration:

1. Was there a reason to not include LMS in the XMSS discussion?

2. It would be nice to see a HW example - like an HSM and what is being done to make it quantum - safe - since you covered protocols (TLS) and SW (Apple and Signal).

3. What is the definition of quantum - safe? For example, does it mean that every part of the system is quantum secure and you have no classical cryptography in it (unless it is hybrid-PQC)? Let's take an HSM. Does everything from secure boot to silicon components containing classical only need to be updated to be considered quantum-safe? I wish there were more descriptions of this somewhere because how does keeping classical alongside PQC impact security given the weakest link principle?

Thanks Q

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/4990E9FF-37B1-414F-BF1E-EF70B48B8360%40symbolic.software.

[Daniel Apon]

Q wrote:

“ Does everything from secure boot to silicon components containing classical only need to be updated to be considered quantum-safe? I wish there were more descriptions of this somewhere because how does keeping classical alongside PQC impact security given the weakest link principle?”

The ‘weakest link principle’ is the right idea abstractly.

Various components of a total system can be validated as quantum-safe by that principle.

For example, hybridizing ML-KEM with your favorite ECC key exchange gives a quantum-safe key establishment mechanism conditioned on using an appropriate key derivation function to merge the two key-bit-strings on the receiver’s end.

That component can be independently verified as quantum-safe. Other components of a system can each be verified independently as (minimally) quantum-safe or not in a similar way.

Note that different types of system components have different types of requirements to be minimally quantum-safe, yes? eg, KEMs are one realm; signatures another; secure boot another; SCA/physical-tamper resistance another; etc.

But for an entire system, obviously you not only need to verify each separable mechanism in the system (eg, in addition to any KEM, also secure boot like you mention, etc etc). Further, the composition of these components together into a full system must be vetted.

In the cryptographic literature, the proper notion is probably UC (universal composability), at least in theory land. In the real world, you don’t necessarily need UC, because you have a fixed system that operates in a particular way (take care to consider how use of the system would potentially evolve over a future decade or three). But UC is certainly a very powerful tool.

But more broadly in the real world, UC may not necessarily indicate all of the potential considerations need to guarantee end-to-end quantum-safety of a full system (in the real world, there is hardware, with many details; in the real work, there are humans using these systems, etc).

So, various quantum-safety certifications can be made about various components of a total system; eg getting a system component through CAVP/CMVP processes. But in terms of broader understanding (going into slides), the more information and the more context, always the better, imo..

Cheers,

—Daniel Apon

da...@anduril.com

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CACz_hZdG9G6NW8Zp-ZeXKyubRBbw4HADgQZwAkzD4%3DR0SipZ_A%40mail.gmail.com.

[John Jiang]

AWS claims its HSM supports PQC. It may be used as an example.

https://aws.amazon.com/blogs/security/aws-post-quantum-cryptography-migration-plan/

I also have a question or comment on Slide 110. It says Digital Signature is not vulnerable to Store Now, Decrypt Later. It is true if one takes "decrypt" literally and is not true otherwise. If A sends B a bitcoin, the output of the transaction is signed by A. E can store the transaction, (in reality, the transaction is widely available), and re-write the transaction with a forged signature of A.SNDL threatens all non-repudiation use cases.

Y. John Jiang

[Tim Hudson]

On Fri, Jul 18, 2025 at 7:26 AM John Jiang <y...@xanatech.com> wrote:

AWS claims its HSM supports PQC. It may be used as an example.

https://aws.amazon.com/blogs/security/aws-post-quantum-cryptography-migration-plan/

To be precise, AWS notes that it is working on having HSM support for PQC - not that HSM support for PQC is already in place.

Workstream 3 is where that work is being addressed.

If you read the documentation at https://docs.aws.amazon.com/kms/latest/developerguide/create-cmk-keystore.html it still notes that only symmetric keys can be created in a backing HSM with AWS KMS.

What AWS notes is its KMS supports ML-DSA but does not claim that its HSM supports any PQC algorithms as yet (at least in the public documentation). 

The underlying HSM technology at https://csrc.nist.gov/projects/cryptographic-module-validation-program/certificate/4703 and https://csrc.nist.gov/projects/cryptographic-module-validation-program/certificate/4884 are relevant documents as is https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/validation-search?searchMode=implementation&vendor=amazon&productType=1&ipp=25 and https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/details?product=19610 in terms of looking at what technology has made it through algorithm testing for hardware modules). 

If anyone has pointed to a shipping HSM with FIPS140-3 validated PQC inside it as a hardware module type, that would be a useful reference to have.

Tim.

[ji...@crypto4a.com]

Hi Tim,

 

  When you say “FIPS 140-3 validated PQC” are you referring to the

  device having completed the FIPS certification process completely,

  or is it sufficient to be in the MIP queue for FIPS 140-3 certification

  with ACVP certification of the PQC components of the device?

 

  If it’s the former then I don’t think you’ll find an example device

  given the first availability of PQC CAVP certification was last

 August and it’s ~18 months to get through the MIP queue.

 

  If it’s the latter then I’ll mention the Crypto4A QxHSM and QxEDGE

 devices which use the QASM module that was submitted to the

  MIP queue in March 2025, and which has been fully certified for

 all NIST PQC algorithms (see CAVP certificate A5631).

 

  Furthermore, this device also uses quantum-safe roots of trust based

 on HSS (it’s actually a hybrid root of HSS and ECDSA) to provide a

 true quantum-safe update process which has been in place since the

 first device was manufactured 7 years ago, so at no point has it

 ever been reliant on only classic cryptographic algorithms (i.e.,

 RSA and/or ECC).

 

  Take care.

 

Jim

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CANKrMkiAV%2BPMhh%3D-DMKhyme%3DiRmcLMd64bwhLoerQnC8TPdjHQ%40mail.gmail.com.

[Tim Hudson]

On Fri, Jul 18, 2025 at 9:00 AM <ji...@crypto4a.com> wrote:

Hi Tim,

 

  When you say “FIPS 140-3 validated PQC” are you referring to the

  device having completed the FIPS certification process completely,

  or is it sufficient to be in the MIP queue for FIPS 140-3 certification

  with ACVP certification of the PQC components of the device?

I was being very clear in my terminology usage - "If anyone has pointed to a shipping HSM with FIPS140-3 validated PQC inside it as a hardware module type, that would be a useful reference to have."

Anything in-process is by definition outside the scope of what I'm talking about.

FIPS140-3 validated HSMs containing validated PQC algorithms (specifically in the context of the email for FIPS 203, FIPS 204, and FIPS 205) are coming - they are not yet here from the point of view of end customer usage.

There are products in process for sure. And there are early release products with non-validated PQC algorithms. 

But we aren't yet there with the lastest PQC algorithms in validated HSMs. 

Tim.

[Bas Westerbaan]

On Tue, Jul 15, 2025 at 6:41 PM 'Mike Ounsworth' via pqc-forum <pqc-...@list.nist.gov> wrote:

+1 to this point:

 

> It completely ignores the fact that in every commercial device you can think of, all of that SW depends entirely on some foundational, immutable hardware and ROM for all of its security.

> If this foundational security is compromised by a working quantum computer, you can update your software until you are blue in the face, but it doesn't change the fact that your systems are irrevocably, irreparably, foundationally broken.

 

 

The buzzword “Harvest-Now-Decrypt-Later” has gained media attention. I’d like to propose the buzzword “Trust-Now-Forge-Later”

Ship now/regret later :P.

 

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB57390353486FB6E636AE71BE9F57A%40CH0PR11MB5739.namprd11.prod.outlook.com.

[Watson Ladd]

On Tue, Jul 15, 2025 at 10:15 AM 'Mike Ounsworth' via pqc-forum
<pqc-...@list.nist.gov> wrote:
>
> Uri,
>
>
>
> > Majority of the readers thing of “sign/trust now” as “authenticate now, and it’s pointless to forge today’s session after 10 years”.
>
>
>
> Right, exactly. Hence “Trust Now” not “Sign Now”. Emphasis on the fact that this applies to cases where you have to make some long-term root-of-trust decision now.
>
>
>
>
>
> > though again, installing firmware with forged signature of 2025 on a computer in 2035 does not sound extremely plausible
>
>
>
> I have an ePassport with a 10 year life that begs to differ.
>
> I have customers with satellites in orbit who would beg to differ.
>
> I have HSM hardware on a 10-year replacement cycle that would beg to differ.
>
> Etc.
>
> Even if these things have field-updatable trust stores, this A) introduces extra security concern compared with immutable trust stores, so immutable is a defensible design choice, and B) you have to assume that all things are able to obtain an update before Q-Day, which is also not guaranteed.

You assume of course the key is not leakable.

Thankfully hashing=>signatures, so there are signature schemes secure
if the hash function used is secure, ideal for these applications.

> To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB57399FBC7DA3B8CAD46CFD9A9F57A%40CH0PR11MB5739.namprd11.prod.outlook.com.



--
Astra mortemque praestare gradatim

[Ivan Mclean]

To be clear -

- Q-Day assumes full recovery of the root RSA or ECDSA private keys that are responsible for all foundational security of almost every device we can think of today, allowing the attacker to sign whatever primordial image they want, at any time

- The root keys involved are invariably ecosystem-wide keys, governing the security posture of millions or billions of devices

-  so the foundational breakage is invariably also a class break, meaning that all devices sharing the targeted root key are irreparably broken, making such root keys very attractive targets for bad guys

- Such a foundational class break will often provide indirect access to the PQ-encrypted data you had the best intentions of protecting with your "harvest now, decrypt later" defensive strategy (unless the data involved is truly ephemeral, perfect-forward-secrecy protected, it is likely to be persistently stored on a vulnerable box somewhere. And breaking secure boot typically gives you access to the PQ keys)

- Unlike software, hardware development and commercialization lifecycles are really long

- Unlike higher level software, these primordial HW Roots of Trust are typically highly constrained w.r.t. processing and memory resources

 

The last point is really important, because IMO our SW-centric view of the world causes this to be overlooked by compliance standards, government and commercial PQ rollouts. Doing ML-DSA-87 on a highly resource constrained RoT is brutal, and I wish we had more tenable options.

Ivan

[Falko Strenzke]

Moreover, I don't think we can rely on a "warning time window" at the beginning of which we know that a QRQC will exist at the end of that window. In other words: simply waiting for the public information of the existence of a QRQC means running into the situation where authentication will become vulnerable. (Even ignoring any update delay, which might well add at least a few years of delay in many cases, as was discussed.)

 Falko

Am 15.07.25 um 19:14 schrieb 'Mike Ounsworth' via pqc-forum:

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB57399FBC7DA3B8CAD46CFD9A9F57A%40CH0PR11MB5739.namprd11.prod.outlook.com.

--

MTG AG
Dr. Falko Strenzke

Phone: +49 6151 8000 24
E-Mail: falko.s...@mtg.de
Web: mtg.de

---

MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
Commercial register: HRB 8901
Register Court: Amtsgericht Darmstadt
Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
Chairman of the Supervisory Board: Dr. Thomas Milde

This email may contain confidential and/or privileged information. If you are not the correct recipient or have received this email in error,
please inform the sender immediately and delete this email.Unauthorised copying or distribution of this email is not permitted.

Data protection information: Privacy policy