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?

Improve this question
$\endgroup$
6
  • $\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
    Commented Jun 23, 2018 at 7:38
  • $\begingroup$ @ChangyuDong I should say assuming discrete log is hard. $\endgroup$
    – qweruiop
    Commented Jun 23, 2018 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
    Commented Jun 23, 2018 at 7:48
  • $\begingroup$ @ChangyuDong added more details. $\endgroup$
    – qweruiop
    Commented Jun 25, 2018 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
    Commented Jun 26, 2018 at 9:25

2 Answers 2

Reset to default
3
$\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)}$.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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