Oblivious pseudorandom function

Overview

An Oblivious Pseudorandom Function (OPRF) are a family of cryptographic functions, similar to keyed-hash functions, but with the distinction that these are cooperatively calculated by two parties.

An OPRF is any function with the following properties:

• The parties compute: O = OPRF(I, S)
• The first party (Alice), knows the input (I) and learns the output (O) but does not learn the secret (S)
• The second party (Bob), knows the secret (S), but does not learn either the input (I), nor the output (O).

The function is called an Oblivious Pseudorandom Function, because the second party is oblivious to the function's output. It learns no new information from participating in the calculation of the result.

But because the second party holds the secret, the first party must involve the second party to calculate the output of the Pseudorandom Function (PRF). This enables the second party to implement access controls, or throttling, or other security measures.

Implementations

OPRF's can be implemented over asymmetric cryptography, such as Elliptic Curves, Diffie-Hellman prime order groups, or RSA.

EC and Conventional Diffie-Hellman

Elliptic Curves and prime order fields can be used to implement an OPRF. The essential idea is that the first party (the client), first cryptographically blinds the input prior sending it to the second party.

The second party then performs a computation on this blinded input using a secret. The result of this computation must not reveal the secret. For example, the second party may perform a point multiplication of a point on an elliptic curve. Or it may perform a modular exponentiation modulo a large prime.

The first party, upon receipt of the result, and with knowledge of the blinding-factor, computes a function that removes the blinding factor's influence on the result returned by the second party. This 'unblinds' the result, revealing the output of the OPRF.

Client-side calculation: step 1

The client first blinds its input with a random blinding factor. It must remember this blinding factor until it performs the unblinding operation.

BlindInput(ECPoint input) {
  Scalar b = randomScalar(); // a random blinding factor
  blinded_input = ECMultiply(input, b); // Curve multiply
  return (b, blinded_input);
}

The client then sends blinded_input to the server.

Server-side calculation: step 2

The server receives the blinded_input value from the client, and may perform authentication, access control, request throttling, or other security measures before processing the request. It then uses it's own secret, to compute:

ComputeBlindedOutput(ECPoint blinded_input, Scalar secret) {
  blinded_output = ECMultiply(blinded_input, secret);
  return blinded_output;
}

It then returns the blinded_output to the client.

Client-side calculation: step 3

The client receives the blinded output from the server, and now must unblind it using the same original blinding factor it used to create the request in step 1:

ComputeResult(ECPoint blinded_output, Scalar b) {
  Scalar i = modInverse(b); // Compute multiplicative inverse modulo the order of the group
  output = ECMultiply(blinded_output, i);
  return hash(output);
}

The client computes the multiplicative inverse of the blinding factor. This enables it to reverse the affect of the blinding factor on the result, and obtain the result the server would have returned had the client not blinded the input.

As a final step, to complete the PRF, the client performs a one-way hash on the output to ensure the output is uniform, completely pseudorandom, and non-invertible.

RSA Blind Signatures

When the output of a blind signature scheme is deterministic, they can be used as the basis of building an OPRF, e.g. simply by hashing the resulting signature.

This is because due to the blinding, the party computing the blind signature learns neither the input (what is being signed) nor the output (the resulting digital signature).

Applications

OPRFs have many applications in cryptography and information security.

These include in password-based key derivation and key agreement, password-hardening, password management, and homomorphic key management.

An OPRF can be viewed as a special class, and highly efficient form of homomorphic encryption, as it enables a third party to compute a function over an encrypted input and produce a result (which remains encrypted) and thereby learns nothing about what it computed.

Password-Authenticated Key Derivation

Most forms of password-based key derivation suffer from the fact that passwords typically contain a small amount of randomness (or entropy) compare to full-length 128- or 256-bit encryption key. This makes keys derived from passwords vulnerable to brute-force attacks.

However, this threat can be mitigated by using an OPRF with the password as input. If the server's secret key is high-entropy, then the output of the OPRF will also be high-entropy, and thus eliminate the vulnerability of the password to cracking via brute force.

This technique is called Password-Hardening.

Further, since each attempt at guessing a password that is hardened in this way requires interaction with a server, it prevents an offline attack. It enables the user or system administrator to be alerted to any password-cracking attempt.

Password-Authenticated Key Agreement

For protocols such as TLS, a password can be used as the basis of key agreement is used to establish temporary session keys or to authenticate the client. In the TLS protocol, this system is called a Password-Authenticated Key Exchange or PAKE.

But in its most basic implementations, the server learns the user's password during the course of the authentication. If the server is compromised, this exposure can compromise the security of the user.

To overcome this, various 'augmented forms' of PAKE incorporate an Oblivious Pseudorandom Function so that the server never sees the user's password during the authentication, but nevertheless it is able to authenticate the client is in possession of the correct password. This is done by assuming only the client that knows the correct password, can properly use the OPRF to derive the right key.

An example of an augmented PAKE that uses an OPRF in this way is OPAQUE.

A More-secure Password Manager

A password manager is software or a service that holds potentially many different passwords on behalf of the a single user.

Access to the password manager, is thus highly sensitive. If it is a service, and that service is attacked, it could expose many of that user's passwords to the attacker.

By using an OPRF, however, passwords for an individual site can be derived from a single master password, without the service being in a position to learn either the user's master password, nor any of the derived passowrds used for individual sites.

An OPRF is used by the Password Monitor in Microsoft Edge.

Homomorphic Key Management System

Similarly to securing passwords managed by a password manager, an OPRF can be used to enhance the security of a key management system.

For example, an OPRF enables a key-management server to issue cryptographic keys to authenticated and authorized users, without ever seeing or learning being in a position to learn any of the keys it issues to users.

Threshold Implementations

For even greater security, it is possible to thresholdize the server, such that the secret (S) is not held by any individual service, and so the compromise of any single server, or set of servers below some threshold, will not expose the secret.

This can be done by having each server be a shareholder in a secret sharing scheme, and then compute a protocol known as interpolation in the exponent. This algorithm is used in various distributed cryptographic protocols.