Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

Question

The Commutative Cipher Setup

• Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime.
• Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) = 1$. And a decryption exponent $d$ chosen such that $d * e ≡ 1\bmod (p-1)$. Alice has $(e_A, d_A)$ and Bob has $(e_B, d_B)$ as their private key pairs.

Note: I've also discovered that @fgrieu has proposed two variants of Pohlig-Hellman adressing some of the problems of modular exponentiation. Please assume the the key generation is done according to their explanation in both. variant 1, variant 2

We expect, this commutative cipher setup should be secure enough to use.

---

The Protocol

Alice has a message $m$ and wants to perform an oblivious PRF with Bob for this message.

The steps are as follows:

1. Alice seeds a PRG with $m$ and generates a 2048 (or 2047) bit random output $r$

   a. For the properties $r$ satisfies, please check the PH variant by @fgrieu

2. Alice calculates the following encrypted random sequence with modular exponentiation, $E_A(r) = r^{e_A} \bmod p$ and sends the result to Bob.

3. Bob calculates $E_B(E_A(r)) = (E_A(r))^{e_B}\bmod p = E_{A,B}(r)$ and sends the result $E_{A,B}(r)$ back to Alice

4. Finally Alice calculates $D_A(E_{A,B}(r))=(E_{A,B}(r))^{d_A}\bmod p = E_B(r)$.

This should be the same value, where Bob:

• Seeds the same PRG with the message $m$ to get $r$ (The same sequence Alice got from her PRG)
• And calculate $E_B(r) = r^{e_B}\bmod p$

I believe this protocol should be satisfying the requirements of an Oblivious PRF. I'm assuming, given a random input, we can use modular exponentiation as a PRF. Using the commutative nature of modular exponentiation, I believe we can achieve an Oblivious PRF. However I'm not sure if that's true, and I don't know how to prove this.

Once Alice and Bob have achieved an Oblivious PRF, My final goal for this OPRF is to use it for a Private Set Intersection protocol. Based on the answer of @Mikero in the question: How can Alice enable Bob to look-up values in a private map

Do you see any vulnerabilities here whether it might leak the keys of either parties or the message of Alice? Do you see any problems with my assumptions and utilization of modular exponentiation, if there are any points potentially insecure and should be avoided or fixed?

Answer 1

I believe this protocol should be satisfying the requirements of an Oblivious PRF.

This protocol is (nearly) identical to what is proven secure as an OPRF in the OPAQUE paper (Appendix A). There the OPRF is described (up to some formal notation) as follows, I'll annotate your notation in parenthesis:

---

Parameters: A multiplicatively-written Group $\mathbb G$ of order $q$ where the discrete logarithm is hard. A hash function $H(\cdot,\cdot):\{0,1\}^*\times \mathbb G\to\{0,1\}^l$. A hash function $H'(\cdot):\{0,1\}^*\to\mathbb G$.
(You call $H'$ a "PRG" and use $\mathbb Z_p$, that is the group of integers modulo $p$ with multiplication, as $\mathbb G$. This means that if it says $a^b$ below it means $a^b\bmod p$ for this group. If you need guidance on instantiating any of these hash functions, have a look at my prepared answer for this)

Setup: The Server $\mathsf{S}$ picks $k\gets_R\mathbb Z_q$, that is the server randomly picks a non-negative integer smaller than $q$.

Execution:

$\mathsf U$ wants to learn $F_k(x)$ with $F:\mathbb Z_q\times \{0,1\}^*\to\mathbb \{0,1\}^l$ without learning $k$ nor having $\mathsf S$ learn $x$.

1. $\mathsf U\to\mathsf S: H'(x)^r$, that is $\mathsf U$ picks an $r\gets_R\mathbb Z_q$, stores it and sends $H'(x)^r$. (This is step 1 and 2 of your protocol.)
2. $\mathsf S\to\mathsf U: \left(H'(x)^r\right)^k$, that is $\mathsf S$ simply exponentiates the given input with its secret value and returns the result. (This is step 3 in your protocol)
3. $\operatorname{return}\ H\left(x,\left(\left(H'(x)^r\right)^k\right)^{1/r}\right)$ That is $\mathsf U$ simply "unblinds" the received value (which is the decryption in your commutative cipher) and returns the original input and the received value through another hash function. (The last hashing step has been missing)

---

Additional notes: In OPAQUE, $x$ is the password and one can see $H'(x)^k$ as the "salt" and $H(\text{pw},s)$ as a password-based key derivation function, which gets evaluated client-side to decrypt a server-stored long-term DH key-pair. Then this key-pair with an ephemeral keypair gets used in a standard DH-based key-exchange computation (in this case HMQV).