New Realizations of Somewhere Statistically Binding Hashing and Positional Accumulators
New Realizations of Somewhere Statistically Binding Hashing and Positional Accumulators
复制标题
某处统计绑定散列和位置累加器的新实现
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Daniel Wichs
中科院分区：
文献类型：
--
作者：
T. Okamoto;Krzysztof Pietrzak;Brent Waters;Daniel Wichs
由HUBAă和WICHS ITCS‘15引入的某处具有统计约束力的单边带哈希可用于使用公共散列密钥$$\mathsf{HK}$$将长字符串x散列为短摘要$$y=H_{\mathsf{hk}}x$$。此外，存在一种设置散列键$$\mathsf{HK}$$以使其在某个任意隐藏位置i上统计地绑定的方法，这意味着：1摘要y完全确定x的第i比特或符号，使得y的所有前图像在第i位置具有相同的值，2在计算上不可能区分其上的$$\mathsf{HK}$$与任何其他位置$$i‘$的统计绑定的位置i。最后，散列应该有一个类似于Merkle-Tree散列的局部开始属性，这意味着给定x和$$y=H_{\mathsf{HK}}x$$，应该可以创建简短的证明$$\pi$$来证明x的第i位或符号的值，而不必提供整个输入x。由KopPula，Lewko和Waters Stoc‘15引入的类似的称为位置累加器的原语进一步支持散列值的动态更新。这些工具本身很有趣，也是最近几个从不可区分的混淆中构建高级应用程序的主要技术组件之一。
单边带散列和位置累加器的先前构造分别需要完全同态加密FHE和IO。在这项工作中，我们给出了这些工具的新构造，这些工具是基于充分研究的数论假设，如DDH，Phi-隐藏和DCR，以及由有耗/内射函数构造的一般工具。
A somewhere statistically binding SSB hash, introduced by Hubaăi¾?ek and Wichs ITCS '15, can be used to hash a long string x to a short digest $$y = H_{\mathsf {hk}}x$$ using a public hashing-key $$\mathsf {hk}$$ . Furthermore, there is a way to set up the hash key $$\mathsf {hk}$$ to make it statistically binding on some arbitrary hidden position i, meaning that: 1 the digest y completely determines the i'th bit or symbol of x so that all pre-images of y have the same value in the i'th position, 2 it is computationally infeasible to distinguish the position i on which $$\mathsf {hk}$$ is statistically binding from any other position $$i'$$ . Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and $$y = H_{\mathsf {hk}}x$$ it should be possible to create a short proof $$\pi $$ that certifies the value of the i'th bit or symbol of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters STOC '15 further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation iO.
The prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption FHE and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions.
影响因子：
3
作者：
Eike Kiltz;Adam O'Neill;Adam D. Smith
通讯作者：
Eike Kiltz;Adam O'Neill;Adam D. Smith