TR17-027 Authors: Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

Publication: 17th February 2017 16:20

Downloads: 225

Keywords:

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 for sources with arbitrarily

small constant rate. 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). We prove correctness by

showing that doing the sampling properly, the sample size can be

made so small that it is smaller then the non-malleability parameter

t of the first extractor, which is enough for the correctness.

The parameters we require from the non-malleable construction hold

(quite comfortably) in a 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]. Furthermore, the

reduction highlights a barrier in constructing non-malleable

extractors, and reveals its importance. We hope this work would lead

to further developments in explicit constructions of both

non-malleable and two-source extractors.