Post Quantum Cryptography (Post Quantum Safe)

Post Quantum Safe Cryptography

Cryptographic algorithms that are secure against a cryptanalytic attack by a quantum computer running Shor’s Algorithm or better (in terms of number of qubits required) alternatives

Quantum Algorithms

Shor’s Algorithm

• Developed in 1994 by Peter Shor
• can be used to break certain instances of period-finding problems (which are instances of Hidden Subgroup Problem (HSP)), including:
  • Integer Factorization
  • Discrete Logarithm Problem (DLP)

Grover’s Algorithm

• Developed by Lov Grover in 1996
• an algorithm for unstructured search that finds, with high probability, the unique input to a black box function that produces a particular output value
• use $O(\sqrt{N})$ evaluations of the function, $N$ is size of the function’s domain
• In comparison to classical computation (non-quantum computation), the problem cannot be solved in $<O(N)$ evaluations
• thus Grover’s algorithm gives at most a quadratic speedup
  • i.e. use Grover’s to brute force:
    • a 256-bit symmetric cryptographic key in ~$2^{128}$ iterations
    • a 128-bit symmetric cryptographic key in ~$2^{64}$ iterations

Non-Quantum Safe Cryptography

• cryptographic algorithms based on:
  • Integer Factorization
  • Discrete Logarithm Problem (DLP)
  • period-finding problem

Quantum Safe Cryptography

• cryptographic systems that are resistant to quantum-based attacks
• 6 approaches are considered Quantum Safe
  1. Latticed-based Cryptography (NIST promoted cryptography)
  2. Multivariate Cryptography
     • Rainbow cryptosystem based on Unbalanced Oil and Vinegar
  3. Hash-based Cryptography
     • Lamport signatures
     • Merkle signature scheme
  4. Error Correcting Code-based Cryptography (NIST promoted cryptography)
     • McElience
     • Niederreiter
       • Courtois, Finiasz and Sendrier Signature scheme
  5. Isogeny based (NIST promoted cryptography)
     • CSIDH (Commutative Supersingular Isogeny-based Diffie–Hellman)
       • pronounced seaside
       • straightforward quantum-safe replacement for DH and ECDH
  6. Symmetric Key

Harvest Now, Decrypt Later / Retrospective Decryption

• storing currently unreadable encrypted data awaiting for possible breakthrough in decryption technology