Quantum Public-Key Encryption with Tamper-Resilient Public Keys
Explore the concept of Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions. Learn about the essentials of Public-key Encryption (PKE), computational assumptions, and the implications of realizing PKE from OWFs in the quantum world. Delve into topics like statistical security, multiparty computation, and quantum-authenticated channels.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions Fuyuki Kitagawa (NTT), Tomoyuki Morimae (Kyoto Univ.), Ryo Nishimaki (NTT), Takashi Yamakawa (NTT & Kyoto Univ.) arXiv:2304.01800 1 Slides made by Tomoyuki Morimae
Public-key Encryption (PKE): (KeyGen, Enc, Dec) Receiver Sender ?? ??,?? ??????(1?) ???????:? ?? ?? ???(??,?) ?? ? ???(??,??) They do not need to share key in advance! 2
PKE needs computational assumption Cryptomania Multiparty computation Key exchange PKE [IR89] Zero knowledge PRGs Minicrypt OWFs Commitments SKE Digital signatures PKE needs stronger assumptions than OWFs 3 3
What happens in the Q world? Statistical security[BB84] ? Multiparty computation Cryptomania PKE Key exchange [BCKM21,GLSV21] Zero knowledge PRGs Minicrypt OWFs Commitments SKE Digital signatures Can we realize PKE from OWFs? 4 4
YES (Concurrent to [Malavolta, Walter, 2024]) 5
Quantum Public-key Encryption (QPKE) Receiver Sender Quantum ?? ?????(1?) ?? ?????(??) ?? ?? ???(??,?) Classical ?? ? ???(??,??) We construct QPKE from OWFs! 6
Subtle issue: authentication ?? should be authenticated Receiver Sender ?? ,?? ??????(1?) ??,?? ??????(1?) ?? ?? ?? ???(?? ,?) ?? ? ???(?? ,??) In classical PKE, pk is authenticated by, e.g., digital signatures 7
Quantum authenticated channel? Quantum authenticated channel Receiver Sender ?? ??,?? ??????(1?) However, quantum authentication channel quantum secure channel The problem becomes trivial! [Coladangelo 2023] and [Barooti, Grilo, Huguenin-Dumittan, Malavolta, Sattath, Vu, Walter, 2023] assume Q authenticated channel 8
In our QPKE, (1)Quantum channels are NOT authenticated (2)Classical channels are authenticated This is the same as the classical PKE 9
Construction 10
?0,?1 0,1? ? {0,1} ?? = (?0,?1) ?? = 0 ?0 + 1 |?1 ???= 0 ?0+ 1?1 |?1 ? ???(??,??) If the adversary can distinguish ??0and ??1, it can get both ?0 and ?1. 11 [Aaronson, Atiya, Susskind, 2020] [Hhan, Morimae, Yamakawa, 2022] Q authenticated channel is necessary
?? ????,?? ????.??????(1?) ? {0,1} ?? = ???? ?? = 0 ?(0) + 1 |?(1) Verify signature coherently ???= ? 0 ?(0) + 1?? 1 |?(1) If OK, the state is ? 0 ? 0 + ? 1 |? 1 12 If the adversary can distinguish ??0and ??1, it can get both ? 0 and ?(1). Many copies of ?? cannot be distributed
????,?? ????.??????(1?) ? {0,1} ?? = ???? ? 0,1? ?? = (?, 0 ? 0? + 1 |?(1?)) + 1?1 |?(1?) ) ???= (?, 0 ? 0? 13 ?? is quantum
????,?? ????.??????(1?) ? {0,1} ?? = ???? ? 0,1? ?? = (?, 0 ? 0? + 1 |?(1?)) Measure 0 ? 0? in the Hadamard basis to obtain ? + 1?1 |?(1?) ?? = (?,?) 14 ? = ? (0| ? 0? 1 |?(1?)) Can the receiver detect decryption error?
??,?? ??????(1?) ?? ?? ???(??,?||?(?)) ?? 15
CCA security ?? ?? ??,?? ??????(1?) ?? ??( ?? ) Error oracle Decryption oracle / ???(??,??) 16 We give a generic compiler from CPA to CCA Such a general compiler is an open problem in classical PKE!
Open problem 1: classical pk is possible? If pk is classical If pk is quantum |?? ?? ?? ?? ? |?? ?? ?? |?? ?? |?? Partial negative result shown by [Li, Li, Li, Liu, 2024] 18
Open problem 2: QPKE from weaker assumptions? PKE Cryptomania Multiparty computation ? Zero knowledge PRGs Minicrypt OWFs SKE Commitments Digital signatures Microcrypt OWSGs PRSGs EFI Pessiland No classical crypto 19 19
Thank you 20
