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 an OPRF is cooperatively calculated by two parties.

Specifically, an OPRF is any function with the following properties:

• The parties compute: O = OPRF(I, S)
• The first-party (the client), knows the input (I) and learns the output (O) but does not learn the secret (S)
• The second-party (the server), 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. This party learns no new information from participating in the calculation of the result.

However, because it is only the second-party that holds the secret, the first-party must involve the second-party to calculate the output of the Pseudorandom Function (PRF).

This requirement enables the second-party to implement access controls, throttling, and or other security measures.

Implementations

There are various mathematical functions that can serve as the basis to implement an OPRF.

For example, methods from asymmetric cryptography, including Elliptic Curve point multiplication, Diffie-Hellman modular exponentiation over a prime, or an RSA signature calculation.

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), must cryptographically blind the input prior sending it to the second-party.

This blinding can be viewed as a form of encryption that survives the computation performed by the second-party. Therefore the first-party can decrypt what it receives from the second-party to "unblind" it, and thereby receive the same result it would have received had the input not been blinded.

When the second-party receives the blinded input, it performs a computation on it 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, (or an intermediate result which is then used by the client to compute the output of the OPRF, for example, by hashing this intermediate result).

Sample OPRF Protocol

The following is pseudo code for the calculations performed by the client and server using an Elliptic Curve based OPRF.

Client-side calculation

The following code represents calculations performed by the client, or the first-party.

byte[] computeOPRF(byte[] input) {

    // Apply point-hashing algorithm 
    // For example, as described in RFC 9380
    ECPoint hashedPoint = hashToPoint(input);

    // Generate a random blinding factor
    Scalar b = randomScalar(); 

    // Blind the input via a curve multiply 
    ECPoint blindedInput = ECMultiply(input, b);

    // Send request to server to obtain response 
    ECPoint serverResponse = sendRequest(blindedInput);
 
   // Compute multiplicative inverse of b
   Scalar inverse = modInverse(b); 
   
   // Unblind the response to produce the result 
   ECPoint result = ECMultiply(serverResponse, i);

   // Hash the unblinded result to complete OPRF calculation 
   return hash(result);

Notes:

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 OPRF, the client performs a one-way hash on the result to ensure the OPRF output is uniform, completely pseudorandom, and non-invertible.

Server-side calculation

The following code represents calculations performed by the server, or the second-party.

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:

ECPoint processRequest(ECPoint blindedInput, Scalar secret) {
    // Apply secret to compute the response 
    ECPoint response = ECMultiply(blindedInput, secret);
    return response;
}

It then returns the response, which is the blinded output, to the client.

Notes:

Because the elliptic curve point multiplication is computationally difficult to invert (like the discrete logarithm problem, the client cannot feasibly learn the server's secret from the response it produces.

Note, however, that this function is vulnerable to attacks by quantum computers. A client or third party in possession of a quantum computer could solve for the server's secret knowing the result it produced for a given input.

RSA Blind Signatures

When the output of a blind signature scheme is deterministic, it 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 useful applications in cryptography and information security.

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

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

Password-Authenticated Key Derivation

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

However, this threat can be mitigated by using the output of an OPRF that takes the password as input.

If the secret key used in the OPRF is high-entropy, then the output of the OPRF will also be high-entropy. This thereby solves the problem of the password being low-entropy, and therefore vulnerabile to cracking via brute force.

This technique is called Password-Hardening.^[1]

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

Password-Authenticated Key Exchange

For protocols such as TLS, a password can be used as the basis of a key agreement protocol, to establish temporary session keys or and mutually authenticate the client and server. 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 PAKE authentication. If the server is compromised, this exposes the user's password which 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 use the OPRF to derive the correct key.

An example of an augmented PAKE that uses an OPRF in this way is OPAQUE.^[2][3][4][5]

An Improved 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 passwords produced from it.

An OPRF is used by the Password Monitor in Microsoft Edge^[6].

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 system to issue cryptographic keys to authenticated and authorized users, without ever seeing, learning, or being in a position to learn, any of the keys it provides to users^[7].

Threshold Implementations

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

This can be done by having each server be a shareholder in a secret sharing scheme. Instead of using it's secret to compute the result, each server uses it's share of the secret to perform the computation.

The client then takes some subset of the server's computed results, and combines them, for example by computing a protocol known as interpolation in the exponent. This recovers the same result as had the client interacted with a single server which has the full secret.

This algorithm is used in various distributed cryptographic protocols.^[8]

References

1. Ford, W.; Kaliski, B. S. (2000). "Server-assisted generation of a strong secret from a password". Proceedings IEEE 9th International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET ICE 2000): 176–180. doi:10.1109/ENABL.2000.883724. ISBN 0-7695-0798-0. S2CID 1977743.
2. Krawczyk, Hugo; Lewi, Kevin; Wood, Christopher (5 February 2021). "The OPAQUE Asymmetric PAKE Protocol (Draft)". Internet Engineering Task Force.
3. Tatiana Bradley (2020-12-08). "OPAQUE: The Best Passwords Never Leave your Device". The Cloudflare Blog.
4. Bourdrez, Daniel; Krawczyk, Hugo; Lewi, Kevin; Wood, Christopher A. (2022-07-06). "The OPAQUE Asymmetric PAKE Protocol (Internet Draft)". IETF.
5. Matthew Green. "Let’s talk about PAKE". 2018.
6. Lauter, Kristin; Kannepalli, Sreekanth; Laine, Kim; Cruz Moreno, Radames (January 1, 2021). "Password Monitor: Safeguarding passwords in Microsoft Edge". Microsoft Research Blog. Retrieved January 1, 2021.
7. Jarecki, Stanislaw; Krawczyk, Hugo; Resch, Jason (2019). "Updatable Oblivious Key Management for Storage Systems". Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. Vol. November 2019. pp. 379–393. doi:10.1145/3319535.3363196. ISBN 978-1-4503-6747-9. Retrieved Jan 27, 2024.
8. Cachin, Christian; Krawczyk, Hugo; Rabin, Tal; Stathakopoulou, Chrysoula; Resch, Jason (14 March 2019). "Platform for Robust Threshold Cryptography". NIST Computer Security Resource Center. NIST.gov. Retrieved 27 January 2024.