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