Quantum Security of Commitment Schemes and Hash Functions
"Explore the quantum security implications of commitment schemes and hash functions through surprising scenarios. Delve into classical definitions and the need for new definitions in this thought-provoking discussion by Dominique Unruh at 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
Quantum-security of commitment schemes and hash functions Dominique Unruh University of Tartu 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 $$$ Commitments and hashes 2 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 $$$ Commitments and hashes 3 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) Commitments and hashes 4 Dominique Unruh
Surprises with hash functions (IV) Some fake Player Player Bookie Bookie | ? with ? ??????,? = Player Player Bookie Bookie | used up! Commitment : A protocol that does not allow the player to change their mind. This talk. Commitments and hashes 5 Dominique Unruh
Commitments: scope of this talk Hiding and binding Hiding seems well understood Statistically vs. computationally binding Weaker assms, everlasting security Interactive vs. non-interactive For simplicity Secure against quantum attacks Classical protocols Commitments and hashes 6 Dominique Unruh
Classical definitions ? Commit: S S R R ?,? Open: Computationally binding (classical-style): Hard to find: ? and ? ? and ?,? s.t.: ? opens ? as ? ? opens ? as ? Adv. cannot change his mind Commitments and hashes 7 Dominique Unruh
New definitions needed Classical def of computationally binding: Walloping Waldo attack still possible! Our proposal: Our proposal: Collapse Collapse- -binding commitments binding commitments Collision-resistance Weaker than expected Stronger def? (NIST post-quantum competition?) Our proposal: Our proposal: Collapsing hash functions Collapsing hash functions Commitments and hashes 8 Dominique Unruh
Existing defs (binding) Various prior def s Brassard, Cr peau, Damg rd, Dumais, Fehr, Jozsa, Langlois, Lunemann, Mayers, Salvail, Schaffner Various problems: Need trapdoors (or even UC) Rewinding proofs difficult No parallel composition Do not imply knowledge of message Commitments and hashes 9 Dominique Unruh
Collapse-binding commitments Adv. A outputs commitment ? (classically), and valid openings ?,? (in superposition) |? |? A A A A A A A A or |? |? ? ? Def: Collapse-binding = A cannot distinguish Commitments and hashes 10 Dominique Unruh
Why this def? Intuition: Adversary cannot produce several openings in superposition If he could, he d notice measurement Formally: Weaker than non-existence of two openings (perfect) Stronger than hard to find two openings (class.-style) kind of |? |? A A |? A A A A A A or |? ? ? Commitments and hashes 11 Dominique Unruh
Properties Perfect binding collapse-binding classical-style binding Avoids change of mind Composes in parallel Rewinding friendly gives ZK arguments of knowledge Simple constructions from collapsing hashes Commitments and hashes 12 Dominique Unruh
Collapsing hash functions Strengthening of collision-resistance for quantum setting Adv. A messages ? (in superposition) |? |? A A A A A A A A or Def: Collapsing = A cannot distinguish Commitments and hashes 13 Dominique Unruh
Collapsing hash functions (ctd.) Simple collapse-binding commitments Statistically hiding Using collapsing hashes in existing constructions Drop in replacement for collision-resistance ? Random oracle is a collapsing hash Suggestion: Collapsing required property for hashes e.g., NIST post-quantum crypto competition Commitments and hashes 14 Dominique Unruh
Collapsing hash funs constructions? Lossy function (LF): Indistinguishable whether injective, or highly non-injective ( lossy ) message LF universal hash func long hash injective on im(??) is collapsing looks injective is collapsing Commitments and hashes 15 Dominique Unruh
Hashing long messages? Prior construction: Fixed compression factor (e.g., 2) For long messages: Merkle-Damg rd ???? ??? ?? ? ? ? ? ???1 ???2 ???3 ??????? Commitments and hashes 16 Dominique Unruh
Summary Classical definitions for commitments & hashes: insufficient! New definitions: collapse-binding / collapsing Constructions from lossy functions / lattice-assumptions Question: Collapsing hashes from OWF / coll.-resistance? Commitments and hashes 17 Dominique Unruh
I thank for your attention This research was supported by European Social Fund s Doctoral Studies and Internationalisation Programme DoRa Dominique Unruh
