2
$\begingroup$

Define three hash functions:

  1. $H_1: \{0, 1\}^* \rightarrow \mathbb{G}$ mapping $x$ to the group $\mathbb{G}$ of prime order $q$
  2. $H_2: \mathbb{G} \rightarrow \{0, 1\}^\tau$
  3. $H_3: \{0, 1\}^* \times \mathbb{G} \rightarrow \{0, 1\}^\tau$

Under random oracle model and DDH assumption, I noticed the PRF $H_2(H_1(x)^k)$ defined in this paper where $k$ is the PRF key. Besides, I also saw other PRF variants such as $H_3(x, H_1(x)^k)$ in PAKE papers and $H_1(x)^k$ in Private Set Intersection papers(also see in a related previous question).

I have the following questions:

  1. Is there any formal proof that they are PRFs?
  2. If they are all PRFs in the random oracle model under DDH assumption, what are the differences between the three constructions, in particular between $H_2(H_1(x)^k)$ and $H_3(x, H_1(x)^k)$?
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think this needs a little more context to be answerable. For example, what is $H_2$? $\endgroup$
    – Guut Boy
    Mar 5, 2021 at 8:00
  • $\begingroup$ @Guut Boy thanks, have revised accordingly. $\endgroup$
    – D.V.
    Mar 5, 2021 at 8:42

1 Answer 1

Reset to default
1
$\begingroup$

Is there any formal proof that they are PRFs?

In these applications (PSI, PAKE), it's usually not necessary to prove standalone PRF security. Sometimes you can get a secure PSI for example from something that is slightly weaker than a PRF (e.g., a PRF for bounded # of queries).

In this case, the constructions are standalone PRFs, and the proof would follow the same logic as the PSI/PAKE security proofs. I can give an idea of the proof for $H(x)^k$ (in prime-order cyclic groups):

  • Consider a reduction algorithm $R$ that takes as input a triple of group elements $(K,A,B)$ and does the following: $R$ internally runs a PRF adversary and plays the role of the random oracle $H$ and the construction $F(k,x) = H(x)^k$. Whenever $A$ queries $H(x)$, respond with $A^{r_x}$; whenever $A$ queries $F(x)$, respond with $B^{r_x}$. Here $r_x$ is uniform for each distinct $x$.

  • If $(K=g^k, A=g^a, B=g^{ak})$ then $B^{r_x} = (g^{ak})^{r_x} = ((g^a)^{r_x})^k = H(x)^k$ so the PRF adversary is seeing true outputs of the PRF.

  • If $B$ is uniform in $(K,A, B)$, then each $B^{r_x}$ is uniform, so the PRF adversary is seeing random outputs from its PRF oracle.

  • The two cases of $R$'s inputs $(K,A,B)$ are indistinguishable by the DDH assumption, this shows that the PRF construction is secure.

If they are all PRFs in the random oracle model under DDH assumption, what are the differences between the three constructions?

PSI/PAKE applications are interactive protocols. When we need security against malicious adversaries, there must be a simulator that watches what the adversary does and "explains" it (extracting an input to send to the ideal PSI/PAKE functionality on behalf of the adversary). In the random oracle model, the simulator gets to also observe all of the adversary's queries to the random oracle.

So the reason to use something like $H(x,stuff)$ instead of $H(stuff)$ in such a protocol is to help the simulator extract. If $x$ is right there (as an input to the random oracle) then the simulator's job is much easier. This is a standard trick in malicious-secure PSI (in the random oracle model).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you, your answer really helps. I guess another consideration on $H_2$ $H_3$ is that in PAKE they want to obtain a bit-string rather than a group element, e.g., $H_2$ $H_3$ can be Key Derivation Functions for deriving the session key. In PSI, we have no need to do that since we only want to match elements. Towards malicious security, can the simulator extract $x$ from $H_1(x)$ if $H_1$ is modeled as a random oracle? $\endgroup$
    – D.V.
    Mar 6, 2021 at 2:49
  • 1
    $\begingroup$ Yes, the simulator can "recognize" $x$ from $H_1(x)$ in the random oracle model. But in PSI/PAKE you often have things like $H_1(x)^r$. If $r$ is random then this value perfectly hides $x$ even from the simulator. $\endgroup$
    – Mikero
    Mar 6, 2021 at 17:09

Your Answer

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

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