Doubly-Affine Extractors, and their Applications
Doubly-Affine Extractors, and their Applications
复制标题
DOI：
10.4230/lipics.itc.2021.13
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Y. Dodis;Kevin Yeo
中科院分区：
文献类型：
--
作者：
Y. Dodis;Kevin Yeo
在这项工作中，我们挑战了普遍的误解，即信息理论（IT）隐私太不切实际，无法在现实世界中使用：我们建议构建简单且可重用的IT加密解决方案，其唯一的效率损失（与计算安全方案相比）来自较大的密钥大小，这通常是一个相当小的不便，因为存储便宜。特别是，我们的解决方案是无状态的，并且以最优速率可在本地计算，这意味着诚实的各方在每次使用时不维护状态，并且只读取（最优）其大密钥的一小部分。此外，我们还提出了一种新颖的架构，用于将这些长密钥的存储外包给半可信服务器网络，在假设很难同时危及太多可公开访问的ad-hoc服务器的情况下，交换了存储大型秘密的需要。我们的体系结构支持派生的一次性密钥的永久隐私和应用后安全性，解决了外包密钥存储的相关模型（称为有界存储模型）的两个主要限制。这两个结果都来自于所谓的双仿射提取器的近乎最优结构：局部可计算的种子提取器Ext (X， S)，它是X的线性函数（对于任何固定的种子S），并防止X上的有界仿射泄漏。这是无条件成立的，即使(a)仿射泄漏可以自适应地依赖于提取的密钥R = Ext (X， S)；(b)种子S仅是计算安全的。这两种特性在一般泄漏提取器中都不可能实现。
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.