Impact of Quantum Technologies to Cryptography
Tutorial – Part I
Ludovic Perret (ludovic.perret@lip6.fr)
Sorbonne University/CNRS
Co-founder of CryptoNext Security

Computability in Europe 2023, 24th-28th July 2023, Batumi, Georgia

1 / 34

Introduction & Organization of the Tutorial
Post-Quantum Cryptography
Cryptosystems secure both against classical and quantum adversaries
Start-up
Large-scale deployment

Standardization
Basic researchInnovation

2 / 34

Introduction & Organization of the Tutorial
Post-Quantum Cryptography
Cryptosystems secure both against classical and quantum adversaries
Start-up
Large-scale deploymentStandardization
Basic researchInnovation

Part I. Cryptography in the era to quantum technologies

2 / 34

Introduction & Organization of the Tutorial
Post-Quantum Cryptography
Cryptosystems secure both against classical and quantum adversaries
Start-up
Large-scale deployment

Standardization
Basic researchInnovation

Part I. Cryptography in the era to quantum technologies
Part II. On the use of quantum algorithms in cryptanalysis
Part III. A zoom on the design of post-quantum signature schemes
2 / 34

Outline

1

Cryptography Warm-Up

2

Quantum Impact

3

Transition toward quantum-resistant infrastructure

3 / 34

Outline1Cryptography Warm-Up

2

Quantum Impact

3

Transition toward quantum-resistant infrastructure

4 / 34

The basic goal of cryptography
Secure communicationinternet, phone line, . . .

eavesdrops
AliceBobEve
5 / 34

Information security objectives

confidentiality

keeping information secret from all but those
who are authorized to see it

integrity

ensuring information has not been alteredby unauthorized or unknown means

authentication

corroborating the source of information

anonymity

concealing the identity of an entity involved
in some process

non-repudiation

preventing the denial of previous
commitments or actionsetc...

6 / 34

Cryptography in the old time
mskGenskEnccDec

AlicemBob

Adversary

Figure: Enigma machine

Figure: Enigma principle

7 / 34

Cryptography in the old time

Figure: Enigma machine

Figure: Enigma principle

Reputed unbreakable

7 / 34

The rise of computers

Figure: Alan Turing
Figure: Turing’s computer

Full cryptanalysis of Enigma (and similar mechanical machines)☛ Technology took cryptography down
8 / 34

How to formalize security ?

Intuition. Attacker should not be able
to compute any information about mDefinition
An encryption scheme is perfectly
secret (or Information TheoreticallySecure, ITS) if for every randomvariable M, every message m ∈ Mand every ciphertext c ∈ C withPr(C = c ) > 0:
Figure: Claude Shannon

Pr(M = m) = Pr(M = m|C = c )9 / 34

A perfectly secure scheme: one-time padDescription❏ Let ℓ ∈ N be a parameter and ⊕ denotes component-wise XOR
Message space M = {0, 1}ℓ
Key space K = {0, 1}ℓ❏ Vernam’s cipher: Enc(K , m) = m ⊕ K and Dec(K , c ) = c ⊕ K☛ One-time pad is perfectly secret!
☛ Each key cannot be used morethan once!

☛ Key is as long as the message☛ One time-pad is optimal in theclass of perfectly secret schemes
Figure: Red phone
10 / 34

Block-ciphers

Problems❏ the plaintexts and keys may be extremely long

11 / 34

Block-ciphers

Problems❏ the plaintexts and keys may be extremely long
Idea

☛ Design ciphers that work on small blocks☛ Expand the encryption key from a fixed-size secret-key

11 / 34

Block-ciphers

Idea☛ Design ciphers that work on small blocks☛ Expand the encryption key from a fixed-size secret-key
Description
EncK (m) := Enc(K , m) : {0, 1}λ × {0, 1}n → {0, 1}n1
λnnEnc−
K (c ) := DecK (c ) = Dec(K , c ) : {0, 1} × {0, 1} → {0, 1}∀K , ∀m : DecK (EncK (m)) = m

11 / 34

Block-ciphers
Description
EncK (m) := Enc(K , m) : {0, 1}λ × {0, 1}n → {0, 1}n1
λnnEnc−
K (c ) := DecK (c ) = Dec(K , c ) : {0, 1} × {0, 1} → {0, 1}∀K , ∀m : DecK (EncK (m)) = m
Data Encryption Standard (DES)❏ Defined by US National
Bureau of Standards, 1976

Advanced Encryption Standard(AES)❏ Defined by NIST, 2001

❏ Key length : 56 bits

❏ open call for proposals,❏ Block-size : 64 bits

competitive process❏ Complete deprecation,
National Institute ofStandards (NIST), 2017

❏ Key length : 128/192/256 bits
❏ block-size : 128 bits
❏ Widely deployed
11 / 34

Hash functions

Hash functions compute fingerints
Various uses

H12 / 34

Hash functions

Hash functions compute fingerints
Various uses

H0x1d66ca77ab361c6f

12 / 34

Hash functions

Hash functions compute fingerints
Various uses

No Keys !
H0x1d66ca77ab361c6f

12 / 34

Public-key cryptography

Limitations of symmetric cryptography☛ Key-distribution needs physical meeting☛ The number of keys for k users is Θ(k 2 )13 / 34

Public-key cryptography

anyone can lock it
the key is needed to unlock

Diffie and Hellman, 1976

☛ The concept, no implementation☛ A protocol for key-exchange

13 / 34

Diffie–Hellman (DH) key-exchange(G, ·) a finite cyclic group; ⟨g ⟩ = G

ya = g ayb = g b
AliceBob

Ka = yb a

Kb = ya b

EveKa = yb a = (g b )a = g ab = (g a )b = ya b = Kb
14 / 34

Computational securityDiscrete Logarithm problem❏ Given a cyclic group (G, g ) and y ∈ G❏ Find integer s such that y = g s☛ Assumption. It should be computationally difficult to find s from y☛ How to choose G : G = (Z/nZ× , ·) for some integer p or elliptic curves☛ Security level. Base-2 logarithm of the complexity of the best algorithm☛ Symmetric cryptography : security level given by the bit-size of thesecret-key, typically 128/192/256☛ Public-key cryptography : same, more tricky analysis

15 / 34

Beyond DH key-exchange

Trapdoor function: is easy to compute, difficult to inverse without special
information, the “trapdoor”.
easy
easy
x

trapdF (x )hard

16 / 34

Beyond DH key-exchange
Trapdoor function: is easy to compute, difficult to inverse without special
information, the “trapdoor”.

☛ A Public-Key Encryption (PKE) scheme can be constructed from any
trapdoor permutation☛ Key-Encapsulation Mechanism (KEM) : key-exchange using a PKEmpk

Gen

sk

Enc

c

Dec

AlicemBob

Adversary

16 / 34

Beyond DH key-exchange
Trapdoor function: is easy to compute, difficult to inverse without special
information, the “trapdoor”.

☛ A Digital Signature Scheme (DSS) can be constructed from any
trapdoor permutation.

mAlicesk

Gen

pk

Enc

c

Dec
mm
Signσmb

Bob

Verify16 / 34

Beyond DH key-exchange

Trapdoor function: is easy to compute, difficult to inverse without special
information, the “trapdoor”.

Factorization
Given two primes p and q.
easy to compute N = p × q
hard to get p and q from N(factorization)

16 / 34

Key Size (Bits) Comparison

AES

RSA (N)/DH(p)ECC (order q)

56

512

112

80

1024

160

112

2048

224

128

3072

256

192

7680

384

256

15360

512

❏ Factorization Record, RSA829 [Boudot, Thomé, Gaudry, Heniniger,Zimmermann, 2020].

17 / 34

Cryptography in practice

Limitation of public-key cryptography❏ It is order of magnitude slower than secret-key cryptography

18 / 34

Cryptography in practice

Limitation of public-key cryptography❏ It is order of magnitude slower than secret-key cryptography
Hybrid encryption (KEM/DEM paradigm)❏ Use public-key cryptography to exchange keys
❏ then secret-key cryptography for protecting large traffic

18 / 34

Cryptography in practiceHybrid encryption (KEM/DEM paradigm)❏ Use public-key cryptography to exchange keys
❏ then secret-key cryptography for protecting large traffic
confidentiality

block cipher (AES128)

integrity

Hash functions (SHA2/SHA3)

authentication

Message Authentication Code (MAC)
symmetric-key primitive
can be constructed from a hash function

authentication

Certificate
public-key primitive
roughly public-key +signature by a TTP

18 / 34

Cryptography in practice

18 / 34

Cryptography is a commodity€150bn in 2023
Cybersecurity market

19 / 34

Outline

1

Cryptography Warm-Up

2

Quantum Impact

3

Transition toward quantum-resistant infrastructure

20 / 34

Quantum threat to secret-key cryptography (1/2)

Grover’s algorithm❏ F : {0, 1}n → {0, 1}❏ Find x∗ ∈ {0, 1}n such that F (x∗ ) = 1l qmn❏ π4 |F −21 (1)| evaluations of F as a quantum circuit

21 / 34

Quantum threat to secret-key cryptography (1/2)

