2
$\begingroup$

I heard shared input. For example, original values $x,y \in M$ are divided into pairs of shares $(x_1,x_2)$ and $(y_1, y_2)$ such that $x_1 + x_2 = x \text{ and } y_1 + y_2 = y$. Each share is distributed to two parties $P_1$ (who obtains $x_1$ and $y_1$) and $P_2$ (who obtains $x_2$ and $y_2$).

When $M = \mathbb{Z}_2$, addition is just XOR computation.

With additive shared input, can any computations be evaluated??

If so, what is the method used for the evaluation??

Is garbled circuit applicable to this scenario??

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

With additive shared input, can any computations be evaluated??

If so, what is the method used for the evaluation??

Is garbled circuit applicable to this scenario??

Yes, any computation can be evaluated. This is achieved by representing the functionality to be computed as an arithmetic circuit (not a garbled circuit) that consists of addition and multiplication gates. The addition gate can be evaluated by the parties locally because the shares are additively homomorphic. The multiplication gates can be evaluated by the parties interactively.

If you want to know more about it, there is a book: Secure Multiparty Computation and Secret Sharing, by Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen.

There are also some relevant papers if you are interested:

Ronald Cramer, Ivan Damgård, Ueli M. Maurer: General Secure Multi-party Computation from any Linear Secret-Sharing Scheme. EUROCRYPT 2000: 316-334

Dan Bogdanov, Sven Laur, Jan Willemson: Sharemind: A Framework for Fast Privacy-Preserving Computations. ESORICS 2008: 192-206

Ivan Damgård, Valerio Pastro, Nigel P. Smart, Sarah Zakarias: Multiparty Computation from Somewhat Homomorphic Encryption. CRYPTO 2012: 643-662

Improve this answer
$\endgroup$
4
  • $\begingroup$ Any functional differences between Shamir-Secret Sharing and additive secret sharing? $\endgroup$
    – mallea
    Sep 4, 2018 at 8:29
  • $\begingroup$ Shamir-secret sharing is an additively homomorphic secret sharing, meaning that if secrets $a$, $b$ are shared into shares $a_1,...,a_n$, $b_1,b_n$, then you can obtain shares $c_1=a_1+b_1,..., c_n=a_n+b_n$ such that $c_1,...,c_n$ are the shares of value $c=a+b$. It can also be used in MPC to compute any function. $\endgroup$
    – Changyu Dong
    Sep 4, 2018 at 8:38
  • $\begingroup$ I'm sorry that my question was really stupid. So, for example, SPDZ does not use Shamir Secret Sharing. Are you aware of when and when not to use a particular secret sharing scheme? $\endgroup$
    – mallea
    Sep 4, 2018 at 15:01
  • $\begingroup$ It is up to you to select, depending on your requirement. For example, Shamir secret sharing offers t out of n threshold reconstruction, meaning that any $t$ shares allows to recover the secret. So you can tolerate up to $n-t$ share loss and still do the computation/get the result. While the simple mod addition based secret sharing requires all $n$ shares to recover the secret. On the other hand, it's more efficient in computation than Shamir usually. $\endgroup$
    – Changyu Dong
    Sep 4, 2018 at 16:20

Your Answer

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

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