Post-Quantum Security of Hash Functions Explained
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. 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
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
