Document Open Access Logo

Sharp Indistinguishability Bounds from Non-Uniform Approximations

Author Christopher Williamson

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2022.59.pdf
  • Filesize: 0.65 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • bounded indistinguishability
  • randomness
  • secret sharing
  • polynomial approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Christopher Williamson. Sharp Indistinguishability Bounds from Non-Uniform Approximations. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.59

Author Details

Christopher Williamson
  • The SW7 Group, Hong Kong, China

References

  1. RW Barnard, Germund Dahlquist, K Pearce, Lothar Reichel, and KC Richards. Gram polynomials and the kummer function. Journal of approximation theory, 94(1):128-143, 1998. Google Scholar
  2. Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistinguishability and the complexity of recovering secrets. In CRYPTO, 2016. Google Scholar
  3. Andrej Bogdanov, Nikhil S Mande, Justin Thaler, and Christopher Williamson. Approximate degree, secret sharing, and concentration phenomena. RANDOM, 2019. Google Scholar
  4. Andrej Bogdanov and Christopher Williamson. Approximate bounded indistinguishability. In ICALP, 2017. Google Scholar
  5. H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka. Bounds for small-error and zero-error quantum algorithms. In IEEE Symp. on Foundations of Computer Science (FOCS), 1999. Google Scholar
  6. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and markov-bernstein inequalities. Information and Computation, 243:2-25, 2015. Google Scholar
  7. Ronald de Wolf. A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions. arXiv preprint arXiv:0802.1816, 2008. Google Scholar
  8. Xuangui Huang and Emanuele Viola. Approximate degree-weight and indistinguishability. In Electronic Colloquium on Computational Complexity (ECCC), volume 26, page 85, 2019. Google Scholar
  9. Matthias Krause and Hans Ulrich Simon. Determining the optimal contrast for secret sharing schemes in visual cryptography. In Gaston H. Gonnet and Alfredo Viola, editors, LATIN 2000: Theoretical Informatics, volume 1776 of Lecture Notes in Computer Science, pages 280-291. Springer Berlin Heidelberg, 2000. Google Scholar
  10. Christian Kuhlmann and Hans Ulrich Simon. Construction of visual secret sharing schemes with almost optimal contrast. In Symposium on Discrete Algorithms: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, volume 9 (11), pages 263-272, 2000. Google Scholar
  11. Marvin Minsky and Seymour Papert. Perceptrons. MIT Press, Cambridge, MA, 1969. Google Scholar
  12. Moni Naor and Adi Shamir. Visual cryptography. In Advances in Cryptology - EUROCRYPT'94, volume 950 of Lecture Notes in Computer Science, pages 1-12. Springer Berlin Heidelberg, 1994. Google Scholar
  13. DJ Newman and TJ Rivlin. Approximation of monomials by lower degree polynomials. aequationes mathematicae, 14(3):451-455, 1976. Google Scholar
  14. Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. Google Scholar
  15. Ramamohan Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In ACM Symp. on the Theory of Computing (STOC), pages 468-474, 1992. Google Scholar
  16. Sushant Sachdeva and Nisheeth Vishnoi. Approximation theory and the design of fast algorithms. arXiv preprint, 2013. URL: http://arxiv.org/abs/1309.4882.
  17. Alexander A. Sherstov. The pattern matrix method for lower bounds on quantum communication. In 40th ACM Symp. on the Theory of Computing (STOC), pages 85-94, 2008. Google Scholar
  18. Alexander A Sherstov. Approximate inclusion-exclusion for arbitrary symmetric functions. Computational Complexity, 18(2):219-247, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact