Title: A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries,
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, 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, shown by Cohen and Vidick (unpublished), we
obtain the first privacy amplification protocol secure against active quantum
adversaries.