Paper 2019/254

A Quantum-Proof Non-Malleable Extractor With Application to Privacy Amplification against Active Quantum Adversaries

Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, and Thomas Vidick

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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2019
Keywords
Privacy AmplificationNon-malleable extractorsQuantum Cryptography
Contact author(s)
dcsdiva @ nus edu sg
kmchung @ iis sinica edu tw
linhh @ cs utexas edu
vidick @ cms caltech edu
History
2019-02-28: received
Short URL
https://ia.cr/2019/254
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/254,
      author = {Divesh Aggarwal and Kai-Min Chung and Han-Hsuan Lin and Thomas Vidick},
      title = {A Quantum-Proof Non-Malleable Extractor With Application to Privacy Amplification against Active Quantum Adversaries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/254},
      year = {2019},
      url = {https://eprint.iacr.org/2019/254}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.