License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.13
URN: urn:nbn:de:0030-drops-143320
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14332/
Go to the corresponding LIPIcs Volume Portal

Dodis, Yevgeniy ; Yeo, Kevin

Doubly-Affine Extractors, and Their Applications

pdf-format:
LIPIcs-ITC-2021-13.pdf (0.8 MB)

Abstract

In this work we challenge the common misconception that information-theoretic (IT) privacy is too impractical to be used in the real-world: we propose to build simple and reusable IT-encryption solutions whose only efficiency penalty (compared to computationally-secure schemes) comes from a large secret key size, which is often a rather minor inconvenience, as storage is cheap. In particular, our solutions are stateless and locally computable at the optimal rate, meaning that honest parties do not maintain state and read only (optimally) small portions of their large keys with every use.
Moreover, we also propose a novel architecture for outsourcing the storage of these long keys to a network of semi-trusted servers, trading the need to store large secrets with the assumption that it is hard to simultaneously compromise too many publicly accessible ad-hoc servers. Our architecture supports everlasting privacy and post-application security of the derived one-time keys, resolving two major limitations of a related model for outsourcing key storage, called bounded storage model.
Both of these results come from nearly optimal constructions of so called doubly-affine extractors: locally-computable, seeded extractors Ext(X,S) which are linear functions of X (for any fixed seed S), and protect against bounded affine leakage on X. This holds unconditionally, even if (a) affine leakage may adaptively depend on the extracted key R = Ext(X,S); and (b) the seed S is only computationally secure. Neither of these properties are possible with general-leakage extractors.

BibTeX - Entry

@InProceedings{dodis_et_al:LIPIcs.ITC.2021.13,
  author =	{Dodis, Yevgeniy and Yeo, Kevin},
  title =	{{Doubly-Affine Extractors, and Their Applications}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{13:1--13:23},
  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.dagstuhl.de/opus/volltexte/2021/14332},
  URN =		{urn:nbn:de:0030-drops-143320},
  doi =		{10.4230/LIPIcs.ITC.2021.13},
  annote =	{Keywords: extractors, information-theoretic privacy, everlasting privacy}
}

Keywords: extractors, information-theoretic privacy, everlasting privacy
Collection: 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Issue Date: 2021
Date of publication: 19.07.2021

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