来自散列函数的PRF？

Question

设$G=\langle g \rangle$是素数阶$Q$的循环群。设$H_1:{0,1}^*\to G$是一个散列函数。下面是$s \in \mathbb{Z}_Q^*$的PRF家族吗？

$$f_s(X)=(H_1(X))^S$

或等效地，设$H_2:{0,1}^*\to \mathbb{Z}^*_Q$为散列函数，

$$f_s(X)=(g^{H_2(X)})^S$

直观地说，它在ROM中，但是有人能证明吗？

Answer 1

第一个构造是著名的随机预言模型中的PRF，具有DDH的安全性.我现在找不到一个很好的参考，在这里这个建筑被明确的框架作为一个PRF，但我会更新，如果我找到它。

编辑:这是在私有集合交集协议中隐含的PRF，可以追溯到: Catherine Meadows。在没有持续可用的第三方的情况下使用的更有效的密码匹配协议。在IEEE安全与隐私研讨会上。1986年Bernardo A. Huberman，Matt Franklin和Tad Hogg.加强电子社区的私隐和信任。在ACM电子商务会议上。1999年

第二个建筑是不安全的。如果我知道f_s(x)，那么我可以将这个值提高到H_2(y)/H_2(x)幂(倒置是mod Q)，这告诉我f_s(y)。因此，我可以很容易地区分f_s(y)和随机。

顺便说一句，在随机预言模型中，f_s(x) = H(s,x)是PRF，f_s(x) = g^{H(s,x)}也是。

Answer 2

我认为，在DDH下，人们可以证明这是一种较弱的PRF形式。如果认为H_1是具有适当区域和范围的H_1'和H_1''两个哈希函数的组合，则如果H_1‘和H_1''都建模为RO，则可以证明D3’和D4在DDH下的构造是PRF。我不知道该建筑是否逐字列出PRF。