Grover’s algorithm❏ F : {0, 1}n → {0, 1}❏ Find x∗ ∈ {0, 1}n such that F (x∗ ) = 1l qmn❏ π4 |F −21 (1)| evaluations of F as a quantum circuit❏ Given m, c = Enc(K , m) ∈ {0, 1}n × {0, 1}n❏ F : {0, 1}λ → {0, 1} is the function that returns 1 if c = Enc(K ∗ , m).
21 / 34

Quantum threat to secret-key cryptography (1/2)
❏ Given m, c = Enc(K , m) ∈ {0, 1}n × {0, 1}n❏ F : {0, 1}λ → {0, 1} is the function that returns 1 if c = Enc(K ∗ , m).
Impact√Quantum exhaustive search in O ( 2λ ) calls to F

☛ Exponential speedup toward classical approaches☛ ≈ double the key-length
Resource estimates
V. Gheorghiu, M. Mosca.
“Benchmarking the Quantum Cryptanalysis of Symmetric, Public-Keyand Hash-Based Cryptographic Schemes.”
arXiv.org 2019.
21 / 34

Quantum threat to secret-key cryptography (1/2)
❏ Given m, c = Enc(K , m) ∈ {0, 1}n × {0, 1}n❏ F : {0, 1}λ → {0, 1} is the function that returns 1 if c = Enc(K ∗ , m).
Impact√Quantum exhaustive search in O ( 2λ ) calls to F

☛ Exponential speedup toward classical approaches☛ ≈ double the key-length
Resource estimates
V. Gheorghiu, M. Mosca.
“Benchmarking the Quantum Cryptanalysis of Symmetric, Public-Key
and Hash-Based Cryptographic Schemes.”
arXiv.org 2019.
21 / 34

Quantum threat to secret-key cryptography (2/2)

Beyond Grover
M. Kaplan, G. Leurent, A. Leverrier, M. Naya-Plasencia.
“Breaking Symmetric Cryptosystems Using Quantum Period Finding.”
CRYPTO 2016.
Simon’s problem❏ F : {0, 1}n → {0, 1}❏ Find s ∈ {0, 1}n such that F (x ⊕ s) = F (x)❏ quantum polynomial-time

22 / 34

Quantum threat to public-key cryptography(Large) Quantum computers will be able break current public-key
cryptography
Shor’s algorithm
Polynomial-time quantum algorithms for
RSA/Diffie-Hellman

RSA1024 – classic ≈ 400 years
RSA1024 – quantum ≈ hours

23 / 34

Quantum computing limits2019 : “Quantum supremacy” by Google 2022 :⩾ 100 qubits by Pasqal 
Sycamore : 53/70 qubits

24 / 34

Quantum computing limits

24 / 34

Quantum computing limits
C. Gidney, M. Ekera.
“How to factor 2048 bit RSA integers in 8 hours using 20 million noisyqubits.”
Quantum, 2021.

Extrapolating (paranoid)☛ 9 years for RSA2048☛ 8 years for RSA1024☛ Time for a cryptographic transition 5/10 years
24 / 34

Quantum computing limits
E. Gouzien, N. Sangouard“Factoring 2048-bit RSA integers in 177 days with 13436 qubits and amultimode memory.”
Physical Review Letters, 2021.

24 / 34

Quantum computing limits

Bao Yan et al.
“Factoring integers with sublinear resources on a superconducting
quantum processor.”
ArXiv 2022.

24 / 34

Quantum computing limits

Adi Shamir predictions – 2016
“There will be no full size quantum computerscapable of factoring RSA keys”.

24 / 34

Time bomb effect
Harvest now, decrypt later

25 / 34

Time bomb effectConnected objects with long life cycle

26 / 34

Outline

1

Cryptography Warm-Up

2

Quantum Impact

3

Transition toward quantum-resistant infrastructure

27 / 34

A risk perceived as major

28 / 34Solutions
Quantum-Key Distribution (QKD)❏ two channels : authenticated classical and quantum❏ Unconditional security based on quantum physics❏ Practical limitations : distance, cost, . . .

29 / 34

Solutions

National Security Agencies (French ANSSI, UK GCHQ, US NSA,. . . ) usually
argue against current deployment of QKD

29 / 34

Solutions

National Security Agencies (French ANSSI, UK GCHQ, US NSA,. . . ) usually
argue against current deployment of QKD❏ Out-of-band distribution of a pre-shared key for ITS MAC authentication❏ Key expansion with QKD❏ Encryption of traffic with a block-cipher (computational assumption)

29 / 34

Solutions
Post-Quantum Cryptography (PQC)❏ Computational security based on new hard algorithmic problems❏ Natural integration into security protocols
Multivariatebased

