post_quantum_crypto

quantum cryptography

tl; dr

• almost all public-key cryptography right now could be broken with just a few advances in quantum computing
• the commonly-used public-key algorithms are based: factoring (rsa), finite field discrete logarithms (diffie-hellman), and elliptic curve discrete logarithms (ecdh and ecdsa) - the hidden subgroup problem, which quantum computers are good at solving
• modern design of post-quantum algorithms:
  • make constant-time implementations easy, reducing the risk of timing attacks
  • reduce reliance on random number generators (rngs) by extending nonce values with deterministic functions (shake)
  • implement random sampling techniques for non-uniform distributions, reducing the risk of attacks that rely on biased sampling
  • many are fully deterministic in their input reducing nonce reuse issues
  • many are designed to allow quick and easy generation of new keys, making it easier to provide forward secrecy

---

shor's algorithm

• how quantum computers break encryption: shor's algorithm explained (video)
• when will a quantum computer running shor's algorithm be used to factor one of the rsa numbers for the first time?

---

nist post-quantum cryptography standardizations

general resources

• nist's pqc standardization process: second round candidate announcement
• minimum quantum assumptions for cryptography workshop, simons institute
• nist's transition to post-quantum cryptography standards, by d. moody et al. (nov/2024)

bike

• bit flipping key encapsulation (BIKE)

sike

• supersingular isogeny key encapsulation (SIKE)

---

quantum key distribution (qkd)

• prototyping post-quantum and hybrid key exchange and authentication in TLS and SSH
• uncloneable cryptography, by o. sattah (review talking about quantum money and uncloneable forms of encryption)

---

applications

• apple implements pq3 on imessage
• signal implements x3dh (named pqxdh)