Document Open Access Logo

Replacing Probability Distributions in Security Games via Hellinger Distance

Author Kenji Yasunaga

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.17.pdf
  • Filesize: 0.7 MB
  • 15 pages

Document Identifiers

Author Details

Kenji Yasunaga
  • Graduate School of Information Science and Technology, Osaka University, Japan

Funding

This work was supported in part by JSPS Grants-in-Aid for Scientific Research Numbers 16H01705, 17H01695, and 18K11159.

Cite As Get BibTex

Kenji Yasunaga. Replacing Probability Distributions in Security Games via Hellinger Distance. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITC.2021.17

Abstract

Security of cryptographic primitives is usually proved by assuming "ideal" probability distributions. We need to replace them with approximated "real" distributions in the real-world systems without losing the security level. We demonstrate that the Hellinger distance is useful for this problem, while the statistical distance is mainly used in the cryptographic literature. First, we show that for preserving λ-bit security of a given security game, the closeness of 2^{-λ/2} to the ideal distribution is sufficient for the Hellinger distance, whereas 2^{-λ} is generally required for the statistical distance. The result can be applied to both search and decision primitives through the bit security framework of Micciancio and Walter (Eurocrypt 2018). We also show that the Hellinger distance gives a tighter evaluation of closeness than the max-log distance when the distance is small. Finally, we show that the leftover hash lemma can be strengthened to the Hellinger distance. Namely, a universal family of hash functions gives a strong randomness extractor with optimal entropy loss for the Hellinger distance. Based on the results, a λ-bit entropy loss in randomness extractors is sufficient for preserving λ-bit security. The current understanding based on the statistical distance is that a 2λ-bit entropy loss is necessary.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
  • Mathematics of computing → Probability and statistics
Keywords
  • Security proof
  • Hellinger distance
  • randomness extractor
  • entropy loss

Metrics

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

