Aggarwal, Divesh and Chung, Kai-Min and Lin, Han-Hsuan and Vidick, Thomas (2019) A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries. In: Advances in Cryptology - EUROCRYPT 2019. Lecture Notes in Computer Science. No.11477. Springer , Cham, pp. 442-469. ISBN 978-3-030-17655-6. https://resolver.caltech.edu/CaltechAUTHORS:20190320-102401828
![]() |
PDF
- Submitted Version
See Usage Policy. 431kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190320-102401828
Abstract
In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantum-proof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, this simple solution is no longer secure. Nevertheless, Dodis and Wichs (STOC’09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor. We give the first construction of a non-malleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS’12), and is able to extract from source of min-entropy rates larger than 1 / 2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, due to Cohen and Vidick (unpublished) we obtain the first privacy amplification protocol secure against active quantum adversaries.
Item Type: | Book Section | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||||||||||
ORCID: |
| ||||||||||||||||||||||
Additional Information: | © 2019 International Association for Cryptologic Research. First Online: 24 April 2019. D. Aggarwal—This research was further partially funded by the Singapore Ministry of Education and the National Research Foundation under grant R-710-000-012-135. K.-M. Chung—This research is partially supported by the 2016 Academia Sinica Career Development Award under Grant no. 23-17, and MOST QC project under Grant no. MOST 107-2627-E-002-002. H.-H. Lin—This material is based on work supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13. T. Vidick—Supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). | ||||||||||||||||||||||
Group: | Institute for Quantum Information and Matter | ||||||||||||||||||||||
Funders: |
| ||||||||||||||||||||||
Series Name: | Lecture Notes in Computer Science | ||||||||||||||||||||||
Issue or Number: | 11477 | ||||||||||||||||||||||
DOI: | 10.1007/978-3-030-17656-3_16 | ||||||||||||||||||||||
Record Number: | CaltechAUTHORS:20190320-102401828 | ||||||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190320-102401828 | ||||||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||||
ID Code: | 93984 | ||||||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||||||
Deposited By: | Tony Diaz | ||||||||||||||||||||||
Deposited On: | 20 Mar 2019 17:35 | ||||||||||||||||||||||
Last Modified: | 16 Nov 2021 17:02 |
Repository Staff Only: item control page