The Threat of Quantum Computing

"Quantum supremacy,” as proposed by John Preskill in 2012, was to describe the point where quantum computers can do things that classical computers can’t.

Superposition In Quantum Computing

- As you may know, there are 2 states |1> and |0> happen at the same time

- For short, 10 classical bits are approximately equivalent to 5 qubits.

- We can think of it on a large scale: 64 qubits is equivalent to 128 classical bits.

Entanglement In Quantum Computing

An effect over a single in quantum bit can propagate through entire array.

Threat of Quantum Algorithm over RSA, ECC cryptography

Quantum Computer can solve in polynomial time:

Threat of Quantum Algorithm over RSA, ECC cryptography

• Integer factorization
• Discrete log in finite field
• Discrete log on elliptic field

Quantum Computer can solve in polynomial time:

Threat of Quantum Algorithm over RSA, ECC cryptography

• Integer factorization
• Discrete log in finite field
• Discrete log on elliptic field

Quantum Computer can solve in polynomial time:

=> RSA is dead

=> DSA, Elgamal are dead

=> ECC is dead

• Frankly, algorithm for factorization and discrete logarithm can be solved in a similar fashion.

Both can be solved in polynomial time on a quantum computer.

Threat of Quantum Algorithm over Symmetric Cryptography

Grover's algorithm can thwart classical security bit by a half

• AES-128 is only 64 security bits in quantum computer. Thus, AES-192 is only 96 quantum security bit. 

• SHA0, SHA1 are dead, SHA2 suffer length extension attack due to its Merkle–Damgård structure, SHA3-224 is insecure in quantum era. 

• SHA3-256, SHA3-384, SHA3-512 (published in 2015) are not widely deployed yet.

Need to invalidate AES-128, AES-192 in the government sector. Move to AES-256, deploy SHA3 as soon as possible.

"Quantum Supremacy" may not happen now, but it's expected

"Quantum Supremacy" may not happen now, but it's expected

1. IBM quantum scientists are building a quantum computer with a 1,121-qubit processor, called Condor, inside a large dilution "super-fridge"

2.  Condor lays the groundwork for scaling to fully error-corrected, interconnected, 1-million-plus-qubit quantum computers.

3. In 2021, IBM will debut the 127-qubit "Eagle" chip.

4. Eagle will be followed by the 433-qubit "Osprey" processor in 2022

5. These advances are necessary to establish a Quantum Industry: fabrication, cryogenic, and electronics, software capabilities, error-correction coding.

Situation before 2024

• NIST (National Institute of Standards and Technology) is currently in the process of standardizing a quantum-safe public key encryption system which will be completed by 2024.
• The NSA has followed suit by announcing its CNSA Encryption Suite which is meant to be a transitionary encryption standard quantum-safe encryption becomes standardized.
• The NSA has withdrawn its support of AES-128 and AES-192 as cryptographically secure long-term encryption schemes because of quantum computing

Introduction to Post-Quantum Cryptography

Introduction to Post-Quantum Cryptography

Post-Quantum Cryptography (Mật mã hậu lượng tử):

• Public key cryptography that run on classical computer
• Based on hard cryptography problem that cannot be solved efficiently by quantum computer

NOTE: KEM is Key Encapsulate Mechanism

Lattice-based Cryptography

Lattice-based Cryptography

Security problem relied on Shortest/Closest Vector Problem

NIST finalist KEM selection:

• CRYSTAL-Kyber
• SABER
• NTRU

NIST finalist Signature selection:

• Falcon
• CRYSTAL-Dilithium

Code-based Cryptography

Security problem relied in syndrome decoding

NIST finalist KEM selection:

• Classic McEliece

NIST finalist Signature selection:

• No Code-based submission in Signature category.
• Due to ridiculous signature size. (hundred of Mb)

Only suitable for KEM.

Multivariate Cryptography

Security problem relied in solving multivariate equations.

NIST finalist KEM selection:

• No Multivate submission in KEM category.

NIST finalist Signature selection:

• Rainbow

Only suitable for Signature

Isogeny-based Cryptography

Security problem relied on pseudo-random walks in supersingular isogeny graphs.

NIST finalist Signature selection:

• SIKE

It's only advantage is small public keysize.

Horribly slow.

Unacceptable speed in IoT device e.g: Cortex-M4

Hash-based Cryptography

Security problem relied on hash security.

NIST alternative Signature selection:

• SPHINCS+

It's only advantage is re-use native hash instruction set in modern CPU.

Horribly slow.

Vulnerable to side-channel attack, signature can be forge at very small computation cost

PQC standardization timeline

Real-world Cryptography

TLS Post-Quantum Crypto Performance

2020 Cloudflare experiments

Lattice size: 1138 bytes

Isogeny size: 676 bytes

Public key + Ciphertext size

2020 Cloudflare experiments

• Isogeny has smaller keysize, but in practice, latency is higher than lattice

• Lattice-based with 2 times bigger in keysize, the latency is somewhat  unnoticeable compare to current public cryptography

TLS Post-Quantum Crypto Experiment

• Big win to lattice
• Key size is a not a big deal
• Moore's Law is kinda stopped, we can't rely on hardware to do the hard work for us.