References

  1. Rohit Agrawal. Samplers and extractors for unbounded functions. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA., volume 145 of LIPIcs, pages 59:1-59:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.59.
  2. Shi Bai, Tancrède Lepoint, Adeline Roux-Langlois, Amin Sakzad, Damien Stehlé, and Ron Steinfeld. Improved security proofs in lattice-based cryptography: Using the rényi divergence rather than the statistical distance. J. Cryptology, 31(2):610-640, 2018. URL: https://doi.org/10.1007/s00145-017-9265-9.
  3. Boaz Barak, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Pietrzak, François-Xavier Standaert, and Yu Yu. Leftover hash lemma, revisited. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 1-20. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22792-9_1.
  4. Boaz Barak and Shai Halevi. A model and architecture for pseudo-random generation with applications to /dev/random. In Vijay Atluri, Catherine A. Meadows, and Ari Juels, editors, Proceedings of the 12th ACM Conference on Computer and Communications Security, CCS 2005, Alexandria, VA, USA, November 7-11, 2005, pages 203-212. ACM, 2005. URL: https://doi.org/10.1145/1102120.1102148.
  5. Boaz Barak, Ronen Shaltiel, and Eran Tromer. True random number generators secure in a changing environment. In Colin D. Walter, Çetin Kaya Koç, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2003, 5th International Workshop, Cologne, Germany, September 8-10, 2003, Proceedings, volume 2779 of Lecture Notes in Computer Science, pages 166-180. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-45238-6_14.
  6. Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. How to reduce your enemy’s information (extended abstract). In Hugh C. Williams, editor, Advances in Cryptology - CRYPTO '85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings, volume 218 of Lecture Notes in Computer Science, pages 468-476. Springer, 1985. URL: https://doi.org/10.1007/3-540-39799-X_37.
  7. Itay Berman, Akshay Degwekar, Ron D. Rothblum, and Prashant Nalini Vasudevan. Statistical difference beyond the polarizing regime. Electronic Colloquium on Computational Complexity (ECCC), 26:38, 2019. URL: https://eccc.weizmann.ac.il/report/2019/038.
  8. Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, and Adam D. Smith. Secure remote authentication using biometric data. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of Lecture Notes in Computer Science, pages 147-163. Springer, 2005. URL: https://doi.org/10.1007/11426639_9.
  9. Kai-Min Chung and Salil P. Vadhan. Tight bounds for hashing block sources. In Ashish Goel, Klaus Jansen, José D. P. Rolim, and Ronitt Rubinfeld, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings, volume 5171 of Lecture Notes in Computer Science, pages 357-370. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85363-3_29.
  10. Wei Dai, Viet Tung Hoang, and Stefano Tessaro. Information-theoretic indistinguishability via the chi-squared method. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part III, volume 10403 of Lecture Notes in Computer Science, pages 497-523. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-63697-9_17.
  11. Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput., 38(1):97-139, 2008. URL: https://doi.org/10.1137/060651380.
  12. Yevgeniy Dodis, Krzysztof Pietrzak, and Daniel Wichs. Key derivation without entropy waste. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 93-110. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_6.
  13. Yevgeniy Dodis and Yu Yu. Overcoming weak expectations. In Amit Sahai, editor, Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 1-22. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_1.
  14. Cynthia Dwork. Differential privacy: A survey of results. In Manindra Agrawal, Ding-Zhu Du, Zhenhua Duan, and Angsheng Li, editors, Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008. Proceedings, volume 4978 of Lecture Notes in Computer Science, pages 1-19. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-79228-4_1.
  15. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006. URL: https://doi.org/10.1007/11681878_14.
  16. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014. URL: https://doi.org/10.1561/0400000042.
  17. Rosario Gennaro, Hugo Krawczyk, and Tal Rabin. Secure hashed diffie-hellman over non-ddh groups. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, volume 3027 of Lecture Notes in Computer Science, pages 361-381. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-24676-3_22.
  18. Alison L. Gibbs and Francis Edward Su. On choosing and bounding probability metrics. INTERNAT. STATIST. REV., pages 419-435, 2002. Google Scholar
  19. Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pages 12-24. ACM, 1989. URL: https://doi.org/10.1145/73007.73009.
  20. Hugo Krawczyk. Cryptographic extraction and key derivation: The HKDF scheme. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 631-648. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14623-7_34.
  21. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 1-23. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_1.
  22. Takahiro Matsuda, Kenta Takahashi, Takao Murakami, and Goichiro Hanaoka. Improved security evaluation techniques for imperfect randomness from arbitrary distributions. In Dongdai Lin and Kazue Sako, editors, Public-Key Cryptography - PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part I, volume 11442 of Lecture Notes in Computer Science, pages 549-580. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17253-4_19.
  23. Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with small parameters. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 21-39. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_2.
  24. Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 37(1):267-302, 2007. URL: https://doi.org/10.1137/S0097539705447360.
  25. Daniele Micciancio and Michael Walter. Gaussian sampling over the integers: Efficient, generic, constant-time. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II, volume 10402 of Lecture Notes in Computer Science, pages 455-485. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-63715-0_16.
  26. Daniele Micciancio and Michael Walter. On the bit security of cryptographic primitives. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in Computer Science, pages 3-28. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-78381-9_1.
  27. Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 333-342. ACM, 2009. URL: https://doi.org/10.1145/1536414.1536461.
  28. Thomas Pöppelmann, Léo Ducas, and Tim Güneysu. Enhanced lattice-based signatures on reconfigurable hardware. In Lejla Batina and Matthew Robshaw, editors, Cryptographic Hardware and Embedded Systems - CHES 2014 - 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings, volume 8731 of Lecture Notes in Computer Science, pages 353-370. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44709-3_20.
  29. Thomas Prest. Sharper bounds in lattice-based cryptography using the rényi divergence. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I, volume 10624 of Lecture Notes in Computer Science, pages 347-374. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-70694-8_13.
  30. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discrete Math., 13(1):2-24, 2000. URL: https://doi.org/10.1137/S0895480197329508.
  31. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84-93. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060603.
  32. Oded Regev. The learning with errors problem (invited survey). In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 191-204. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/CCC.2010.26.
  33. Ronen Shaltiel. An introduction to randomness extractors. In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, volume 6756 of Lecture Notes in Computer Science, pages 21-41. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22012-8_2.
  34. Maciej Skorski. Lower bounds on key derivation for square-friendly applications. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 57:1-57:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.57.
  35. John P. Steinberger. Improved security bounds for key-alternating ciphers via hellinger distance. IACR Cryptology ePrint Archive, 2012:481, 2012. URL: http://eprint.iacr.org/2012/481.
  36. Michael Walter. Sampling the integers with low relative error. In Johannes Buchmann, Abderrahmane Nitaj, and Tajje-eddine Rachidi, editors, Progress in Cryptology - AFRICACRYPT 2019 - 11th International Conference on Cryptology in Africa, Rabat, Morocco, July 9-11, 2019, Proceedings, volume 11627 of Lecture Notes in Computer Science, pages 157-180. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-23696-0_9.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact