# Is there a secure two party protocol that $P_1$ (with x as input) gets $rx+r'$ and $P_2$ gets $(r,r')$

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!

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

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

• 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? Commented 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. Commented 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. Commented 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$ Commented 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. Commented Sep 26, 2021 at 8:54