Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification
 
conference paper

Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification

Aggarwal, Divesh  
•
Hosseini, Kaave
•
Lovett, Shachar
2016
2016 Ieee International Symposium On Information Theory
IEEE International Symposium on Information Theory (ISIT)

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a weak random source x with min-entropy k and a uniformly random seed Y of length d, and outputs a string of length close to k that is close to uniform and independent of Y. Dodis and Wichs [DW09] introduced a generalization of randomness extractors called non-malleable extractors (nmExt) where nmExt(X, Y) is close to uniform and independent of Y and nmExt(X, f(Y)) for any function f with no fixed points. We relax the notion of a non-malleable extractor and introduce what we call an affine-malleable extractor (AmExt : Fn x Fd -> F) where AmExt(X, Y ) is close to uniform and independent of Y and has some limited dependence of AmExt(X, f(Y )) - that conditioned on Y , (AmExt(X, Y ), AmExt(X, f(Y ))) is epsilon-close to (U, A U + B) where U is uniformly distributed in F and A, B is an element of F are random variables independent of U. We show that the inner-product function (,) : FnxFn -> F is an affine-malleable extractor for min-entropy k = n/2 + Omega(log(1/epsilon)). Moreover, under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture), we show that this holds for k = Omega(log n log(1/epsilon)). As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial Freiman-Ruzsa conjecture. We also study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. The main application of non-malleable extractors and their many variants has been in constructing secure privacy amplification protocols. We show that affine-malleable extractors along with affine-evasive sets can also be used to construct efficient privacy amplification protocols. This gives a much simpler protocol for min-entropy k = n/2 + Omega(log(1/epsilon)), and additionally, under the Spectrum Doubling Conjecture, achieves near optimal parameters and achieves additional security properties like source privacy that have been the focus of some recent results in privacy amplification.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/ISIT.2016.7541832
Web of Science ID

WOS:000390098702196

Author(s)
Aggarwal, Divesh  
Hosseini, Kaave
Lovett, Shachar
Date Issued

2016

Publisher

Ieee

Publisher place

New York

Published in
2016 Ieee International Symposium On Information Theory
ISBN of the book

978-1-5090-1806-2

Total of pages

5

Series title/Series vol.

IEEE International Symposium on Information Theory

Start page

2913

End page

2917

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LASEC  
Event nameEvent placeEvent date
IEEE International Symposium on Information Theory (ISIT)

Barcelona, SPAIN

JUL 10-15, 2016

Available on Infoscience
February 17, 2017
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/134468
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés