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?

  • 1
    $\begingroup$ Have a look at the OPRF used in OPAQUE (which essentially blinds a hash with an exponentiation, sends that to the server, who exponentiates with a secret and sends the result back which is then unblinded). $\endgroup$
    – SEJPM
    Jul 23, 2018 at 18:51
  • 1
    $\begingroup$ @SEJPM I've tried reading the related sections of the paper, It's a hard read... Would I be asking too much, if you could help by describing the OPRF in that article, I feel like a total illiterate when I read the paper. It's really hard for me to understand the notation and the idea on that paper. $\endgroup$
    – zetaprime
    Jul 23, 2018 at 22:30

1 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$.


$\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).

  • $\begingroup$ I assume the exponentiation is simply the DH exponentiation with the same modulo p. However, I couldn't really understand the function H(.,.) with two arguments. Can I simply assume it's a hash with salt, which concatates the inputs given? $\endgroup$
    – zetaprime
    Jul 24, 2018 at 23:01
  • 1
    $\begingroup$ @zetaprime yes, if you use $\mathbb Z_p$ as your group then the exponentiation is indeed standard exponentiation modulo $p$. The matter of how to instantiate $H(\cdot,\cdot)$ is a bit more complex and I'll address it later. $\endgroup$
    – SEJPM
    Jul 25, 2018 at 11:25
  • 1
    $\begingroup$ @zetaprime I have expanded my explanations in the parameters section accordingly. $\endgroup$
    – SEJPM
    Jul 25, 2018 at 14:56

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.