Paper 2020/1371

Privacy Amplification with Tamperable Memory via Non-malleable Two-source Extractors

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

Abstract

We extend the classical problem of privacy amplification to a setting where the active adversary, Eve, is also allowed to fully corrupt the internal memory (which includes the shared randomness, and local randomness tape) of one of the honest parties, Alice and Bob, before the execution of the protocol. We require that either one of Alice or Bob detects tampering, or they agree on a shared key that is indistinguishable from the uniform distribution to Eve. We obtain the following results: (1) We give a privacy amplification protocol via low-error non-malleable two-source extractors with one source having low min-entropy. In particular, this implies the existence of such (non-efficient) protocols; (2) We show that even slight improvements to the state-of-the-art explicit non-malleable two-source extractors would lead to explicit low-error, low min-entropy two-source extractors, thereby resolving a long-standing open question. This suggests that obtaining (information-theoretically secure) explicit non-malleable two-source extractors for (1) might be hard; (3) We present explicit constructions of low-error, low min-entropy non-malleable two-source extractors in the CRS model of (Garg, Kalai, Khurana, Eurocrypt 2020), assuming either the quasi-polynomial hardness of DDH or the existence of nearly-optimal collision-resistant hash functions; (4) We instantiate our privacy amplification protocol with the above mentioned non-malleable two-source extractors in the CRS model, leading to explicit, computationally-secure protocols. This is not immediate from (1) because in the computational setting we need to make sure that, in particular, all randomness sources remain samplable throughout the proof. This requires upgrading the assumption of quasi-polynomial hardness of DDH to sub-exponential hardness of DDH. We emphasize that each of the first three results can be read independently.

Note: Revised presentation of results. This paper subsumes the following: https://eprint.iacr.org/2020/259