License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.53
URN: urn:nbn:de:0030-drops-74671
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7467/
Go to the corresponding LIPIcs Volume Portal

Bogdanov, Andrej ; Williamson, Christopher

Approximate Bounded Indistinguishability

pdf-format:
LIPIcs-ICALP-2017-53.pdf (0.4 MB)

Abstract

Two distributions over n-bit strings are (k,delta)-wise indistinguishable if no statistical test that observes k of the n bits can tell the two distributions apart with advantage better than delta. Motivated by secret sharing and cryptographic leakage resilience, we study the existence of pairs of distributions that are (k, delta)-wise indistinguishable, but can be distinguished by some function f of suitably low complexity. We prove bounds tight up to constants when f is the OR function, and tight up to logarithmic factors when f is a read-once uniform AND \circ OR formula, extending previous works that address the perfect indistinguishability case delta = 0.

We also give an elementary proof of the following result in approximation theory: If p is a univariate degree-k polynomial such that |p(x)| <= 1 for all |x| <= 1 and p(1) = 1, then l (p) >= 2^{Omega(p'(1)/k)}, where lˆ (p) is the sum of the absolute values of p’s coefficients. A more general 1 statement was proved by Servedio, Tan, and Thaler (2012) using complex-analytic methods. As a secondary contribution, we derive new threshold weight lower bounds for bounded depth AND-OR formulas.

BibTeX - Entry

@InProceedings{bogdanov_et_al:LIPIcs:2017:7467,
  author =	{Andrej Bogdanov and Christopher Williamson},
  title =	{{Approximate Bounded Indistinguishability}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{53:1--53:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7467},
  URN =		{urn:nbn:de:0030-drops-74671},
  doi =		{10.4230/LIPIcs.ICALP.2017.53},
  annote =	{Keywords: pseudorandomness, polynomial approximation, secret sharing}
}

Keywords: pseudorandomness, polynomial approximation, secret sharing
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI