2
$\begingroup$

Let $G=\langle g \rangle$ be a cyclic group of prime order $Q$. Let $H_1:\{0,1\}^*\to G$ be a hash function. Is the following a family of PRF for $s \in \mathbb{Z}_Q^*$?

$$f_s(x)=(H_1(x))^s$$

Or equivalently, let $H_2:\{0,1\}^*\to \mathbb{Z}^*_Q$ be a hash function,

$$f_s(x)=(g^{H_2(x)})^s$$

Intuitively it is in ROM, but can somebody prove it?

$\endgroup$
  • $\begingroup$ I assume H is public, then if logarithm is easy to compute, it is not PRF. This is because one can pick $x$ and compute $H(x)$, then given $f_s(x)$, find $s$. After having $s$, $f_s(x)$ can be easily distinguished from a random string. $\endgroup$ – Changyu Dong Jun 23 '18 at 7:38
  • $\begingroup$ @ChangyuDong I should say assuming discrete log is hard. $\endgroup$ – qweruiop Jun 23 '18 at 7:40
  • 2
    $\begingroup$ There are still problems e.g. $H(x)$ may not be a generator of the group, what is the distribution of $s$. I think you need to define the problem more formally. $\endgroup$ – Changyu Dong Jun 23 '18 at 7:48
  • $\begingroup$ @ChangyuDong added more details. $\endgroup$ – qweruiop Jun 25 '18 at 17:40
  • $\begingroup$ If you assume $H_1$ and $H_2$ are random oracles and $s$ is chosen uniformly random from $Z_Q$, then yes $f_s(x)$ is pseudorandom. $\endgroup$ – Changyu Dong Jun 26 '18 at 9:25
2
$\begingroup$

The first construction is a well-known PRF in the random oracle model, with security from DDH. I can't find a good reference right now where this construction is explicitly framed as a PRF, but I will update if I find it.

Edit: this is the PRF that is implicit in private set intersection protocols dating back to:

Catherine Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy. 1986

Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing Privacy and Trust in Electronic Communities. In ACM Conference on Electronic Commerce. 1999

The second construction is insecure. If I know $f_s(x)$, then I can raise this value to the $H_2(y)/H_2(x)$ power (inversion is mod $Q$) and this tells me $f_s(y)$. So I can easily distinguish $f_s(y)$ from random.

BTW, in the random oracle model, $f_s(x) = H(s,x)$ is a PRF, as is $f_s(x) = g^{H(s,x)}$.

$\endgroup$
0
$\begingroup$

I think, under DDH one can prove this to be a weaker form of PRF. If one considers $H_1$ to be a composition of two hash functions $H_1'$ and $H_1''$ with appropriate domain and range, then one can prove the construction to be PRF under DDH if both $H_1$' and $H_1''$ are modeled as RO. I am not sure if the construction verbatim gives a PRF.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.