SNARK友好的单向压缩功能
SNARK友好的单向压缩功能
提问于 2018-12-19 01:36:55
我正在寻找一个单向压缩功能，是安全和有效的zk电路。这背后的动机来自以下考虑：
- for 256-压缩对于SNARKs来说效率很低。
- Pedersen散列函数是有效的，但其输入上限为32字节，输出为32字节。
- Merkle实现需要一个哈希函数，它接受一个输入64个字节(两个散列的32字节输出)。
因此，我正在寻找一种安全有效地将两个32字节值组合成一个32字节值的方法。
为此，我正在考虑使用MiMC哈希函数，但为此目的似乎有些过分；我已经在使用Pedersen对数据进行散列。也许使用较少回合的MiMC会很好，但也许有更好的方法来实现它。
回答 1
Cryptography用户
发布于 2018-12-20 01:27:33
如果您只需要单向(而不是冲突电阻)，需要一个压缩函数，并且有64个字节的输入，那么您就有可能完全处于这样的状态，即Goldreich单向函数具有适当的参数选择，是不可战胜的。
具体而言：
- 选择一次为所有(并存储)256个均匀随机大小-5个子集的[1,512]。表示它们为(S_i)_{i \leq 256}。
- 定义以下压缩函数f：在输入x \in \{0,1\}^{512}上，将输出的256位y_i中的每一个计算为P(x[S_i])，其中x[S_i]表示由S_i索引的5位x的子集，P表示谓词：
P : (x_1,x_2,x_3,x_4,x_5) \rightarrow x_1 \oplus x_2 \oplus x_3 \oplus x_4\cdot x_5。
过去20年中对Goldreich的功能进行了深入的研究(请参阅我的论文的介绍)。它的安全性还远未被完全理解，但本质上，当您寻找一个非常长的输出时，安全性会大大降低。当你真的想要一个压缩函数并且有一个512位的输入时，我相信它应该保证一个明确的足够的安全级别。
值得注意的是，这是一个完全可并行的函数:所有输出位都可以并行计算。
(当然，还有其他几种乘法次数较少或电路深度较小的方案，但我认为上述方案看起来是一个非常好的选择)。
页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://crypto.stackexchange.com/questions/65975
复制相关文章
相似问题
腾讯云开发者
