Encrypted Multi-Maps with Computationally-Secure Leakage
Encrypted Multi-Maps with Computationally-Secure Leakage
复制标题
具有计算安全泄漏的加密多地图
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Tarik Moataz
中科院分区：
文献类型：
--
作者：
S. Kamara;Tarik Moataz
本文首先研究了具有计算安全泄漏的结构化加密方案。具体来说，我们专注于体积隐藏加密的多地图的设计，也就是说，加密的多地图隐藏的响应长度计算有界的对手。我们描述了第一个卷隐藏STE计划，不依赖于天真的填充，也就是说，填充所有元组相同的长度。我们的第一个构造具有高效的查询复杂度和存储，但可能是有损的。然而，我们表明，对于一大类多重映射（即，长度根据Zipf分布分布）。我们的第二个构造是无损的，并且可以实现渐进地优于Zipf分布式多映射的朴素填充的存储开销。我们还展示了如何进一步提高存储时，多地图是高度集中的意义上，它有大量的元组与一个大的交集。我们通过利用计算假设来实现这些结果。不仅仅是为了加密，更有趣的是，为了隐藏卷本身。我们的第一个结构实现了这一点，使用伪随机函数，而我们的第二个结构实现了这一点，依靠种植的dendrifugal子图问题，这是一个种植的变体，研究dendrifugal子图问题的dendrifugal硬度。该假设先前被用于设计公钥加密方案（Applebaum等人，STOC '10）和研究金融产品的计算复杂性（Arora等人，ICS '10）。brown.edu.†tarik_moataz@brown.edu.
We initiate the study of structured encryption schemes with computationally-secure leakage. Specifically, we focus on the design of volume-hiding encrypted multi-maps; that is, of encrypted multi-maps that hide the response length to computationally-bounded adversaries. We describe the first volume-hiding STE schemes that do not rely on naive padding; that is, padding all tuples to the same length. Our first construction has efficient query complexity and storage but can be lossy. We show, however, that the information loss can be bounded with overwhelming probability for a large class of multi-maps (i.e., with lengths distributed according to a Zipf distribution). Our second construction is not lossy and can achieve storage overhead that is asymptotically better than naive padding for Zipf-distributed multi-maps. We also show how to further improve the storage when the multi-map is highly concentrated in the sense that it has a large number of tuples with a large intersection. We achieve these results by leveraging computational assumptions. Not just for encryption but, more interestingly, to hide the volumes themselves. Our first construction achieves this using a pseudo-random function whereas our second construction achieves this by relying on the conjectured hardness of the planted densest subgraph problem which is a planted variant of the well-studied densest subgraph problem. This assumption was previously used to design public-key encryptions schemes (Applebaum et al., STOC ’10 ) and to study the computational complexity of financial products (Arora et al., ICS ’10 ). ∗seny@brown.edu. †tarik_moataz@brown.edu.