Robust Combiners and Universal Constructions for Quantum Cryptography
This study delves into robust combiners and universal constructions for quantum cryptography, focusing on quantum commitments, one-way state generators, quantum money, and unclonable encryption. It explores the reliability of cryptographic constructions based on stronger assumptions, offering insights into enhanced security for various primitives in the quantum realm.
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
Robust Combiners and Universal Constructions for Quantum Cryptography 1 2 2 2 Taiga Hiroka , Fuyuki Kitagawa , Ryo Nishimaki , Takashi Yamakawa 1 Yukawa Institute for Theoretical Physics, Kyoto University 2 NTT Corporation
Outline Motivation Quantum Cryptography Robust Combiners Universal Constructions Result 1 Plaintext Expansion of Unclonable Encryption Result 2 2
Motivation) Quantum Cryptography (1). Cryptography from weaker assumptions Quantum Cryptography Classical Cryptography Quantum Commitments SKE PRSGs Digital Signature PKE OT One-Way State Generators MPC OWFs PRSGs exist even if BQP=QMA (relative to Q oracle)
Motivation) Quantum Cryptography (1). Cryptography from weaker assumptions Previous concrete instantiation relies on OWFs. Rely on unproven computational assumptions. (2). Cryptographic tasks impossible with classical cryptography Public Key Quantum Money Unclonable Encryption Receiver Sender Receiver Sender | | |??? ? |??? ? Our Question: Can we give constructions relied on more reliable assumptions? Everyone can verify money. However, no one can copy it. No one can copy the ciphertext.
Outline Motivation Quantum Cryptography Robust Combiners Universal Constructions Result 1 Plaintext Expansion of Unclonable Encryption Result 2 5
Result 1)Robust Combiner and Universal Construction Our Question: Can we give constructions relied on more reliable assumptions? Explain robust combiners Our results: Robust combiner and universal construction for several primitives. (1).Quantum Commitments (Quantum generalization of Commitments) (2).One-Way State Generators(One of Quantum generalization of OWFs) (3).Quantum Money (4).Unclonable Encryption
(Result 1) Robust Combiner Robust Combiner for a primitive P: Turing machine ? that takes as input candidates ?? ? [?]of the primitive, and outputs new candidate ?[???]. ?[new] satisfies both correctness and security if there exists ?? ? [?]with correctness and security. e.g., Robust Combiner for Quantum commitments ????: Candidate B ????: Candidate D ????: Candidate A ????: Candidate C Find attacks for B, C, and D ???[???]: New Candidate The new candidate satisfies correctness and security properties if one of original candidate satisfies both. Our Results: Robust Combiners for (1). Quantum Commitments (2). OWSGs (3). Quantum Money (4). Unclonable Encryption
(Result 1) Universal Construction Universal Construction for a Primitive P: Construction of the primitive P whose security relies on the existence of the primitive. e.g., Universal Construction for Quantum Commitments: ??????: LWE based Quantum Commitments ??????: LPN based Quantum Commitments ???[????]:Universal Quantum Commitments ???[????] satisfies security as long as secure quantum commitments exist. In this sense, universal construction is the most secure construction. The original motivation of Quantum Cryptography is cryptography without OWFs . However, all previous concrete instantiations rely on assumptions which imply OWFs. Our Results: Universal Constructions for (1). Quantum Commitments (2). OWSGs (3). Quantum Money (4). Unclonable Encryption
Outline Introduction Quantum Cryptography Robust Combiners Universal Constructions Result 1 Plaintext Expansion of Unclonable Encryption Result 2 9
Result 2)Plaintext Expansion of Unclonable Encryption Our Result: We show how to expand plaintext space of unclonable encryption using quantum randomized encoding. B Security of Unclonable Encryption (UE)[BL20] ?? ?? ?? ?? (0,1) Challenger A ? {0,1} ?? ? = ??= ?? ? ?+ ????(?) ?? ?? |?????? C ?? ?? ?? Open Problems: UE for single bit message UE for multi-bit message ? Bit-wise encryption does not work!
Future Directions Q1. Find more quantum cryptographic assumptions plausibly weaker than OWFs? Quantum Case Classical Case Hardness of Learning Quantum States LWE OWSGs Commitments Quantum Advantage Assumption + PPP BQP Discrete Log OWFs Meta-Complexity RSA Q2. Universal construction for Pseudorandom State Generator or Unitary? Q3. Universal construction via Meta-Complexity? Classical Cryptography has universal construction via Meta-complexity. AH-time bounded Kolmogorov Complexity[LP20] OWFs
Idea) Combiner for Quantum Commitments First Step: If both ????and ????satisfy at least binding, then we can construct ??? ??? straightforwardly ???[???] Want to commit b ????(r[1]), ????(r[2]) (1). ? ? + ? ? = ? (2). Commit ? ? using (3). Commit ? ? using ???? ???? Hiding: He cannot learn either ?[?] and ?[?] Binding: She cannot change both ? ? and ?[?] Problem: In general, candidate ???[1] and ??? [2] are not promised to satisfy even binding. Main Technical Contribution Give transformation ? ??? ??? such that (1) ??? satisfies binding regardless of ???. (2) ??? satisfies hiding if ??? satisfies hiding and binding.
Idea) Combiner for Quantum Commitments Main Technique Give transformation ? ??? ??? such that (1) ??? satisfies binding regardless of ???. (2) ??? satisfies hiding if ??? satisfies both hiding and binding. Want to commit b ??? ? ????, ??? ? ???? (1). Commit ? using ??? many times (2). Commit ? using ??? many times Hiding: Both ??? and ??? satisfies hiding. Binding: Either ??? or ??? satisfies binding. There exists a transformation ? ??? ??? such that Flavor Change (1) ??? satisfies binding if ??? satisfies hiding (2) ??? satisfies hiding if ??? satisfies binding Uhlmann Theorem Any candidate of quantum commitment ???satisfies either weak binding or weak hiding
Idea) Combiner for Quantum Commitments Overview of our robust combiner for Quantum Commitments ????: Candidate It is not promised to satisfy even binding. ????:Candidate It is not promised to satisfy even binding Main Technique Main Technique ????: Promised Candidate Statistical binding is promised. ????: Promised Candidate Statistical binding is promised. If ????satisfies binding and hiding ????satisfies hiding. If ????satisfies binding and hiding ????satisfies hiding. Secret Sharing (Explained in the first step) ???[???]:Candidate for Quantum Commitment If either ????or ????satisfies both hiding and binding ???[???] satisfies both hiding and binding
