English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this paper we give improved constructions of several central objects inthe literature of randomness extraction and tamper-resilient cryptography. Ourmain results are:  (1) An explicit seeded non-malleable extractor with error $\epsilon$ and seedlength $d=O(\log n)+O(\log(1/\epsilon)\log \log (1/\epsilon))$, that supportsmin-entropy $k=\Omega(d)$ and outputs $\Omega(k)$ bits. Combined with theprotocol in \cite{DW09}, this gives a two round privacy amplification protocolwith optimal entropy loss in the presence of an active adversary, for allsecurity parameters up to $\Omega(k/\log k)$.  (2) An explicit non-malleable two-source extractor for min-entropy $k \geq(1-\gamma)n$, some constant $\gamma>0$, that outputs $\Omega(k)$ bits witherror $2^{-\Omega(n/\log n)}$. Combined with the connection in \cite{CG14b}this gives a non-malleable code in the two-split-state model with relative rate$\Omega(1/\log n)$. This exponentially improves previous constructions, all ofwhich only achieve rate $n^{-\Omega(1)}$.\footnote{The work of Aggarwal et. al\cite{ADKO15} had a construction which "achieves" constant rate, but recentlythe author found an error in their proof.}  (3)A two-source extractor for min-entropy $O(\log n \log \log n)$, which alsoimplies a $K$-Ramsey graph on $N$ vertices with $K=(\log N)^{O(\log \log \logN)}$. We also obtain a seeded non-malleable $9$-source extractor with optimalseed length, which in turn gives a $10$-source extractor for min-entropy$O(\log n)$. Previously the best known extractor for such min-entropy requires$O(\log \log n)$ sources \cite{CohL16}.  Independent of our work, Cohen \cite{Cohen16} obtained similar results to (1)and the two-source extractor, except the dependence on $\epsilon$ is$\log(1/\epsilon)(\log \log (1/\epsilon))^{O(1)}$ and the two-source extractorrequires min-entropy $\log n (\log \log n)^{O(1)}$.

Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors