Unclonable Commitments and Proofs Overview
Get insights into unclonable commitments and proofs with discussions on zero-knowledge proofs, non-malleable proofs, and quantum no-cloning. Explore the results and definitions, including strong unclonability and commitments in the QROM, in this comprehensive topic overview.
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
Unclonable Commitments and Proofs Vipul Goyal, Giulio Malavolta, and Justin Raizes
Zero Knowledge Proofs I claim that ? ?. Prover Adversarial Verifier Witness: w ???
Non-Malleable Proofs [DDN98] I claim that ? ?. I claim that ? ?. Prover Prover Adversarial Verifier Man-in-the-Middle Adversarial Verifier Man-in-the-Middle (MiM) (MiM) Verifier Witness: w ???
Forwarding in Non-malleable Proofs I claim that ? ?. Okay, ? ?. I claim that ? ?. Prover Man-in-the-Middle (MiM) Verifier Witnesses are for losers.
Can we construct proofs cannot be cloned? proofs that More basic question: What about commitments commitments?
Our Results Definitions for unclonable commitments and proofs Same-Protocol: Right sessions use the same protocol as the left session. Commitments from various assumptions, with tradeoffs. Proofs are equivalent to public-key quantum money. Verifier/Receiver Prover/Sender Man-in-the-Middle (MiM) Verifier/Receiver
Our Results Definitions for unclonable commitments and proofs Same-Protocol: Right sessions use the same protocol as the left session. Commitments from various assumptions, with tradeoffs. Proofs are equivalent to public-key quantum money. Strong Unclonability: Right sessions may use arbitrary verification procedures. Commitments in the QROM. Proofs are impossible. Verifier/Receiver Prover/Sender Man-in-the-Middle (MiM) Verifier/Receiver
Our Results Definitions for unclonable commitments and proofs Same-Protocol: Right sessions use the same protocol as the left session. Commitments from various assumptions, with tradeoffs. Proofs are equivalent to public-key quantum money. Strong Unclonability: Right sessions may use arbitrary verification procedures. Commitments in the QROM. Proofs are impossible. This talk Verifier/Receiver Prover/Sender Man-in-the-Middle (MiM) Verifier/Receiver
Definition: Commitments 1) Commit randomly to ?0 or ?1 ???(??) Man-in-the-Middle (MiM) Challenger
Definition: Commitments 1) Commit randomly to ?0 or ?1 ???0 ???(??) Man-in-the-Middle (MiM) Challenger ???1 2) Adversary splits the commitment
Definition: Commitments 3) Oracle reveals committed message 1) Commit randomly to ?0 or ?1 ?0 ???0 Oracle ???(??) Man-in-the-Middle (MiM) Challenger ?1 ???1 2) Adversary splits the commitment Oracle
Definition: Commitments 3) Oracle reveals committed message I guess ? = ?1 1) Commit randomly to ?0 or ?1 ?0 ???0 Oracle ???(??) Distinguisher 1 4) Distinguishers guess b without communicating Man-in-the-Middle (MiM) Challenger ?1 ???1 I guess ? = ?2 2) Adversary splits the commitment Distinguisher 2 Oracle
Definition: Commitments 3) Oracle reveals committed message I guess ? = ?1 1) Commit randomly to ?0 or ?1 ?0 ???0 Oracle ???(??) Distinguisher 1 4) Distinguishers guess b without communicating Man-in-the-Middle (MiM) Challenger ?1 ???1 I guess ? = ?2 2) Adversary splits the commitment Distinguisher 2 Oracle ?1 1 Security: |?? ? = ?0= 2| = ????(?)
Definition: Commitments I guess ? = ?1 ?0 ???0 Oracle ???(??) Distinguisher 1 Man-in-the-Middle (MiM) Challenger ?1 ???1 I guess ? = ?2 Distinguisher 2 Oracle Intuitively, if session 1 is correlated to the left session, then session 2 should be independent.
Unclonable Commitments vs Unclonable Encryption Unclonable Encryption: Adversary tries to split the ciphertext into two parts which it can independently decrypt when it steals the key later. Philosophically: adversary wants to collect information for later use.
Unclonable Commitments vs Unclonable Encryption Unclonable Encryption: Adversary tries to split the ciphertext into two parts which it can independently decrypt when it steals the key later. Philosophically: adversary wants to collect information for later use. Unclonable Commitments: Philosophically: adversary wants to use the information before it breaks hiding.
Definition: Extraction-Unclonability for Proofs Ideal World Real World Prove(s, w) Verifier Prover MiM Verifier
Definition: Extraction-Unclonability for Proofs Ideal World Real World Prove(s, w) ?1,?2 Verifier Prover MiM MiM Simulator Verifier Security: Simulator-extractor simulates the adversary s view without the left witness w. If both right sessions accept, then at least one of ?1or ?2is a valid witness for one of the right sessions.
Construction Key Idea Non-malleability is very similar: ??? ??? Prover MiM Verifier If ??? Idea: unclonable tags! ???, then the right session is independent of the left.
Unclonable Tag Generation Alice Bob ??? ??? At the end of the protocol, Alice and Bob output the same tag.
Unclonable Tag Generation: Security ???2 Honest 2 Honest 1 Man-in-the-Middle (MiM) ???3 ???? Honest 3
Unclonable Tag Generation: Security ???2 Honest 2 Honest 1 Man-in-the-Middle (MiM) ???3 ???? Honest 3 Security: At least one of the three tags output by honest parties is different.
Non Non- -Interactive Interactive Unclonable Tag Generation from Public Public- -Key Quantum Money Key Quantum Money Offline phase Alice Bob
Non Non- -Interactive Interactive Unclonable Tag Generation from Public Public- -Key Quantum Money Key Quantum Money Offline phase Alice Bob
Non Non- -Interactive Interactive Unclonable Tag Generation from Public Public- -Key Quantum Money Key Quantum Money Offline phase Serial number: s Alice Bob
Non Non- -Interactive Interactive Unclonable Tag Generation from Public Public- -Key Quantum Money Key Quantum Money Offline phase Alice Bob Does it match the serial number Alice claimed? Output: s
Non Non- -Interactive Interactive Unclonable Tag Generation from Public Public- -Key Quantum Money Key Quantum Money Offline phase Alice Bob Does it match the serial number Alice claimed? Output: s Output: s
Non Non- -Interactive Interactive Unclonable Tag Generation from Public Public- -Key Quantum Money Key Quantum Money Offline phase Serial number: s Alice Bob Hey, this doesn t match! Serial number: s Charlie
Non-Interactive Unclonable Commitments Commitments Commitment Phase Sender Receiver Opening Phase Sender Receiver
Non-Interactive Unclonable Commitments Commitments Tag is generated and used, but not checked. Commitment Phase Sender Don t need public verifiability! Receiver Reveal secret information allowing the tag to be checked. Opening Phase Sender Receiver
