License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.21
URN: urn:nbn:de:0030-drops-118823
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11882/
Go to the corresponding LIPIcs Volume Portal

Zimand, Marius

Secret Key Agreement from Correlated Data, with No Prior Information

pdf-format:
LIPIcs-STACS-2020-21.pdf (0.4 MB)

Abstract

A fundamental question that has been studied in cryptography and in information theory is whether two parties can communicate confidentially using exclusively an open channel. We consider the model in which the two parties hold inputs that are correlated in a certain sense. This model has been studied extensively in information theory, and communication protocols have been designed which exploit the correlation to extract from the inputs a shared secret key. However, all the existing protocols are not universal in the sense that they require that the two parties also know some attributes of the correlation. In other words, they require that each party knows something about the other party’s input. We present a protocol that does not require any prior additional information. It uses space-bounded Kolmogorov complexity to measure correlation and it allows the two legal parties to obtain a common key that looks random to an eavesdropper that observes the communication and is restricted to use a bounded amount of space for the attack. Thus the protocol achieves complexity-theoretical security, but it does not use any unproven result from computational complexity. On the negative side, the protocol is not efficient in the sense that the computation of the two legal parties uses more space than the space allowed to the adversary.

BibTeX - Entry

@InProceedings{zimand:LIPIcs:2020:11882,
  author =	{Marius Zimand},
  title =	{{Secret Key Agreement from Correlated Data, with No Prior Information}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11882},
  URN =		{urn:nbn:de:0030-drops-118823},
  doi =		{10.4230/LIPIcs.STACS.2020.21},
  annote =	{Keywords: secret key agreement, Kolmogorov complexity, extractors}
}

Keywords: secret key agreement, Kolmogorov complexity, extractors
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

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