Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption
Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption
复制标题
Fiat-Shamir 和强 KDM 安全加密的关联难处理性
DOI：
10.1007/978-3-319-78381-9_4
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ron D. Rothblum
中科院分区：
文献类型：
--
作者：
R. Canetti;Yilei Chen;Leonid Reyzin;Ron D. Rothblum
如果对于所有稀疏关系，给定哈希函数族中的随机函数，很难找到满足该关系的输入-输出对，则哈希函数族被称为相关性棘手（Canetti等人，STOC 1998）。相关性棘手性（CI）捕获散列函数的强随机Oracle类属性。特别是，当安全持有的所有稀疏关系，CI足以保证健全的菲亚特-沙米尔变换从任何恒定轮，统计上健全的互动证明一个非互动的论点。然而，迄今为止，用于所有稀疏关系的唯一CI散列函数（Kalai等人，Crypto 2017）基于具有指数硬度属性的通用程序混淆。
A hash function family is called correlation intractable if for all sparse relations, it is hard to find, given a random function from the family, an input-output pair that satisfies the relation (Canetti et al., STOC 1998). Correlation intractability (CI) captures a strong Random-Oracle-like property of hash functions. In particular, when security holds for all sparse relations, CI suffices for guaranteeing the soundness of the Fiat-Shamir transformation from any constant round, statistically sound interactive proof to a non-interactive argument. However, to date, the only CI hash function for all sparse relations (Kalai et al., Crypto 2017) is based on general program obfuscation with exponential hardness properties.