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 $\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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. ITC 2021
- Keywords
- extractorsinformation-theoretic privacyeverlasting privacy
- Contact author(s)
-
dodis @ cs nyu edu
kwlyeo @ google com - History
- 2021-05-17: received
- Short URL
- https://ia.cr/2021/637
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/637, author = {Yevgeniy Dodis and Kevin Yeo}, title = {Doubly-Affine Extractors, and their Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/637}, year = {2021}, url = {https://eprint.iacr.org/2021/637} }