Oblivious pseudorandom function
An oblivious pseudorandom function (OPRF) is a PRF together with a two-party protocol in which a server holding a key and a client holding an input securely compute the functionality : the client learns and nothing else, and the server learns nothing — FIPR05.
Syntax
An OPRF is a pair of a PRF with key space , domain and range , and a two-party protocol :
- , a randomized algorithm generating public parameters, with in the plain model,
- (the server, or sender) and (the client, or receiver) are stateful interactive algorithms with:
- input: a key ,
- input: ,
- output: ,
- output: .
We write and for the functionality. The server samples its key as ; the definitions below quantify over every .
Properties
Correctness
An OPRF is -correct if for all , and ,
where and . When , is perfectly correct.
Pseudorandomness
is pseudorandom: is negligible for all efficient .
Semi-honest security
The corrupted party is fixed in advance, and the adversary chooses both inputs after seeing the reference string. In world it receives ‘s view of a real execution together with the honest party’s output; in world it receives the simulator’s output on ‘s input and output together with the honest party’s output in an ideal execution of . In world the simulator also produces the reference string, as in semi-honest MPC; in the plain model this is immaterial.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sh}}_{\Pi,\PRF,P,\Sim,\calA}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$; $\pp_0 \gets \Setup(1^\secpar)$; $\pp_1 \gets \Sim(1^\secpar)$
\Comment{$P \in \{S, R\}$ is the corrupted party; $\Sim$ is stateful}
\State $(k, x, \stA) \gets \calA(1^\secpar, \pp_b)$
\State Run $\langle S(\pp_0, k), R(\pp_0, x) \rangle$; let $y$ be $R$'s output and $\View_P$ be $P$'s view
\State $y^* := \Eval(k, x)$
\If{$P = S$}
\State $\mathit{out}_0 := (\View_S, y)$; $\mathit{out}_1 := (\Sim(k), y^*)$
\Else
\State $\mathit{out}_0 := \View_R$; $\mathit{out}_1 := \Sim(x, y^*)$
\EndIf
\State $b' \gets \calA(\stA, \mathit{out}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
An OPRF is semi-honest secure if is pseudorandom and for each there is an efficient such that for all efficient ,
is negligible. Up to pseudorandomness of , this is semi-honest two-party computation of .
Malicious security
An OPRF has malicious security if is pseudorandom and securely computes with abort against corruptions, in the sense of security with abort for (2PC): for all efficient corrupting one of the two parties and deviating arbitrarily there is an efficient such that for all efficient , is negligible. In the ideal execution a corrupted server hands the trusted party a key of the simulator’s choice and may then make the client output , and a corrupted client hands it an input of the simulator’s choice and receives .
Variations
OPRF with a group range
An OPRF with a group range is a semi-honest secure OPRF whose domain contains two distinct efficiently computable points and whose range is a finite group with and efficiently computable operation and inverse.
OPRF with super-polynomial range
An OPRF with super-polynomial range is a semi-honest secure, -correct OPRF whose domain contains for a polynomial , whose range has negligible, and for which the maximum over distinct of is negligible. Pseudorandomness against non-uniform adversaries implies the last condition: the circuit with a pair hard-wired queries both points and outputs whether the answers agree, so the probability for that pair is at most plus its advantage — folklore.
Verifiable OPRF
A verifiable OPRF (V-OPRF) is an OPRF whose protocol UC-realizes the V-OPRF ideal functionality of JKK14. Informally, the server publishes a value that binds its key, and the client outputs either the function value under the bound key or , so a malicious server cannot evaluate different inputs under different keys. JKK14 give realizations of the functionality in the random-oracle model and instantiations in the standard model, and build one from the 2HashDH function below, the server publishing and proving in zero knowledge that its reply is computed with the same exponent.
UC-secure OPRF
A UC-secure OPRF UC-realizes an OPRF functionality whose function is a random function sampled by the functionality, not a fixed PRF; this functionality is more general than the V-OPRF functionality of JKK14 — JKKX16. For a group of prime order with generator and hash functions and for an output length , the 2HashDH function is
The client sends for , the server replies , and the client outputs . With and modeled as random oracles, this protocol UC-realizes the OPRF functionality under the one-more gap Diffie–Hellman assumption: for all efficient given , a list of uniform elements of , an oracle and a DDH oracle, the probability that outputs for more elements of the list than it made queries to is negligible — JKKX16.
Partially oblivious PRF
A partially oblivious PRF is a pair of a PRF with domain and a two-party protocol , with server input , client input , server output and client output , that securely computes against semi-honest adversaries: the server learns and nothing about . Compared with the semi-honest game above, a corrupted server’s simulator also receives , and a corrupted client’s view is paired with the honest server’s output.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{po}}_{\Pi,\PRF,P,\Sim,\calA}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$; $\pp_0 \gets \Setup(1^\secpar)$; $\pp_1 \gets \Sim(1^\secpar)$
\Comment{$P \in \{S, R\}$ is the corrupted party; $\Sim$ is stateful}
\State $(k, (t, x), \stA) \gets \calA(1^\secpar, \pp_b)$
\State Run $\langle S(\pp_0, k), R(\pp_0, (t, x)) \rangle$; let $s$ and $y$ be the outputs of $S$ and $R$ and $\View_P$ be $P$'s view
\State $y^* := \Eval(k, (t, x))$
\If{$P = S$}
\State $\mathit{out}_0 := (\View_S, y)$; $\mathit{out}_1 := (\Sim(k, t), y^*)$
\Else
\State $\mathit{out}_0 := (\View_R, s)$; $\mathit{out}_1 := (\Sim((t, x), y^*), t)$
\EndIf
\State $b' \gets \calA(\stA, \mathit{out}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
Formally, is a partially oblivious PRF if is pseudorandom and for each there is an efficient such that for all efficient ,
is negligible. ECSJR15 introduce verifiable partially oblivious PRFs and build one, from bilinear pairings and zero-knowledge proofs, that supports bulk rotation of previously obtained outputs to a new key.
Other results
- Given a PRF with and for polynomials and , with equality for malicious security, a protocol securely computing is an OPRF: semi-honest 2PC gives a semi-honest secure OPRF (semi-honest 2PC + PRF ⇒ OPRF) and 2PC with abort an OPRF with malicious security (2PC + PRF ⇒ malicious OPRF) — folklore.
- A semi-honest secure OPRF with a group range gives semi-honest OT: the sender masks and with and , and the receiver obtains the mask of from the OPRF on input (OPRF ⇒ OT) — folklore.
- FIPR05 base their general protocols for keyword search, in which a client retrieves the database records associated with a keyword and privacy is required for both the client and the server, on OPRFs.
- FIPR05 evaluate the Naor–Reingold PRF (DDH ⇒ PRF) obliviously with one 1-out-of-2 OT per input bit. For the key and input , the server samples , the client obtains from the -th OT with choice bit , the server sends , and the client raises it to , obtaining .
- JL09 give an OPRF for the Dodis–Yampolskiy PRF (DY05) and apply it to adaptive oblivious transfer and to secure computation of set intersection.
- JKX18 build strong asymmetric PAKE from a UC-secure OPRF together with either any asymmetric PAKE or any authenticated key-exchange protocol secure against key-compromise impersonation; OPAQUE instantiates the second construction.
Participates in
Builds on Oblivious pseudorandom function
- OPRF with a group range ⇒ OPRF (via OPRF with a group range)
- OPRF ⇒ OT (via OPRF with a group range)
- OPRF ⇒ PSI (via OPRF with super-polynomial range)
- OPRF with super-polynomial range ⇒ OPRF (via OPRF with super-polynomial range)
Produces Oblivious pseudorandom function