Oblivious polynomial evaluation
Oblivious polynomial evaluation (OPE) is a two-party protocol in which a sender holding a polynomial over a finite field and a receiver holding securely compute the functionality : the receiver learns and nothing else about , and the sender learns nothing about — NP99.
Syntax
An OPE for a finite field , whose elements have -bit representations and whose operations are efficient, and a degree bound , a polynomial, is a two-party protocol :
- , a randomized algorithm generating public parameters, with in the plain model,
- (the sender) and (the receiver) are stateful interactive algorithms with:
- input: a polynomial of degree at most , given by its coefficients ,
- input: ,
- output: ,
- output: .
We write and for the functionality. and are public.
Properties
Correctness
An OPE is -correct if for all , all of degree at most and all ,
where and . When , is perfectly correct.
Semi-honest security
The corrupted party is fixed in advance and runs honestly, 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,C,\Sim,\calA}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$; $\pp_0 \gets \Setup(1^\secpar)$; $\pp_1 \gets \Sim(1^\secpar)$
\Comment{$C \in \{S, R\}$ is the corrupted party; $\Sim$ is stateful}
\State $(P, \alpha, \stA) \gets \calA(1^\secpar, \pp_b)$
\Comment{Admissible: $P \in \FF[z]$, $\deg P \le d$, $\alpha \in \FF$}
\State Run $\langle S(\pp_0, P), R(\pp_0, \alpha) \rangle$; let $y$ be $R$'s output and $\View_C$ be $C$'s view
\If{$C = S$}
\State $\mathit{out}_0 := (\View_S, y)$; $\mathit{out}_1 := (\Sim(P), P(\alpha))$
\Else
\State $\mathit{out}_0 := \View_R$; $\mathit{out}_1 := \Sim(\alpha, P(\alpha))$
\EndIf
\State $b' \gets \calA(\stA, \mathit{out}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
An OPE is semi-honest secure if for each there is an efficient such that for all efficient admissible ,
is negligible. This is semi-honest two-party computation of .
Malicious security
An OPE has malicious security if it 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 sender hands the trusted party a polynomial of degree at most of the simulator’s choice and may then make the receiver output , and a corrupted receiver hands it an input of the simulator’s choice and receives .
Variations
Oblivious linear evaluation
The case : the sender holds , the receiver holds and learns . It is called oblivious linear evaluation (OLE). Over , the sender pair and the receiver input give , a 1-out-of-2 OT of bits (OPE ⇒ OT) — folklore.
Other results
- The general protocol run on is a semi-honest secure OPE when it comes from semi-honest 2PC (semi-honest 2PC ⇒ OPE) and one with malicious security when it comes from 2PC (2PC ⇒ malicious OPE) — folklore. Semi-honest OT therefore gives semi-honest OPE without further assumptions (semi-honest OT ⇒ semi-honest MPC) — GMW87, Gol04.
- Semi-honest OPE with gives semi-honest OT with message space : the sender inputs and the receiver inputs its choice bit , learning (OPE ⇒ OT) — folklore.
- NP99 construct OPE from OT under a hardness assumption on noisy polynomial interpolation. The receiver hides as for a random polynomial and sends points of which some lie on the graph of and the others are random; the sender hides in a random bivariate polynomial with ; by OT the receiver learns the values of at the points on the graph of only, and interpolates the univariate polynomial at , obtaining . The assumption is that the points hide .
- Noisy polynomial interpolation asks, given distinct and sets of elements each, consisting of for a hidden polynomial of degree and random elements, to find . BN00a reduce it to the lattice shortest vector problem when the parameters satisfy a condition they make explicit, and standard lattice reduction appears to solve many instances, so the problem is easier than expected; they suggest modifying the schemes based on it so that they rest on a different intractability assumption.
- An additively homomorphic encryption scheme whose message space depends on alone, not on , and whose ciphertexts the sender can rerandomize from to fresh encryptions of the same plaintext, gives semi-honest OPE over , the functionality above with the ring in place of : the receiver sends and encryptions of , and the sender computes an encryption of homomorphically, rerandomizes it and returns it for the receiver to decrypt — folklore. IND-CPA security hides from the sender, and the returned ciphertext is a fresh encryption of . Paillier’s scheme — Pai99 — does not meet this condition: its message space depends on the modulus in , which the receiver generates during the protocol.
Participates in
Builds on Oblivious polynomial evaluation
Produces Oblivious polynomial evaluation