Post-Quantum Cryptography Security Proofs and Models Overview

 
(Post-quantum) cryptography
Security models, proofs and generic
transforms
 
Andreas Hülsing
Eindhoven University of Technology
 
Executive School on Post-Quantum Cryptography
July 2019, TU Eindhoven
Evaluation criteria for crypto
 
 
 
 
 
 
 
 
 
 
 
 
P
e
r
f
o
r
m
a
n
c
e
S
p
e
e
d
S
i
z
e
C
r
y
p
t
a
n
a
l
y
s
i
s
M
a
t
u
r
i
t
y
,
 
q
u
a
n
t
i
t
y
 
&
 
q
u
a
l
i
t
y
A
r
e
 
t
h
e
 
r
e
l
e
v
a
n
t
 
p
r
o
b
l
e
m
s
 
a
n
a
l
y
z
e
d
P
r
o
v
a
b
l
e
 
s
e
c
u
r
i
t
y
S
t
a
n
d
a
r
d
 
m
o
d
e
l
 
v
s
.
 
(
Q
)
R
O
M
T
i
g
h
t
 
v
s
 
n
o
n
-
t
i
g
h
t
 
r
e
d
u
c
t
i
o
n
I
m
p
l
e
m
e
n
t
a
t
i
o
n
 
s
e
c
u
r
i
t
y
P
o
s
s
i
b
i
l
i
t
y
 
/
 
a
v
a
i
l
a
b
i
l
i
t
y
 
o
f
 
p
r
o
t
e
c
t
e
d
 
i
m
p
l
e
m
e
n
t
a
t
i
o
n
s
01/07/2019
https://huelsing.net
2
Picture: By Rizkyharis - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=52757933
How to build PKC
(Computationally)
hard problem
RSA
DL
QR
DDH
PKC Scheme
 
RSA-
OAEP
 
ECDSA
 
DH-
KE
01/07/2019
https://huelsing.net
3
 
Security proofs
 
(for the example of digital signatures)
 
Source: http://hari-cio-8a.blog.ugm.ac.id/files/2013/03/DSA.jpg
 
Digital Signature
 
01/07/2019
 
https://huelsing.net
 
5
 
Security proofs
 
Four dimensions
What are we looking at?
Signature scheme? MAC? Key evolving signatures...
Determines functionality
What do we want to prove?
EU-CMA, SU-CMA, FS-EU-CMA, EU-RMA...
Determines security guarantee
In which model can we give the proof?
Standard model vs ROM vs QROM
Heuristic model or not
Can we get a tight proof?
Reduction loss
Does proof say something for concrete parameters
 
01/07/2019
 
https://huelsing.net
 
6
Existential unforgeability under
adaptive chosen message attacks
PK, 1
n
SIGN
SK
M
i
(
σ
i
, M
i
)
(
σ
*, M*)
01/07/2019
https://huelsing.net
7
PK, 1
n
M
i
(
σ
i
, M
i
)
(
σ
*, M*)
Problem
Solution
Implement
SIGN
SIGN
Transform Problem
Extract Solution
Reduction
01/07/2019
https://huelsing.net
8
Reduction: Implications
01/07/2019
https://huelsing.net
9
 
Standard model vs.
idealized model
 
Standard model:
Assume building block has property P (e.g., collision
resistance). Use property in reduction.
 
Idealized model:
Assume a building block behaves perfectly (e.g. hash
function behaves like truely random function).
Replace building block by an oracle in reduction.
 
01/07/2019
 
https://huelsing.net
 
10
 
Random Oracle Model (ROM)
 
Idealized Model
Perfectly Random Function
 
M
j
 
M
j
 
H(M
j
)
 
H(M
j
)
 
RO
 
01/07/2019
 
https://huelsing.net
 
11
 
How to implement RO?
(In theory)
 
RO
 
01/07/2019
 
https://huelsing.net
 
12
 
ROM security
 
Take scheme that uses cryptographic hash
For proof, replace hash by RO
Different flavors:
Random function vs. Programmable RO
 
 
01/07/2019
 
https://huelsing.net
 
