I would like to perform a dot product operation among $m$ parties using Shamir's $(m,m)$ secret sharing that is used for Secure Multiparty Computation.

I am aware that Shamir's $(m,m)$ scheme is additively homomorphic, but can someone please provide an example of how I can use it for multiplicative homomorphism for SMC?

  • $\begingroup$ Welcome to Crypto.SE :) Remember to sign up on this site and link your accounts to reclaim ownership of your question. $\endgroup$ – Cryptographeur Apr 4 '14 at 15:03
  • $\begingroup$ Sorry for the edit clash DrL $\endgroup$ – Cryptographeur Apr 4 '14 at 15:05
  • $\begingroup$ @figlesquidge no problem ;) $\endgroup$ – DrLecter Apr 4 '14 at 15:07
  • $\begingroup$ This might help: research.cyber.ee/~peeter/teaching/seminar07k/bogdanov.pdf $\endgroup$ – rphv Apr 4 '14 at 19:15
  • $\begingroup$ Thanks. This paper does explain multiplicative homomorphism using Shamir's scheme. However what i want to do is multiplication e.g. using 3 parties and each of them has a secret and acts as a dealer. Can someone provide an example for this. $\endgroup$ – nie_11 Apr 7 '14 at 2:32

As far as I know, you can not do multiplication with (m,m) shamir secret sharing. The typical method to do multiplication on shamir secret shares increases the degree of the sharing polynomial, which is why the parties run an additional protocol to reduce the degree. That is why the degree of the sharing polynomial must be less than $m/2$ if there are $m$ parties.

If you indeed need (m,m) (or $m$ out of $m$ parties must be present to do reconstruction and multiplication), and the only operation you need to compute is multiplication (which I'm not sure about since your comments state you want to do multiplication, but your question mentions dot product), then I'd suggest using multiplicative secret sharing.

If instead you need $m$ out of $m$ computation/reconstruction, but need to do both addition and multiplication operations, you'll have to go with some of the newer MPC constructions which achieve full-threshold security (SPDZ and some of it's references or subsequent works which cite it).

  • $\begingroup$ Thanks for the info. I agree multiplicative secret sharing would work to multiply the values. However my scenario has boolean values at each distributed site. In that case for a '0' if i send shares; one of them will be zero and that will disclose the secret. Any pointers? $\endgroup$ – nie_11 Apr 11 '14 at 10:15
  • $\begingroup$ Also could you suggest a paper with the multiplicative secret sharing scheme that you have explained in your earlier post. Thanks. $\endgroup$ – nie_11 Apr 11 '14 at 11:33
  • 1
    $\begingroup$ @nie_11 I was never able to find a paper on multiplicative secret sharing which is why I asked about it here. In some sense, multiplicative secret sharing is just additive secret sharing in a multiplicative group. Which leads us to 0 (and something I hadn't thought about previously). If we consider the multiplicative group of integers modulo some $n$, 0 is not in that group. So it makes sense 0 won't work. $\endgroup$ – mikeazo Apr 11 '14 at 11:53
  • $\begingroup$ Thanks a ton. That means i have to think of some homomorphic cryptographic scheme which is not something i wanted to do in the first place. $\endgroup$ – nie_11 Apr 12 '14 at 19:01
  • $\begingroup$ [link]google.co.in/… does use multiplicative secret sharing . p10 and 21. Although its a different setting.@mikeazo $\endgroup$ – nie_11 Apr 12 '14 at 19:45

NOTE: This doesn't answer the question... which was how to multiply two secrets...

I played around with it (empirically) and it looks like you can multiply or add as much as you'd like to the secret and the resulting combination is also multiplied/added by the same amount.

IE: I multiplied the share data segment in modulo P, and got back the secret multiplied by the same number.

Of course, this makes sense because you are essentially multiplying the Y-values of the line used to derive the secret.

Thus m parties can multiply and add to their shares, and while none of them will know the secret, the result of combining those shares will be a consistently modified secret.

Inconsistencies in the modified result can be detected as well using VSSS (verifiable secret sharing), and altering the verification generator.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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