License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.59
URN: urn:nbn:de:0030-drops-158692
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15869/
Go to the corresponding LIPIcs Volume Portal

Williamson, Christopher

Sharp Indistinguishability Bounds from Non-Uniform Approximations

pdf-format:
LIPIcs-STACS-2022-59.pdf (0.7 MB)

Abstract

We study the basic problem of distinguishing between two symmetric probability distributions over n bits by observing k bits of a sample, subject to the constraint that all (k-1)-wise marginal distributions of the two distributions are identical to each other. Previous works of Bogdanov et al. [Bogdanov et al., 2019] and of Huang and Viola [Huang and Viola, 2019] have established approximately tight results on the maximal possible statistical distance between the k-wise marginals of such distributions when k is at most a small constant fraction of n. Naor and Shamir [Naor and Shamir, 1994] gave a tight bound for all k in the special case k = n and when distinguishing with the OR function; they also derived a non-tight result for general k and n. Krause and Simon [Krause and Simon, 2000] gave improved upper and lower bounds for general k and n when distinguishing with the OR function, but these bounds are exponentially far apart when k = Ω(n). In this work we provide sharp upper and lower bounds on the maximal statistical distance that hold for all k and n. Upper bounds on the statistical distance have typically been obtained by providing uniform low-degree polynomial approximations to certain higher-degree polynomials. This is the first work to construct suitable non-uniform approximations for this purpose; the sharpness and wider applicability of our result stems from this non-uniformity.

BibTeX - Entry

@InProceedings{williamson:LIPIcs.STACS.2022.59,
  author =	{Williamson, Christopher},
  title =	{{Sharp Indistinguishability Bounds from Non-Uniform Approximations}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15869},
  URN =		{urn:nbn:de:0030-drops-158692},
  doi =		{10.4230/LIPIcs.STACS.2022.59},
  annote =	{Keywords: bounded indistinguishability, randomness, secret sharing, polynomial approximation}
}

Keywords: bounded indistinguishability, randomness, secret sharing, polynomial approximation
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

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