13
PK, 1
n
M
i
(
σ
i
, M
i
)
(
σ
*, M*)
Problem
Solution
Implement
SIGN
SIGN
Transform Problem
Extract Solution
Programmable RO
01/07/2019
https://huelsing.net
14
RO
M
j
H(M
j
)
PK, 1
n
M
i
(
σ
i
, M
i
)
(
σ
*, M*)
Problem
Solution
Implement
SIGN
SIGN
Transform Problem
Extract Solution
Programmable RO
01/07/2019
https://huelsing.net
15
simulated
RO
M
j
H(M
j
)
 
ROM security
 
Take scheme that uses cryptographic hash
For proof, replace hash by RO
Different flavors:
Random function vs. Programmable RO
 
Heuristic security argument
Allows to verify construction
Worked for ”Natural schemes” so far
 
However: Artificial counter examples exist!
Random oracles do not exist!
 
01/07/2019
 
https://huelsing.net
 
16
 
Quantum security worlds
 
[
Gagliardoni’17]
 
QS0: Classical security
 
01/07/2019
 
https://huelsing.net
 
18
 
QS1: Post-quantum security
 
01/07/2019
 
https://huelsing.net
 
19
 
QS1: Post-quantum security
 
Adversary can run local quantum computations
Adversary cannot communicate with honest parties
using quantum states!
Local interfaces & oracles that do not contain secret
information:
Quantum access
Remote interfaces & secretly keyed oracles:
Classical access
 
01/07/2019
 
https://huelsing.net
 
20
 
QS2: Quantum security
 
01/07/2019
 
https://huelsing.net
 
21
 
QS2: Quantum security
 
Adversary can run local quantum computations
Adversary can communicate with honest parties
using quantum states!
Local interfaces & oracles that do not contain secret
information:
Quantum access
Remote interfaces & secretly keyed oracles:
Quantum access
This assumes a world where users have quantum
computers
 
01/07/2019
 
https://huelsing.net
 
22
 
We care about QS1 for
practical applications in
the foreseeable future!!!
 
 
01/07/2019
 
https://huelsing.net
 
23
QS1: Post-quantum security
 
Adversary can run local quantum computations
Adversary cannot communicate with honest parties
using quantum states!
Local interfaces & oracles that do not contain secret
information:
Quantum access
Remote interfaces & secretly keyed oracles:
Classical access
 
What happens in ROM?
01/07/2019
https://huelsing.net
24
PK, 1
n
M
i
(
σ
i
, M
i
)
(
σ
*, M*)
Problem
Solution
Implement
SIGN
SIGN
Transform Problem
Extract Solution
Quantum-accessible ROM (QROM)
01/07/2019
https://huelsing.net
25
QRO
 
The QROM
 
ROM „lives“ in QS0. Wrong model for post-
quantum security!
QROM: Adaption of ROM for QS1 – post-quantum
security.
Proofs in QROM more involved as „looking at
queries“ disturbes adversary -> complicates
adaptive behavior
Only weak separation known (using squareroot
speed-up of Grover)
 
01/07/2019
 
https://huelsing.net
 
26
 
Generic transforms
 
(for the example of KEM construction)
How to build PKC
(Computationally)
hard problem
RSA
DL
QR
DDH
PKC Scheme
RSA-
OAEP
ECDSA
DH-
KE
Simple
cryptographic
scheme
01/07/2019
https://huelsing.net
28
 
Public key encryption (PKE)
 
01/07/2019
 
https://huelsing.net
 
29
plaintext
 
Bob’s pk
 
Bob’s sk
PKE.Enc
SKE.Dec
 
Public key encryption (PKE)
 
01/07/2019
 
https://huelsing.net
 
30
 
Weak passiv security (OW-CPA)
 
01/07/2019
 
https://huelsing.net
 
31
 
Strong passiv security (IND-CPA)
 
01/07/2019
 
https://huelsing.net
 
32
 
Active security (IND-CCA)
 
IND-CPA + access to decryption oracle
Decryption query for challenge ciphertext
forbidden
 
Necessary if scheme gets used with non-ephemeral
keys!
In practice, binary response (valid / invalid
ciphertext) can be sufficient for attack.
 
01/07/2019
 
https://huelsing.net
 
33
 
Hybrid encryption
 
 
01/07/2019
 
https://huelsing.net
 
34
plaintext
SKE.Enc
SKE.Dec
PKE.Enc
PKE.Dec
 
Key encapsulation (KEM)
 
 
01/07/2019
 
https://huelsing.net
 
35
plaintext
SKE.Enc
SKE.Dec
KEM.Enc
KEM.Dec
 
Key encapsulation (KEM)
 
01/07/2019
 
https://huelsing.net
 
36
 
IND security models for KEM
 
01/07/2019
 
https://huelsing.net
 
37
IND-CPA PKE -> IND-CCA KEM
Generic transform essentially going back to
Fujisaki and Okamoto, CRYPTO‘99
01/07/2019
https://huelsing.net
38
IND-CPA PKE
OW-CPA dPKE
IND-CCA KEM
 
IND-CPA PKE -> OW-CPA dPKE
T-Transform [HHK17]
 
01/07/2019
 
https://huelsing.net
 
39
 
Randomness
01/07/2019
https://huelsing.net
40
 
Summary
 
01/07/2019
 
https://huelsing.net
 
41
 
Thank you!
Questions?
 
 
01/07/2019
 
https://huelsing.net
 
42
 
Security proofs
 
Four dimensions
What are we looking at?
Deterministic PKE? Probabilistic PKE? KEM? (A)KE?
Determines functionality
What do we want to prove?
OW-CPA, IND-CPA, IND-CCA,...
Determines security guarantee
In which model can we give the proof?
Standard model vs ROM vs QROM
Heuristic model or not
Can we get a tight proof?
Reduction loss
Does proof say something for concrete parameters
 
01/07/2019
 
https://huelsing.net
 
43
Public key encryption (PKE)
01/07/2019
https://huelsing.net
44
Gen
Enc
Dec
Slide Note
Embed
Share

Explore the various aspects of post-quantum cryptography security, including evaluation criteria, building public key cryptography (PKC) systems, security proofs, digital signatures, and reduction problems. Dive into topics such as performance, cryptanalysis, provable security, standard models, existential unforgeability, and reduction implications.

  • Cryptography
  • Security Proofs
  • Post-Quantum
  • PKC
  • Digital Signatures

