Unpredictable States Generators in Quantum Cryptography

quantum unpredictability n.w
1 / 18
Embed
Share

Explore the concept of unpredictable states generators (UPSGs) in quantum cryptography, demonstrating their role in constructing secure cryptographic primitives such as SKE and MACs. Delve into the necessity of UPSGs and their implications on quantum unpredictability.

  • Quantum Cryptography
  • UPSGs
  • Cryptographic Primitives
  • Unpredictability
  • Quantum Security

Uploaded on | 0 Views


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


  1. Quantum Unpredictability Tomoyuki Morimae (1) Shogo Yamada 1 Takashi Yamakawa 1,2,3 1. Yukawa Institute for Theoretical Physics, Kyoto University 2. NTT Social Informatics Laboratories 3. NTT Research Center for Theoretical Quantum Information Asiacrypt 2024

  2. Introduction Classical world: pseudorandomness and unpredictability are useful. Unpredictable functions (UPFs) Pseudorandom functions (PRFs) MAC Zero-knowledge proof Bit commitment SKE 1/17

  3. Introduction Quantum world: pseudorandomness is also useful. Pseudorandom function-like states generators (PRFSGs) [AQY22,AGQY22] ??? ?,? = | ??? Security: without ?, | ??? looks like independent (Haar) random state. | ???1 , , ???? Many primitives are implied by PRFSGs: Secret-key encryption (SKE), (unclonable) message authentication codes (MACs),bit commitment, ????. ?1, ,| ?? 2/17

  4. Introduction Quantum world: pseudorandomness is also useful How about unpredictability? Pseudorandom function-like states (PRFSGs) What is a quantum version of unpredictable functions? ??? Equivalent? ??? Useful to construct crypto primitives? [AGQY22,JLS18,MY22] Zero-knowledge proof MAC (with unclonable tags) Bit commitment SKE 3/17

  5. Our results We introduce unpredictable states generators (UPSGs). From UPSGs, we construct IND-CPA SKE and EUF-CMA MACs with unclonable tags. From them, all known primitives implied by PRFSGs are also implied. We show BQP PP is necessary for UPSGs. (We omit in this talk.) 4/17

  6. Our results Trivial Unpredictable states generators (UPSGs) Pseudorandom function-like states (PRFSGs) Take home: For quantum crypto, unpredictability is sufficient! All known primitives implied by PRFSGs Zero-knowledge proof MACs (with unclonable tags) Bit commitment SKE 5/17

  7. UPSGs 6/17

  8. Warming up: Unpredictable functions [NR98] Adversary Challenger ??(?): efficiently computable (given ? and ?) ?1,?2, ? {0,1}? ???1,???2, Unpredictable! ? ,? Not queried before! Pr[??? = ? ] negl( ) 7/17

  9. Unpredictable states generators (UPSGs) Adversary Challenger (?) : efficiently generatable |?? (given ? and ?) ?1,?2, (?2) , ? {0,1}? |?? (?1) ,|?? ???1,???2, Unpredictable! ? ? ,? ??? |?|?? ? ????(?) Not queried before! Pr[??? = ? ] negl( ) 8/17

  10. SKE from UPSGs 9/17

  11. IND-CPA SKE : Definition W.l.o.g., we can consider IND-CPA SKE for single bit message. Adversary Challenger ?1,?2, ???1,???2,... ? {0,1}? ??? ? {0,1} ? Pr ? = ? 1 2+ ????(?) 10/17

  12. IND-CPA SKE : Construction Adversary Challenger ?1,?2, ???1,???2,... ? {0,1}? + 1??? ???= (?,?, ?? ? ? ) ? {0,1} with ?,? {0,1}? |?? ? : UPSG ? Pr ? = ? 1 2+ ????(?) 11/17

  13. IND-CPA SKE : Proof Adversary Challenger + 1??? ???= (?,?, ?? ? ? ) with ?,? {0,1}? |?? ? : UPSG ? ? {0,1}? Goal: Show ??0is indistinguishable from ??1without ?. ? {0,1} Theorem [HMY23,AAS20] Distinguishing | is as hard as converting | ??? from | ??? ??? + | ??(?) into | ??? | ??(?) . ??(?) is unpredictable even if the adversary has | ??(?) . | The adversary cannot distinguish ??0 from ??1! 12/17

  14. MACs with unclonable tags from UPSGs 13/17

  15. Unclonable MACs: Definition Adversary Challenger ?1,?2, ???1,???2,... ? {0,1}? Not queried before! ? ??? Unclonable ? Remark: EUF CMA security is implied by the unclonability. ? is far from ??(? ) 2 14/17

  16. Unclonable MACs: Construction ??(?) are How do we make tag states unclonable? We can t say UPSGs | unclonable in general. Idea: BB84 states (Wisner money) + SKE Let ??? be SKE and ? (? ,? ). (?,?,?): random ???(? ,(?,?,?)) ?,?,? ,| ??,|??(?,?,?) ) ??? (??|?? Random Pauli labeled by ? BB84 state UPSGs 15/17

  17. Unclonable MACs: Proof of unclonability Adversary Challenger Learning phase ? : not queried before ?,?,? ,| ??,|??(?,?,?) ) (??|?? ? = (? ,? ) {0,1}2? (?,?,?): random |??(?,?,?) ???(? ,(?,?,?)) Because adversary does not know ? = (? ,? ) ?,?,? ,| ?,?,? ,| ??,|??(0 0) ) ??,|??(?,?,?) ) ??,|??(0 0) ) (??|?? (??|?? (? 2?,| Security of SKE Random Pauli Unclonable! 16/17

  18. Summary and open problem Summary We formalize UPSGs as a quantum analogue of unpredictable functions. We show all known primitives implied by PRFSGs are also implied by UPSGs. For constructing crypto primitives, unpredictability is sufficient in the quantum world. Open problems Can we separate UPSGs from pseudorandom primitives, PRFSGs, PRSGs and PRUs? Can we find primitives implied by PRFSGs but not implied UPSGs? Thank you! 17/17

More Related Content