# Is there a secure two party protocol that makes P1 (with x as input) gets rx+r' and P2 gets (r,r')

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

P1's input is X in Zp* (p is a prime number); P2's input is nothing. P1's output is rX+r'. r,r' are random numbers from Zp* P2' output is r and r'.

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

Thanks for help!

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

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’$$.

• 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? Sep 26, 2021 at 8:29
• And I also want a random r and r', but in your scheme, r and r' are decided by P2 which could be malicious. Sep 26, 2021 at 8:33
• 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. Sep 26, 2021 at 8:41
• 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$ Sep 26, 2021 at 8:45
• 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. Sep 26, 2021 at 8:54