Post-Quantum Security of Hash Functions Explained
Post-quantum security
of hash functions
Dominique Unruh
University of Tartu
Hash functions
•
Integrity of data
•
Identification of files
•
Efficient signatures
•
Commitment schemes
•
etc.
Post-quantum secure hashes
2
H
long input
short output
A
r
e
c
o
m
m
o
n
h
a
s
h
f
u
n
c
t
i
o
n
s
p
o
s
t
-
q
u
a
n
t
u
m
s
e
c
u
r
e
?
Properties of hash functions
•
Collision resistance
•
Pseudo random
generators/functions
•
“Random-oracle like”
Post-quantum secure hashes
3
A
n
d
m
o
r
e
Surprises with hash functions
•
Consider a hash function and a horse race
•
“Spicy Spirit” wins…
Post-quantum secure hashes
4
Surprises with hash functions (II)
•
Consider a cheating player
•
“Wallopping Waldo” wins…
Post-quantum secure hashes
5
Surprises with hash functions (III)
Post-quantum secure hashes
P
l
a
y
e
r
B
o
o
k
i
e
6
Surprises with hash functions (IV)
Post-quantum secure hashes
7
Collapsing hash functions
Post-quantum secure hashes
8
Post-quantum hashes?
Question:
Are existing hashes post-quantum secure?
(E.g., SHA2, SHA3, etc.)
•
Collision-resistance?
•
Collapsing?
•
PRG/PRF?
•
…
Post-quantum secure hashes
9
How are hashes constructed?
A small building block:
•
Checked by cryptanalysis
•
Assumed ideal (e.g., random oracle)
An iterative construction:
•
With security proof
Post-quantum secure hashes
10
•
Compression function
•
Block function
•
Merkle-Damgård (e.g., SHA2)
•
Sponge (e.g., SHA3)
Security of
Merkle-Damgård
Building block:
Compression function
•
Idealized: random function
•
Random functions are
collision-resistant / collapsing
We can assume
f
to be collapsing
Post-quantum secure hashes
11
Security of
Merkle-Damgård (II)
Post-quantum secure hashes
12
✓
Security of
Merkle-Damgård (III)
Post-quantum secure hashes
13
One subtlety:
Superpositions of messages of different lengths
•
We assumed known length
•
Measuring length
disturbs state?
•
Fortunately: padding has length in last block
Security of
sponges
Building block:
Block function (or permutation)
•
Idealized: random function / permutation
•
Collision-resistant / collapsing
when restricted to left/right half of output
•
Not true for invertible permutation!!!
Post-quantum secure hashes
14
SHA3
Security of sponges (II)
Post-quantum secure hashes
15
✓
Security of sponges (III)
Same subtlety:
Superposition of different lengths
more tricky, but solvable
Conclusion:
Sponge hashes are collapsing/collision-resistant
But only if
f
not invertible!
Post-quantum secure hashes
16
Which sponges are post-quantum?
•
With non-invertible block function:
✓
–
E.g., Gluon hash function
•
With invertible block function:
unknown
–
E.g., SHA3
–
Preferred by classical community
(better parameters)?
What shall we prefer in post-quantum case???
Post-quantum secure hashes
17
Indifferentiability of sponges
Classically,
sponges are indifferentiable
•
I.e., they have “the same properties” as
random oracles
•
Collision-resistance and much more:
trivial consequence
Time-saver approach: one proof for all
Post-quantum secure hashes
18
Indifferentiability: “Definition”
•
Simulator must find
f
that “explains” the
random oracle as a sponge.
Post-quantum secure hashes
19
Real model
f
S
p
o
n
g
e
Ideal model
R
a
n
d
o
m
o
r
a
c
l
e
f
fake
indistinguishable
Quantum indifferentiability of sponge
Post-quantum secure hashes
20
Real model
f
S
p
o
n
g
e
Ideal model
R
a
n
d
o
m
o
r
a
c
l
e
f
fake
Half-proven
conjecture
Main open problem
Understand sponges
with invertible block function
Otherwise, no clue if SHA-3 post-quantum secure
Post-quantum secure hashes
21
I thank for your
attention
This research was supported
by European Social Fund’s
Doctoral Studies and
Internationalisation
Programme DoRa
22
23
Postdoc Positions
(also phd)
Verification of
Quantum Crypto
Formal verification of quantum crypto protocols
(“QuEasyCrypt” tool)
http://tinyurl.com/postdoc-vqc
Abstract: In classical cryptography, one of the most important properties of hash functions is collision-resistance. We explain why collision-resistance is (often) not a sufficient requirement in the post-quantum setting, and present an alternative, the collapsing-property. We discuss the security of Merkle-Damgård-hashes (e.g., SHA2) and sponge-based hashes (e.g., SHA3): under which conditions are they collapsing? Finally, we study the "indifferentiability" of the sponge-construction (on which classical proofs are based), and present ongoing work for showing that the sponge-construction is not indifferentiable.
Explore the intricacies of post-quantum secure hash functions, their properties, surprises, and implications in quantum settings. Delve into collision resistance, pseudo-random generators, efficient signatures, and more, presented by Dominique Unruh from the University of Tartu.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Post-quantum security of hash functions Dominique Unruh University of Tartu Dominique Unruh
Hash functions H H long input short output Integrity of data Identification of files Efficient signatures Commitment schemes etc. Are common hash Are common hash functions functions post post- -quantum quantum secure? secure? Post-quantum secure hashes 2 Dominique Unruh
Properties of hash functions H H H H ?1 Collision resistance ? ?2 Pseudo random generators/functions H H more random random H H Random-oracle like ??? ??? Post-quantum secure hashes 3 Dominique Unruh
Surprises with hash functions Consider a hash function and a horse race ?("????? ??????",231632) Player Player Bookie Bookie Spicy Spirit wins 231632 Player Player Bookie Bookie $$$ Post-quantum secure hashes 4 Dominique Unruh
Surprises with hash functions (II) Consider a cheating player ?("????? ??????",231632) Player Player Bookie Bookie Some fake Wallopping Waldo wins ? with ? ??????,? = Player Player Bookie Bookie $$$ Post-quantum secure hashes 5 Dominique Unruh
Surprises with hash functions (III) ? with ? ??????,? = Player Player Bookie Bookie Classical crypto: ? is collision-resistant (infeasible to find ?,? with ? ? = ?(? )) Consequence: Can open to one horse only. Surprise: Does not hold for quantum adv (? might be coll.-res., and attack still works) Post-quantum secure hashes 6 Dominique Unruh
Surprises with hash functions (IV) Some fake Player Player Bookie Bookie | ? with ? ??????,? = Player Player Bookie Bookie | used up! Post-quantum secure hashes 7 Dominique Unruh
Collapsing hash functions Strengthening of collision-resistance for quantum setting Adv. A outputs messages ? (in superposition) |? |? A A A A A A A A or Def: Collapsing = A cannot distinguish Post-quantum secure hashes 8 Dominique Unruh
Post-quantum hashes? Question: Are existing hashes post-quantum secure? (E.g., SHA2, SHA3, etc.) Collision-resistance? Collapsing? PRG/PRF? This talk Post-quantum secure hashes 9 Dominique Unruh
How are hashes constructed? A small building block: Compression function Block function f f fixed len fixed len Checked by cryptanalysis Assumed ideal (e.g., random oracle) An iterative construction: Merkle-Damg rd (e.g., SHA2) Sponge (e.g., SHA3) With security proof Post-quantum secure hashes 10 Dominique Unruh
Security of Merkle-Damgrd Building block: Compression function f f 2? bits ? bits Idealized: random function Random functions are collision-resistant / collapsing We can assume f to be collapsing Post-quantum secure hashes 11 Dominique Unruh
Security of Merkle-Damgrd (II) MD-construction: f f f f f f f f f f ?? ?? ?1 ?2 ?3 ?4 ?5 = measure To show: Measuring: ?? is indistinguishable from measuring: ?1,?2,?3,?4,?5. Post-quantum secure hashes 12 Dominique Unruh
Security of Merkle-Damgrd (III) One subtlety: Superpositions of messages of different lengths f f f f f f f f f f ?? ?? ?1 ?2 ?3 ?4 ?5 We assumed known length Measuring length disturbs state? Fortunately: padding has length in last block SHA2 SHA2 post secure ( secure (coll post- -quantum quantum coll- -res., collapsing) res., collapsing) Post-quantum secure hashes 13 Dominique Unruh
Security of sponges Building block: Block function (or permutation) f f ? bits ? bits SHA3 Idealized: random function / permutation Collision-resistant / collapsing when restricted to left/right half of output Not true for invertible permutation!!! Post-quantum secure hashes 14 Dominique Unruh
Security of sponges (II) Sponge-construction: ?3 1 2 ?1 ?2 f f f f f f f f 0 0 = measure To show: Measuring: 1, 2 is indistinguishable from measuring: ?1,?2,?3. Post-quantum secure hashes 15 Dominique Unruh
Security of sponges (III) Same subtlety: Superposition of different lengths more tricky, but solvable Conclusion: Sponge hashes are collapsing/collision-resistant But only if f not invertible! Post-quantum secure hashes 16 Dominique Unruh
Which sponges are post-quantum? With non-invertible block function: E.g., Gluon hash function With invertible block function: unknown E.g., SHA3 Preferred by classical community (better parameters)? What shall we prefer in post-quantum case??? Post-quantum secure hashes 17 Dominique Unruh
Indifferentiability of sponges Classically, sponges are indifferentiable I.e., they have the same properties as random oracles Collision-resistance and much more: trivial consequence Time-saver approach: one proof for all Post-quantum secure hashes 18 Dominique Unruh
Indifferentiability: Definition Real model Ideal model Random Random oracle oracle f f f f Sponge Sponge fake indistinguishable Simulator must find fthat explains the random oracle as a sponge. Post-quantum secure hashes 19 Dominique Unruh
Quantum indifferentiability of sponge Real model Ideal model Random Random oracle oracle f f f f Sponge Sponge fake Queries to f in superposition simulator cannot adaptively fix f needs to fix all of f in a go Counting argument: not enough different f s Half-proven conjecture Post-quantum secure hashes 20 Dominique Unruh
Main open problem Understand sponges with invertible block function Otherwise, no clue if SHA-3 post-quantum secure Post-quantum secure hashes 21 Dominique Unruh
I thank for your attention This research was supported by European Social Fund s Doctoral Studies and Internationalisation Programme DoRa 22 Dominique Unruh
Postdoc Positions (also phd) Verification of Quantum Crypto Formal verification of quantum crypto protocols ( QuEasyCrypt tool) http://tinyurl.com/postdoc-vqc 23 Dominique Unruh
