Abstract
We show a reduction from the existence of explicit t-non-malleable extractors with a small seed length, to the construction of explicit two-source extractors with small error. Previously, such a reduction was known either when one source had entropy rate above half [Raz05] or for general entropy rates but only for large error [CZ16].
As in previous reductions we start with the Chattopadhyay and Zuckerman approach [CZ16], where an extractor is applied on one source to create a table, and the second source is used to sample a sub-table. In previous work, a resilient function was applied on the sub-table and the use of resilient functions immediately implied large error. In this work we replace the resilient function with the parity function (that is not resilient).
The parameters we require from the non-malleable construction hold (quite comfortably) in non-explicit construction, but currently it is not known how to explicitly construct such graphs. As a result we do not give an unconditional construction of an explicit low-error two-source extractor. However, the reduction shows a new connection between non-malleable and two-source extractors, and also shows resilient functions do not play a crucial role in the two-source construction framework suggested in [CZ16].
Joint work with Avraham Ben-Aroya, Eshan Chattopadhyay, Xin Li and Amnon Ta-Shma.