sgo.to

Oblivious Pseudo Random Function

Sam Goto

An oblivious pseudo random function (OPRF) is a two-party protocol between sender S and receiver R for securely computing F(x) of a pseudorandom function F in such a way that the receiver R learns the value of F(x) without the sender S learning anything from the interaction (x nor F(x)).

One way to construct an OPRF is to rely on two interesting mathematical observations as we did before.

That is:

  1. (g ^ a) ^ b = (g ^ b) ^ a
  2. given g [1] and g ^ a [2], it is really hard to compute a [3].

[1] special kinds of g, [2] a is a natural number and [3] this is known as the discrete logarithm problem

The protocol works in the following order:

  1. The Receiver starts by selecting an input x = .
  2. The Receiver computes a random number r = .
  3. The Receiver computes a hash of the input value H(x) = ,
  4. computes a = H(x) ^ r = ^ =
  5. and sends it to the Sender
  6. The Sender selects its secret key k =
  7. computes b = a ^ k = and
  8. sends it to the Receiver
  9. The Receiver computes the final result with
    b ^ (1/r) = ^(1 / ) =

This is guaranteed to compute H(x) ^ k because:

= b ^ (1/r) = (a ^ k) ^ (1 / r) = (((H(x) ^ r) ^ k) ^ (1/r)) = (((H(x) ^ k) ^ r) ^ (1/r)) = H(x) ^ k = .

There is a rounding number error here calculating 1/r.

The hashing function is kept deliberately small for readability, so there are collisions.