ODIS currently provides a rate-limited PRF service with the primary use case of supporting rate-limited discovery of Celo addresses from a user's phone number. In order to support secure password hardening and future use cases, granular rate limits are invaluable. Applying rate limits on a per-user basis (e.g. restricting the number of guesses on a user's password to a constant number) ODIS's OPRF scheme must be extended to support domain separation between users in a way that that is visible to the service to inform rate limiting rules. In ia.cr/2018/733, a construction that satisfies this need is described as a partially oblivious pseudo-random function (POPRF)
ODIS currently exists as a decentralized verifiable OPRF service based on blind threshold BLS signatures. Building upon this foundation, we aim to create a decentralized and verifiable POPRF service. Doing so enables users to apply the core primitive of ODIS, a rate limited PRF service, to new applications with the same trust assumptions rooted in the collective honesty of the ODIS operators.
In order to extend ODIS to support POPRF computation, with the primary use case of password hardening, we aim to create a POPRF construction with a combination of properties not natively available to any proposed scheme published to date. In particular, the POPRF should be:
Supporting thresholdization, as compared to relying on a single party to compute the POPRF function, supports the decentralized trust model required for many applications of ODIS as a public service supporting Celo. It must be the case that no single party can unilaterally compute the POPRF function, thereby breaking rate limiting, or censor requests from an honest client. ODIS currently does not require interaction between the operators, relying instead only on communication between each operator and the client. This is a desirable property as it greatly simplifies service operation, performance, and reliability.
Supporting verifiability against a pre-shared key (e.g. packaged with the binary) allows clients ensure that no bad actor among the decentralized operators can corrupt the output of the POPRF without being detected. This is as opposed to the verifiability of the (P)OPRF construction used in OPAQUE, where it is verifiable but uses client-specific keys which then requires client state and disallows verification of the first interaction with the service.
Threshold Partially-Oblivious PRFs with Applications to Key Management
OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-Computation Attacks
A Fast and Simple Partially Oblivious PRF, with Applications
Proposed below is an adaptation of the Pythia construction to achieve the threshold computation and verifiability properties described above. It includes a threshold computation method not present in the original work, as well as an interactive verification protocol inspired ia.cr/2018/733.
We start by describing the POPRF protocol as computed by a single party.
As global parameters, the protocol uses three groups $\mathbb{G}_1$, $\mathbb{G}_2$, and $\mathbb{G}_T$ of prime order $p$ with an efficiently computable asymmetric pairing $e: \mathbb{G}_1\times\mathbb{G}_2\to\mathbb{G}_T$. Generators for these groups are respectively written as $g_1$, $g_2$, and $g_T$. In practice this is provided by BLS12-377.