Doubly-affine extractors, and their applications

Yevgeniy Dodis, Kevin Yeo

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2nd Conference on Information-Theoretic Cryptography, ITC 2021
EditorsStefano Tessaro
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771979
StatePublished - Jul 1 2021
Event2nd Conference on Information-Theoretic Cryptography, ITC 2021 - Virtual, Bertinoro, Italy
Duration: Jul 23 2021Jul 26 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference2nd Conference on Information-Theoretic Cryptography, ITC 2021
CityVirtual, Bertinoro


  • Everlasting privacy
  • Extractors
  • Information-theoretic privacy

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Doubly-affine extractors, and their applications'. Together they form a unique fingerprint.

Cite this