Welcome to the resource topic for 2021/637
Title:
Doubly-Affine Extractors, and their Applications
Authors: Yevgeniy Dodis, Kevin Yeo
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 \textit{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 \textit{stateless} and \textit{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 \textit{everlasting privacy} and \textit{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 \textit{doubly-affine extractors}: locally-computable, seeded extractors \textbf{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 \textit{adaptively depend} on the extracted key R = \textbf{Ext}(X, S); and (b) the seed S is only \textit{computationally} secure. Neither of properties are possible with general-leakage extractors.
ePrint: https://eprint.iacr.org/2021/637
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .