It should be a secure two party protocol against a malicious adversary.

$P_1$'s input is $X$ in $Z_p^*$ (p is a prime number); $P_2$'s input is nothing. $P_1$'s output is $r_X+r'$, where $r$,$r'$ are random numbers from $Z_p^*$ $P_2$' output is $r$ and $r'$.

Is there any efficient protocol to realize this functionality other than by using homomorphic encryption? If only HE solves this problem, which is the most efficient one?

Thanks for help!

  • 1
    $\begingroup$ This is a well-known problem called Oblivious Linear function Evaluation (OLE). $\endgroup$
    – Mikero
    Sep 26, 2021 at 20:38
  • $\begingroup$ Thanks for help! $\endgroup$ Sep 27, 2021 at 1:50

2 Answers 2


This functionality can be instantiated using OLE (oblivious linear function evaluation). In a standard OLE, Alice gets (r, r'), Bob gets (x, y=rx+r'), where Alice picks r and Bob picks x. But if you want r to be random then you can just sample it from the uniform distribution.

OLE can be implemented very efficiently using lattices or OT. Here is one example: https://eprint.iacr.org/2020/970


You can do this with any additive/logarithmically homomorphic scheme with $p$ dividing the order of the plaintext group. The Okamoto-Uchiyama system has plaintext space size exactly $p$ and may be suitable if you have no quantum resistance required.

The protocol is as follows:

P1 creates a public key for the scheme as well as encryptions of $X$ and 1, say $c_0=E(X)$ and $c_1=E(1)$. These are passed to P2.

Assuming a log-homomorphic scheme, P2 chooses random $r$ and $r’$, computes $c_2:=c_0^rc_1^{r’}=E(rX+r’)$ and sends this value to P1.

P1 decrypts $c_2$ to recover $rX+r’$.

  • $\begingroup$ thank you! how about its efficiency compared with the Paillier scheme? I want an efficient one because I want it be secure against malicious adversary. Do you know any method other than HE? $\endgroup$ Sep 26, 2021 at 8:29
  • $\begingroup$ And I also want a random r and r', but in your scheme, r and r' are decided by P2 which could be malicious. $\endgroup$ Sep 26, 2021 at 8:33
  • $\begingroup$ O-U is similar in efficiency to Paillier, and often more efficient for the same level of security. I don’t know of any non-HE solution. $\endgroup$
    – Daniel S
    Sep 26, 2021 at 8:41
  • $\begingroup$ To defend against malicious P2, P1 can choose random $s1$ and $s2$ and form $(r+s1)X+(r’+s2)$. Sending $s1$ and $s2$ to P2 allows them to form $r+s1$ and $r’+s2$ $\endgroup$
    – Daniel S
    Sep 26, 2021 at 8:45
  • $\begingroup$ Thanks! I will study O-U scheme. But i thinks to make it secure, some additonal ZKP may have to be added; things like proving the public parameter is rightly generated etc. $\endgroup$ Sep 26, 2021 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.