An oblivious pseudorandom function (OPRF) is a cryptographic function, similar to a keyed-hash function, but with the distinction that in an OPRF two parties cooperate to securely compute a pseudorandom function (PRF).
Definition Specifically, an OPRF is a pseudorandom 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 has the same security properties as any (cryptographically secure) pseudorandom function. Specifically it shall be hard to distinguish the output from true randomness. 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, audit logging and other security measures.
History While conventional pseudorandom functions computed by a single party were first formalized in 1986, it was not until 1997 that the first two-party oblivious pseudorandom function was described in the literature, but the term "oblivious pseudorandom function" was not coined until 2005 by some of the same authors.
Applications OPRFs have many useful applications in cryptography and information security. These include password-based key derivation, password-based key agreement, password-hardening, untraceable CAPTCHAs, password management, homomorphic key management, and private set intersection. 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 therefore it learns nothing about what it computed.
Password-based 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 vulnerable to cracking via brute force. This technique is called password hardening. It fills a similar purpose as key stretching, but password hardening adds significantly more entropy. 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. The recovered key may then be used for authentication (e.g. performing a PKI-based authentication using a digital certificate and private key), or may be used to decrypt sensitive content, such as an encrypted file or crypto wallet.
Password-authenticated key exchange A password can be used as the basis of a key agreement protocol, to establish temporary session keys and mutually authenticate the client and server. This is known as a password-authenticated key exchange or PAKE. In basic authentication, the server learns the user's password during the course of the authentication. If the server is compromised, this exposes the user's password which compromises the security of the user. With PAKE, however, the user's password is not sent to the server, preventing it from falling into an eavesdropper's hands. It can be seen as an authentication via a zero-knowledge password proof. 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. Recently, OPRFs have been applied to password-based key exchange to back up encrypted chat histories in WhatsApp and Facebook Messenger. A similar use case is planned to be added in Signal Messenger.
Untraceable CAPTCHAs A CAPTCHA or "Completely Automated Public Turing test to tell Computers and Humans Apart" is a mechanism to prevent automated robots or (bots) from accessing websites. Lately, mechanisms for running CAPTCHA tests have been centralized to services such as Google and CloudFlare, but this can come at the expense of user privacy. Recently, CloudFlare developed a privacy-preserving technology called "Privacy Pass". This technology is based on OPRFs, and enables the client's browser to obtain passes from CloudFlare and then present them to bypass CAPTCHA tests. Due to the fact that the CloudFlare service is oblivious to which passes were provided to which users, there is no way it can correlate users with the websites they visit. This prevents tracking of the user, and thereby preserves the user's privacy.
… excerpt ends here. Continue reading the full article.
