All reports by Author Xin Li:

__
TR23-023
| 13th March 2023
__

Xin Li#### Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

Revisions: 1

__
TR18-070
| 13th April 2018
__

Eshan Chattopadhyay, Xin Li#### Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More

Revisions: 3

__
TR18-028
| 7th February 2018
__

Xin Li#### Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications

Revisions: 1

__
TR17-027
| 16th February 2017
__

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma#### A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate

Revisions: 1

__
TR16-180
| 15th November 2016
__

Eshan Chattopadhyay, Xin Li#### Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions

__
TR16-115
| 30th July 2016
__

Xin Li#### Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors

__
TR16-036
| 13th March 2016
__

Eshan Chattopadhyay, Xin Li#### Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols

Revisions: 3

__
TR16-018
| 3rd February 2016
__

Kuan Cheng, Xin Li#### Randomness Extraction in $AC^0$ and with Small Locality

Revisions: 7

__
TR15-178
| 10th November 2015
__

Eshan Chattopadhyay, Xin Li#### Extractors for Sumset Sources

__
TR15-125
| 5th August 2015
__

Xin Li#### Improved Constructions of Two-Source Extractors

Revisions: 2

__
TR15-121
| 25th July 2015
__

Xin Li#### Extractors for Affine Sources with Polylogarithmic Entropy

__
TR15-034
| 8th March 2015
__

Xin Li#### Three-Source Extractors for Polylogarithmic Min-Entropy

__
TR13-025
| 6th February 2013
__

Xin Li#### Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revisions: 1

__
TR12-147
| 7th November 2012
__

Xin Li#### New Independent Source Extractors with Exponential Improvement

__
TR11-166
| 4th December 2011
__

Xin Li#### Non-Malleable Extractors for Entropy Rate $<1/2$

Revisions: 1

__
TR11-161
| 4th December 2011
__

Xin Li#### Design Extractors, Non-Malleable Condensers and Privacy Amplification

__
TR10-190
| 9th December 2010
__

Xin Li#### Improved Constructions of Three Source Extractors

__
TR10-064
| 13th April 2010
__

Xin Li#### A New Approach to Affine Extractors and Dispersers

Xin Li

A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show ... more >>>

Eshan Chattopadhyay, Xin Li

We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: ... more >>>

Xin Li

The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in the following five seemingly different topics: seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey ... more >>>

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

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

Eshan Chattopadhyay, Xin Li

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to many elegant constructions and applications in cryptography. However, most works so far only ... more >>>

Xin Li

In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are:

(1) An explicit seeded non-malleable extractor with error $\epsilon$ and seed length $d=O(\log n)+O(\log(1/\epsilon)\log \log (1/\epsilon))$, that supports min-entropy $k=\Omega(d)$ and outputs $\Omega(k)$ bits. Combined with ... more >>>

Eshan Chattopadhyay, Xin Li

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).

For the first ... more >>>

Kuan Cheng, Xin Li

We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that ... more >>>

Eshan Chattopadhyay, Xin Li

We propose a new model of weak random sources which we call sumset sources. A sumset source $\mathbf{X}$ is the sum of $C$ independent sources $\mathbf{X}_1,\ldots,\mathbf{X}_C$, where each $\mathbf{X}_i$ is an $n$-bit source with min-entropy $k$. We show that extractors for this class of sources can be used to give ... more >>>

Xin Li

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{\Omega(1)}$, while the error remains $n^{-\Omega(1)}$.

... more >>>Xin Li

We give the first explicit construction of deterministic extractors for affine sources over $F_2$, with entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require ... more >>>

Xin Li

We continue the study of constructing explicit extractors for independent

general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method --- an extractor for two independent $n$-bit weak random sources with min-entropy as small as $\log n+O(1)$. Previously, the ...
more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only ... more >>>

Xin Li

Dodis and Wichs \cite{DW09} introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable ... more >>>

Xin Li

We introduce a new combinatorial object, called a \emph{design extractor}, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications.

\begin{enumerate}

\item {Improving the output length of known non-malleable extractors.} Non-malleable extractors ...
more >>>

Xin Li

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on $n$ bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy $0.499n$ \cite{Bourgain05}, and the ... more >>>

Xin Li

We study the problem of constructing affine extractors over $\mathsf{GF(2)}$. Previously the only known construction that can handle sources with arbitrarily linear entropy is due to Bourgain (and a slight modification by Yehudayoff), which relies heavily on the technique of Van der Corput differencing and a careful choice of a ... more >>>