Uploaded on Sep 06, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. (Post-quantum) cryptography Security models, proofs and generic transforms Andreas H lsing Eindhoven University of Technology Executive School on Post-Quantum Cryptography July 2019, TU Eindhoven

  2. Evaluation criteria for crypto Performance Speed Size Cryptanalysis Maturity, quantity & quality Are the relevant problems analyzed Provable security Standard model vs. (Q)ROM Tight vs non-tight reduction Implementation security Possibility / availability of protected implementations Picture: By Rizkyharis - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=52757933 01/07/2019 https://huelsing.net 2

  3. How to build PKC (Computationally) hard problem RSA QR Proof Problem hard Scheme secure DL DDH PKC Scheme RSA- OAEP ECDSA DH- KE 01/07/2019 https://huelsing.net 3

  4. Security proofs (for the example of digital signatures)

  5. Digital Signature Source: http://hari-cio-8a.blog.ugm.ac.id/files/2013/03/DSA.jpg 01/07/2019 https://huelsing.net 5

  6. Security proofs Four dimensions What are we looking at? Signature scheme? MAC? Key evolving signatures... Determines functionality What do we want to prove? EU-CMA, SU-CMA, FS-EU-CMA, EU-RMA... Determines security guarantee In which model can we give the proof? Standard model vs ROM vs QROM Heuristic model or not Can we get a tight proof? Reduction loss Does proof say something for concrete parameters 01/07/2019 https://huelsing.net 6

  7. Existential unforgeability under adaptive chosen message attacks SK PK, 1n ?? Mi SIGN ( i, Mi) ( *, M*) Success if M* Mi, i [0,q] and Verify(pk, *,M*) = Accept 01/07/2019 https://huelsing.net 7

  8. Reduction Problem PK, 1n Transform Problem ?? Mi Implement SIGN SIGN ( i, Mi) Solution ( *, M*) Extract Solution 01/07/2019 https://huelsing.net 8

  9. Reduction: Implications To prove: If ? can break [security] of [scheme] in time ? with probability ? then ?? can solve [problem] in time ?1(?) with probability ?2(?). Implications: 1. If ?1,?2 are polynomial functions (non-tight): If [problem] is hard, [scheme] is secure. 2. If ?1,?2 are close to identity (tight): The [scheme] is as hard to break as the problem. 01/07/2019 https://huelsing.net 9

  10. Standard model vs. idealized model Standard model: Assume building block has property P (e.g., collision resistance). Use property in reduction. Idealized model: Assume a building block behaves perfectly (e.g. hash function behaves like truely random function). Replace building block by an oracle in reduction. 01/07/2019 https://huelsing.net 10

  11. Random Oracle Model (ROM) Idealized Model Perfectly Random Function Mj H(Mj) Mj H(Mj) RO 01/07/2019 https://huelsing.net 11

  12. How to implement RO? (In theory) Lazy Sampling : 1. Keep list of (??,??) 2. Given ??, search for ??= ?? 3. If ??= ??exists, return ?? 4. Else sample new ? from Range, using uniform distribution 5. Add (??,?) to table 6. Return ? RO 01/07/2019 https://huelsing.net 12

  13. ROM security Take scheme that uses cryptographic hash For proof, replace hash by RO Different flavors: Random function vs. Programmable RO 01/07/2019 https://huelsing.net 13

  14. Programmable RO Problem PK, 1n Transform Problem ?? Mi Mj Implement SIGN SIGN ( i, Mi) H(Mj) RO Solution ( *, M*) Extract Solution 01/07/2019 https://huelsing.net 14

  15. Programmable RO Problem PK, 1n Transform Problem ?? Mi Mj Implement SIGN SIGN ( i, Mi) H(Mj) simulated RO Solution ( *, M*) Extract Solution 01/07/2019 https://huelsing.net 15

  16. ROM security Take scheme that uses cryptographic hash For proof, replace hash by RO Different flavors: Random function vs. Programmable RO Heuristic security argument Allows to verify construction Worked for Natural schemes so far However: Artificial counter examples exist! Random oracles do not exist! 01/07/2019 https://huelsing.net 16

  17. Quantum security worlds [Gagliardoni 17]

  18. QS0: Classical security 01010101110110 11010101 01110110 11010101 01110110 11000101 00010110 01/07/2019 https://huelsing.net 18

  19. QS1: Post-quantum security 01010101110110 11010101 01110110 11010101 01110110 0 1 0 1 0 1 0 0 1 1 1 1 1 0 01/07/2019 https://huelsing.net 19

  20. QS1: Post-quantum security Adversary can run local quantum computations Adversary cannot communicate with honest parties using quantum states! Local interfaces & oracles that do not contain secret information: Quantum access Remote interfaces & secretly keyed oracles: Classical access 01/07/2019 https://huelsing.net 20

  21. QS2: Quantum security 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 01/07/2019 https://huelsing.net 21

  22. QS2: Quantum security Adversary can run local quantum computations Adversary can communicate with honest parties using quantum states! Local interfaces & oracles that do not contain secret information: Quantum access Remote interfaces & secretly keyed oracles: Quantum access This assumes a world where users have quantum computers 01/07/2019 https://huelsing.net 22

  23. We care about QS1 for practical applications in the foreseeable future!!! 01/07/2019 https://huelsing.net 23

  24. QS1: Post-quantum security Adversary can run local quantum computations Adversary cannot communicate with honest parties using quantum states! Local interfaces & oracles that do not contain secret information: Quantum access Remote interfaces & secretly keyed oracles: Classical access What happens in ROM? 01/07/2019 https://huelsing.net 24

  25. Quantum-accessible ROM (QROM) Problem PK, 1n Transform Problem ?? Mi ?? Implement SIGN SIGN ( i, Mi) ?(??) QRO Solution ( *, M*) Extract Solution 01/07/2019 https://huelsing.net 25

  26. The QROM ROM lives in QS0. Wrong model for post- quantum security! QROM: Adaption of ROM for QS1 post-quantum security. Proofs in QROM more involved as looking at queries disturbes adversary -> complicates adaptive behavior Only weak separation known (using squareroot speed-up of Grover) 01/07/2019 https://huelsing.net 26

  27. Generic transforms (for the example of KEM construction)

  28. How to build PKC (Computationally) hard problem RSA QR Proof Problem hard Scheme secure DL DDH Simple cryptographic scheme PKC Scheme RSA- OAEP ECDSA DH- KE 01/07/2019 https://huelsing.net 28

  29. Public key encryption (PKE) plaintext plaintext SKE.Dec PKE.Enc Bob s pk Bob s sk 01/07/2019 https://huelsing.net 29

  30. Public key encryption (PKE) Gen 1?: is a probabilistic algorithm that outputs a key pair ??,?? . Enc(??,?): is a possibly probabilistic algorithm that on input of a public key and a message outputs a ciphertext ? = Enc??(?). Dec(??,?): is a deterministic algorithm that on input of a secret key and a ciphertext outputs a plaintext ? = Dec??(?). Correctness: ? ?, ??,?? ??? 1? Dec??(Enc??(?)) = ? : 01/07/2019 https://huelsing.net 30

  31. Weak passiv security (OW-CPA) 01/07/2019 https://huelsing.net 31

  32. Strong passiv security (IND-CPA) 01/07/2019 https://huelsing.net 32

  33. Active security (IND-CCA) IND-CPA + access to decryption oracle Decryption query for challenge ciphertext forbidden Necessary if scheme gets used with non-ephemeral keys! In practice, binary response (valid / invalid ciphertext) can be sufficient for attack. 01/07/2019 https://huelsing.net 33

  34. Hybrid encryption symmetric session key plaintext plaintext SKE.Dec SKE.Enc PKE.Enc PKE.Dec Bob s pk Bob s sk 01/07/2019 https://huelsing.net 34

  35. Key encapsulation (KEM) symmetric session key plaintext plaintext SKE.Dec SKE.Enc KEM.Enc KEM.Dec Bob s pk Bob s sk 01/07/2019 https://huelsing.net 35

  36. Key encapsulation (KEM) Gen 1?: is a probabilistic algorithm that outputs a key pair ??,?? . Enc(??,?): is a possibly probabilistic algorithm that on input of a public key outputs a session key ? and an encapsulation (?,?) = Enc??(). Dec(??,?): is a deterministic algorithm that on input of a secret key and an encapsulation outputs a session key ? = Dec??(?). Correctness: ??,?? ??? 1? ?,? = Enc?? : ? = Dec??(?) 01/07/2019 https://huelsing.net 36

  37. IND security models for KEM IND: Given a pair (c, k) decide if c is encapsulation of k or random CPA: Adversary gets pk and can hence generat encapsulations CCA: Adversary gets access to decapsulation oracle (which returns for challenge encapsulation) 01/07/2019 https://huelsing.net 37

  38. IND-CPA PKE -> IND-CCA KEM Generic transform essentially going back to Fujisaki and Okamoto, CRYPTO 99 IND-CPA PKE OW-CPA dPKE IND-CCA KEM 01/07/2019 https://huelsing.net 38

  39. IND-CPA PKE -> OW-CPA dPKE T-Transform [HHK17] Start from IND-CPA secure PKE = (Gen, Enc, Dec) with probabilistic Enc and a hash function H. Build OW-CPA secure PKE = (Gen, Enc , Dec) = T(PKE, H) with deterministic Enc : Enc ??(m) = Enc??(?;H ? ) Randomness Tight security reduction in ROM Non-tight security reduction in QROM 01/07/2019 https://huelsing.net 39

  40. OW-CPA dPKE -> IND-CCA KEM ? -Transform [HHK17] Start from OW-CPA secure dPKE P = (Gen, Enc, Dec), PRF F, and hash function H. Build IND-CCA secure KEM ? P,F,H : 01/07/2019 https://huelsing.net 40

  41. Summary Security proof security proof Only tight proofs say something about the security of parameters Only standard model & QROM proofs say something about post-quantum security Generic transforms can save you a lot of work Sufficient to construct OW-CPA dPKE for IND-CCA KEM with tight QROM proof Sufficient to construct IND-CPA PKE for IND-CCA KEM with QROM proof 01/07/2019 https://huelsing.net 41

  42. Thank you! Questions? 01/07/2019 https://huelsing.net 42

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#