• The overall Internet speed is faster.

Keysize versus computing speed is similar to Internet speed vs Moore's Law

You know which one is growing faster... :)

IoT device Post-Quantum Crypto Performance

Challenges:

• Key size may not fit in RAM. <= Stack size

• Too slow due to complication algorithm. <= Speed

• Power consumption is a big concern. <= Energy

• Bandwidth is limited. <= Key size

Benchmarking Speed of PQC KEM on ARM Cortex-M4

Source

Benchmarking Speed of PQC KEM on ARM Cortex-M4

Source

Benchmarking Speed of PQC KEM on ARM Cortex-M4

Source

Benchmarking Speed of PQC Signature on ARM Cortex-M4

Source

Keysize of PQC Signature

Level 1

Level 3

Keysize of PQC KEM

Level 1

Level 3

Level 5

Predict Future IoT

KEM

• SABER, Kyber: Good overall
• NTRU: Keygen is expensive

Signature

• Falcon: Slow
• SIKE: Small keysize, even slower than Falcon
• Dilithium: Good overall

Post-Quantum Crypto in WireGuard VPN

WireGuard is simple and fastest VPN at the moment, simple design.

Post-Quantum Crypto in WireGuard VPN

Wanna see how Post-Quantum Cryptography can perform in the fastest VPN ?

The key to observe here:

• Is the speed become faster or slower?
• Is the latency, keysize make a huge difference ?

Post-Quantum Crypto in WireGuard VPN

Source

Post-Quantum Crypto in FPGA

Post-Quantum Crypto in FPGA

Performance in FPGA is important, simply because it answers these research questions

1. Given the freedom to implement an algorithm, how fast can it be?
2. Given reasonable number of LUT, DSP, FF, how fast can it still be?
3. Given a tight resource for IoT, how slow and energy-efficient can it be?

At some point in the near future, given crypto algorithm,

it will have Hardware Accelerator, or

Hardware Security Module, or

become a critical component for Crypto Networking Card, etc...

Post-Quantum Crypto ARM NEON vs. FPGA

Post-Quantum Crypto ARM NEON vs. FPGA

Post-Quantum Crypto ARM NEON vs. FPGA

The result shows that FPGA can outperform Cortex-A53 1200 Mhz. Although FPGA run at slower clock ratio 322 Mhz, but still, faster. 

• Hit the limit of NEON implementation.
• There are a lot of rooms for improvement in FPGA
• Again, definitely faster and smaller footprint than RSA, ECC.
• FPGA results shows that PQC is highly proficient in Crypto Networking Card, Hardware Security Module, Hardware Accelerator

Post-Quantum Crypto ARM NEON vs. FPGA

The result shows that FPGA can outperformCortex-A53 1200 Mhz. Although FPGA run at slower clock ratio 322 Mhz, but still, faster. 

• Hit the limit of NEON implementation.
• There are a lot of rooms for improvement in FPGA
• Again, definitely faster and smaller footprint than RSA, ECC.
• FPGA results shows that PQC is highly proficient in Crypto Networking Card, Hardware Security Module, Hardware Accelerator

Challenge In Implementation of FPGA, IoT, CPU

Challenge Implementating PQC on FPGA, IoT, CPU

It must be Side-channel resistance!

• FPGA is vulnerable to side-channel
• IoT device is vulnerable to power-analysis.
• CPU is vulnerable at its core, CPU architecture: Meltdown, Spectre, Spectre variants.

Still, open problems in research community

A look into the future

RSA and ECC security in Quantum Computing Era

RSA and ECC security in Quantum Computing Era

Keysize must be increased

RSA and ECC security in Quantum Computing Era

Computational time must be increased too

Public exponent e = 3

Are lattice-based Crypto Quantum Safe ?

Is lattice-based Crypto Quantum Safe ?

Classical aspects:

• Heuristic Sieve Algorithm is well-known lattice-based crypto attack
• No one can answer why the result of the heuristic search is improving every year.
• Can be run massively in parallel. GPU, FPGA, ASIC really good at parallel algorithms.

Is lattice-based Crypto Quantum Safe ?

• 2010 - Dimension n= 112 is broken. [Sieving]
• 2011 - Dimension n= 120 is broken. [Sieving]
• 2013 - Dimension n= 130 is broken. [Sieving]
• 2014 - Dimension n= 138 is broken. [Sieving]
• 2017 - Dimension n = 150 is broken. [Sieving]
• 2018 - Dimension 150 < n < 155 is broken. [Sieving]
• 2019 - Dimension n = 157 is broken. [Sieving]
• 2020 - Dimension n = 170 is broken. [Sieving]

SVP Challenge Hall Of Frame

Is lattice-based Crypto Quantum Safe ?

No.

Shor's algorithm doesn't apply here, but Grover's quantum search is too strong..

•  Sieving is improving each year....
• Remember, attacks always get better

Is Elliptic Curve Crypto Quantum Safe?

No.

• From 2017 to 2020, within 3 years, the resources of Quantum Circuit Depth is reduced from                     to                    , T-Gates reduce from                   to                     for 256-bit modulus.

• Still, far from practical deployment but the results are expected to be improved over years.