Paper 2020/1371

Two-Source Non-Malleable Extractors and Applications to Privacy Amplification with Tamperable Memory

Divesh Aggarwal and Maciej Obremski and João Ribeiro and Mark Simkin and Luisa Siniscalchi

Abstract

We study two-source non-malleable extractors, which extract randomness from weak sources even when an adversary is allowed to learn the output of the extractor on correlated inputs. First, we study consequences of improving the best known constructions of such objects. We show that even small improvements to these constructions lead to explicit low-error two-source extractors for very low linear min-entropy, a longstanding open problem in pseudorandomness. Moreover, we show the resulting extractor can be made non-malleable for samplable sources in the computational CRS model introduced by Garg, Kalai, and Khurana (Eurocrypt 2020) under standard hardness assumptions, against an unbounded distinguisher. Remarkably, previous constructions of similar extractors require much stronger assumptions. To complement the above, we study unconditional explicit constructions of computational two-source non-malleable extractors for samplable sources in the CRS model with significantly better parameters than their information-theoretic counterparts by exploiting stronger hardness assumptions. Under a quasipolynomial hardness assumption, we achieve security against bounded distinguishers, while assuming the existence of nearly optimal collision-resistant hash functions allows us to achieve security against unbounded distinguishers. Finally, we introduce the setting of privacy amplification resilient against memory-tampering active adversaries. Here, we aim to design privacy amplification protocols that are resilient against an active adversary that can additionally choose one honest party at will and arbitrarily corrupt its memory (i.e., its shared secret and randomness tape) before the execution of the protocol. We show how to design such protocols using two-source non-malleable extractors.

Note: This paper subsumes the following https://eprint.iacr.org/2020/259