1 Search Results for "Yasunaga, Kenji"

Document
DOI: 10.4230/LIPIcs.ITC.2021.17
Replacing Probability Distributions in Security Games via Hellinger Distance

Authors: Kenji Yasunaga

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{yasunaga:LIPIcs.ITC.2021.17,
  author =	{Yasunaga, Kenji},
  title =	{{Replacing Probability Distributions in Security Games via Hellinger Distance}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.17},
  URN =		{urn:nbn:de:0030-drops-143361},
  doi =		{10.4230/LIPIcs.ITC.2021.17},
  annote =	{Keywords: Security proof, Hellinger distance, randomness extractor, entropy loss}
}
  • Refine by Author
  • 1 Yasunaga, Kenji

  • Refine by Classification
  • 1 Mathematics of computing → Probability and statistics
  • 1 Security and privacy → Cryptography

  • Refine by Keyword
  • 1 Hellinger distance
  • 1 Security proof
  • 1 entropy loss
  • 1 randomness extractor

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact