Paper 2021/637

Doubly-Affine Extractors, and their Applications

Yevgeniy Dodis and 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 $\mathit{\text{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 $\mathit{\text{stateless}}$ and $\mathit{\text{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 $$ and $$ 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 $$: locally-computable, seeded extractors $$(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 $$ on the extracted key R = $$(X, S); and (b) the seed S is only $$ secure. Neither of properties are possible with general-leakage extractors.