1 Search Results for "Gürpınar, Emirhan"

Document
DOI: 10.4230/LIPIcs.MFCS.2020.44
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory

Authors: Emirhan Gürpınar and Andrei Romashchenko

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x, y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key the size of which is much smaller than the mutual information between x and y. On the other hand, we provide examples of x, y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses spectral properties of appropriate graphs and the expander mixing lemma as well as various information theoretic techniques.
Cite as

Emirhan Gürpınar and Andrei Romashchenko. Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gurpinar_et_al:LIPIcs.MFCS.2020.44,
  author =	{G\"{u}rp{\i}nar, Emirhan and Romashchenko, Andrei},
  title =	{{Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.44},
  URN =		{urn:nbn:de:0030-drops-127102},
  doi =		{10.4230/LIPIcs.MFCS.2020.44},
  annote =	{Keywords: Kolmogorov complexity, mutual information, communication complexity, expander mixing lemma, finite geometry}
}
  • Refine by Author
  • 1 Gürpınar, Emirhan
  • 1 Romashchenko, Andrei

  • Refine by Classification
  • 1 Mathematics of computing → Information theory
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Expander graphs and randomness extractors

  • Refine by Keyword
  • 1 Kolmogorov complexity
  • 1 communication complexity
  • 1 expander mixing lemma
  • 1 finite geometry
  • 1 mutual information

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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