Exploring Microcrypt: Quantum Cryptography Challenges and Solutions
Delve into the depths of Microcrypt and uncover the challenges and solutions in quantum cryptography, such as separating OWSGs and Quantum Money from QEFID. This cutting-edge research funded by the Israel Science Foundation and the European Union sheds light on average-case hard problems, quantum cryptographic landscapes, and more.
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
A New World In the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID Amit Behera BGU Giulio Malavolta Bocconi University Tomoyuki Morimae Kyoto University Takashi Yamakawa NTT Research Tamer Mour Bocconi University Eurocrypt 2025 May 5, 2025 This project has received funding from the Israel Science Foundation (grant No. 2527/24) and the European Union (ERC-2022-COG, ACQUA, 10108774. 1
Quantum Cryptography Based on average-case hard problems. - Easy to generate a hard instance. - Solution always exists. - Hard to find a solution given (many copies) of the instance. 2
OWSGs [Morimae-Yamakawa24] Average-case hard search problem. ? ? ? , ? accept/reject ? ? Given ? copies of ?, find ? such that ? ?,? =accept. 3
EFI pairs [Brakerski-Canneti-Qian23] Average-case hard decision problem. ?0 ?1 Distinguish between ?0 and ?1. Quantumly Efficient to generate, statistically Far, computationally Indistinguishable. 4
QEFID pairs [Chung-Goldin-Gray24] Average-case hard decision problem. ?0 ?1 Distinguish between ?0 and ?1. Quantumly Efficient to generate, statistically Far, computationally Indistinguishable. 5
Quantum Cryptographic landscape Classical Crypto Cryptomania Public key encryption Minicrypt OWF Microcrypt Average case hard cloning ? ? OWSG EFI Commimtments What is the minimal assumption? 7
Quantum Cryptographic landscape Classical Crypto Cryptomania Public key encryption Minicrypt OWF Microcrypt Private quantum money ? ? OWSG EFI Commimtments What is the minimal assumption? 8
Quantum Cryptographic landscape Classical Crypto Cryptomania Public key encryption Minicrypt OWF Microcrypt Private quantum money OWSG EFI Commimtments What is the minimal assumption? 9
Main results 11
Our Results oracle separation QEFID OWSG therefore, PRS and EV-OWPuzz therefore, EFI, and OWPuzz fully black-box separation Private Quantum Money QEFID [Bostanci-Chen-Nehoran 24] [Chen-Coladangelo-Sattath 24] Concurrent Work: therefore, EFI 1-PRS PRS therefore, EFI OWPuzz,1-PRS OWSG 12
Quantum Cryptographic landscape All of Quantum Cryptography Efficiently verifiable Microcrypt Private quantum money EV OWpuzz OWSG Inefficiently verifiable Microcrypt QEFID OWpuzz IV OWSG EFI Commimtments minimal primitive 13
Technical section QEFID OWSG 14
a unitary oracle where QEFID and OWSG Two-Oracle Recipe Hardness Oracle Gives sufficient hardness to build QEFID Inversion Oracle Gives sufficient computational power to break any OWSG + 15
The ?-Oracle Samples a uniformly random subset ? 0,1?\{0?} of size 2?/2. 0? ? ? Reflection ? ? ??= ? 2 ? ? ? = ? 0? ? ? ? = 0 ? / 2 ? 0?, ? ? 16
Hardness oracle: The controlled-U? Samples a uniformly random subset ? 0,1?\{0?} of size 2?/2. Controlled Reflection about ? = 0 ? / 2 ? ? ? 0, 1,?? ? = 0 ? = 1 ? ??= ? 2 ? ? 17
Fun Facts about the ?-Oracle 1. Can extract ? from . ? 0 ? 2. Can simulate using copies of ? [JLS 18]. ? s.t. ? ? ?(?) ? ? ? ? ? ?(?) ? ? 18
a unitary oracle where QEFID and OWSG ?0:a uniformly random? 0,1?. ? ? {?,?} 0/1 ?1:a uniformly random? ?. 2. Can simulate using copies of ? . 19
a unitary oracle where QEFID and OWSG ?0:a uniformly random? 0,1?. ? {?,?} ? 0/1 ?1:a uniformly random? ?. ? ? 2. Can simulate using copies of ? . Statistical Lemma: (?, ? ?) (?, ? ?) Holds under any additional oracle! (that is independent in ?) 20
a unitary oracle where QEFID and OWSG Two-Oracle Recipe Hardness Oracle Gives sufficient hardness to build QEFID Inversion Oracle Gives sufficient computational power to break any OWSG + 21
a unitary oracle where QEFID and OWSG Two-Oracle Recipe Hardness Oracle Gives sufficient hardness to build QEFID Inversion Oracle Gives sufficient computational power to break any OWSG + QPSPACE machine (Unitary PSPACE) Gentle-Search [Aaronson 19] + S-oracle emulation 22
Thanks ia.cr/2024/1567 *Slides Credit- Tamer Mour 23
