Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-027 | 24th January 2018 23:08

A New Approach for Constructing Low-Error, Two-Source Extractors

RSS-Feed




Revision #1
Authors: Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
Accepted on: 24th January 2018 23:08
Downloads: 1049
Keywords: 


Abstract:

Our main contribution in this paper is a new reduction from explicit two-source extractors for polynomially-small entropy rate and negligible error to explicit t-non-malleable extractors with seed-length that has a good dependence on t. Our reduction is based on the Chattopadhyay and Zuckerman framework [CZ16], and surprisingly we dispense with the use of resilient functions which appeared to be a major ingredient in [CZ16] and follow-up works. The use of resilient functions posed a fundamental barrier towards achieving negligible error, and our new reduction circumvents this bottleneck.

The parameters we require from t-non-malleable extractors for our reduction to work hold (quite comfortably) in a non-explicit construction,
but currently it is not known how to explicitly construct such extractors. As a result we do not give an unconditional construction of an explicit low-error
two-source extractor. Nonetheless, we believe our work gives a viable approach for solving the important problem of low-error two-source extractors. Furthermore, our work highlights an existing barrier in constructing low-error two-source extractors, and draws attention to the dependence of the parameter t in the seed-length of the non-malleable extractor. We hope this work would lead to further developments in explicit constructions of both non-malleable and two-source extractors.



Changes to previous version:

major revision to presentation with more detailed explanations of results.


Paper:

TR17-027 | 16th February 2017 22:30

A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate





TR17-027
Authors: Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
Publication: 17th February 2017 16:20
Downloads: 1000
Keywords: 


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 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.



ISSN 1433-8092 | Imprint