Alice has $p_a,q_a$ and Bob has $p_b,q_b$, all elements of a ring $R$. They want to obtain shares of the value $pq$ where $p=p_a+p_b$, $q=q_a+q_b$. How do they do this ? Does revealing their shares of $pq$ leaks their shares of $p,q$? I am supposing that in the ring $R$, it is hard to deduce $p$ and $q$ from $pq$.


1 Answer 1


This cannot be achieved information-theoretically. This is typically the task that requires multiparty computation protocol to be achieved. In particular, the common method for what you want is called "secure multiplication protocol", and is in general constructed from an additively homomorphic encryption scheme (over the ring $R$), or from oblivious transfer.

Exemple with the encryption scheme: Alice holds $p_a,q_a$; Bob holds $p_b,q_b$. Alice picks an encryption scheme $E()$ and sends the public key to Bob. She keeps the secret key. Then, she sends $E(p_a), E(q_a)$ to Bob, who computes (using the homomorphic properties of the scheme $E()$) and sends back $E(p_aq_b + r_1), E(p_bq_a+r_2)$, where $r_1$ and $r_2$ are fresh random coin. Alice decrypts these values and get $(u_1,u_2)$. She computes $n_a = u_1 + u_2 + p_aq_a$; Bob computes $n_b = -(r_1 + r_2) + p_bq_b$. You can see that $n_a + n_b = (p_a+p_b)(q_a+q_b) = pq$; the fact that this does not reveal $p$ nor $q$ can be proven assuming the encryption scheme is IND-CPA secure (id est indistinguishable against chosen plaintext attacks).

To answer your second question, if $pq$ is hard to factor, then even knowing it, it is computationally infeasible to recover the shares of $p$ and $q$ of the opponent - however, it does obviously not leak "nothing" in an information theoretical sense.


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.