New hard problems

Lattice-based

Isogenybased

Hash-based

Code-based

30 / 34

Polynomial System Solving over Finite Fields (PoSSoq )q, size of fieldn, nb. of variablesm, nb. of equations

PoSSoq
Input. non-linear polynomials p1 , . . . , pm ∈ Fq [x1 , . . . , xn ]Question. Find – if any – (z1 , . . . , zn ) ∈ Fnq such that: p1 (z1 , . . . , zn ) = 0

..
.





pm (z1 , . . . , zn ) = 0

PoSSoq is NP-hard [Garey-Johnson, 1979]

31 / 34

Polynomial System Solving over Finite Fields (PoSSoq )q, size of fieldn, nb. of variablesm, nb. of equations

PoSSoq
Input. non-linear polynomials p1 , . . . , pm ∈ Fq [x1 , . . . , xn ]Question. Find – if any – (z1 , . . . , zn ) ∈ Fnq such that: p1 (z1 , . . . , zn ) = 0

..
.




pm (z1 , . . . , zn ) = 0

PoSSoq is NP-hard [Garey-Johnson, 1979]
FoundationNP problem cannot be solved in poly-time by a quantum Turing machine.
C. H. Bennett, E. Bernstein, G. Brassard and U. V. Vazirani.
“Strengths and Weaknesses of Quantum Computing”.
SIAM J. Comput., 1997.
31 / 34NIST post-quantum standardization process

Round 12016 – 2018 : 82 submissions→ 69 round-1 candidates

Round 22019 – 2020 → 26 algorithms

Round 32020 – 2022 → 7 finalists and 8 alternates

Selection

2022 : first set of algorithms
selected (1 KEM and 2 DSS)

32 / 34NIST post-quantum standardization process
Round 12016 – 2018 : 82 submissions→ 69 round-1 candidates

Round 22019 – 2020 → 26 algorithms

Round 32020 – 2022 → 7 finalists and 8 alternates

Selection

2022 first set of algorithms
selected (1 KEM and 2 DSS)

Round 42023 : selected round-3 andnew signature algorithms
32 / 34

Post-Quantum Cryptography (PQC) standardization
process

First PQC standards
2017 : NIST started a standardization process for PQC
2022 : first set of post-quantum standards
1 lattice-based KEM (Kyber)
3 signature schemes : 2 lattice-based(Dilithium/Falcon) and 1 hash-based (Sphincs+)
2023/2024 : Official standards

33 / 34

Performances
AES

RSA (N)/DH(p)ECC (order q)

80

1024

160

112

2048

224

128

3072

256

Figure: Key-sizes (bits)

Name

Kyber512

Size (bytes)

Performance (cycles)

#pk

#ct

KEYGENE NCAPSULATED ECAPSULATE

800

768

33 85645 20034 57234 / 34

Performances
AES

RSA (N)/DH(p)ECC (order q)

80

1024

160

112

2048

2241283072

256

Figure: Key-sizes (bits)

Name

Kyber512

Name

Dilithium2
Falcon512
SPHINCS+s

Size (bytes)

Performance (cycles)

#pk

#ct

KEYGENE NCAPSULATED ECAPSULATE

800

768

33 85645 20034 572Size (bytes)

Performance (cycles)

#pk

#sig

KEYGENS IGN

V ERIFY

1 312

2 430

124 031333 013

118 41289766618 722 000

386 678

82 340327 856

144 000 000

1 100 000 000

1 190 000
34 / 34

A boom in PQC standardization – cryptographyStandardization for basic PQC
primitives❏ NIST Round-4 for additional
KEM (since 2022)❏ NIST call for additionalsignature schemes (since 2023)❏ ISO JTC 1/SC 27/WG 2
Larger portfolio of PQC
algorithms than NIST
standards

New NIST call for digital signatureschemesNIST.
“Call for Additional Digital Signature
Schemes for the Post-Quantum
Cryptography Standardization Process.”
October 2022.

More diversities in thecomputational assumptions
Short signature sizes
Deadline, June 1st, 2023
50 submissions (23submissions for round-1)

35 / 34

A boom in PQC standardization – cryptographyStandardization for basic PQC
primitives❏ NIST Round-4 for additional
KEM (since 2022)❏ NIST call for additionalsignature schemes (since 2023)❏ ISO JTC 1/SC 27/WG 2❏ Larger portfolio of PQC
algorithms than NIST
standards

Standardization of advanced PQC
Upcoming NIST call for Multi-Party
Threshold Schemes☛ Building blocks forPrivacy-Enhancing
Technologies☛ Homomorphic encryp.,
threshold signature schemes,...

36 / 34