I have the following question related to the privacy of multiplication of Shamir Shared Secrets:

Suppose we have two secrets, a and b, shared by a Shamir Secret Sharing Scheme in a (k,n) configuration. We would like to perform a number of secure addition, scalar multiplication, and multiplication operations on the shares e.g. compute a+b * 2ab and reveal the final output of those operations to a third party over a secure channel. We can assume the holders of the shares have no visibility into the reveal process (i.e. they simply reveal their own shares and do not see the other shares).

We have a static, active adversary who has compromised fewer than k shares. The adversary can: a. view the values of the compromised shares b. view the values of the multiplication results sent by the other shares to the compromised shares i.e. the sharings of αβ in the multiplication protocol of Gennaro, Rabin, and Rabin. c. manipulate the multiplication results sent by the compromised shares to the non-compromised shares d. manipulate the share values revealed to the third party by the compromised shares over the secure channel

We don’t care whether or not the final result is correct or even being able to detect if it isn’t (I realize it this may sound contrived by I don’t want to cloud the question with the reasoning behind this).

What I’d like to know is if the adversary is able to gain any information about a or b in the course of participating in an arbitrary sequence of the above operations on a and b? I guess my concern is that by manipulating the αβ sharings, the adversary can somehow coerce the honest players into revealing data about their shares in subsequent multiplication operations. Sorry if this simply doesn’t make sense, I’m an engineer and not a mathemetician :-) If it doesn’t, some sort of intuitive explanation why this can’t happen would be greatly appreciated. The same goes if it is possible.

BTW, I don’t believe the findings of Tompa and Woll related to the general security of linear secret sharing schemes apply because their attack, as I understand it, assumes that the adversary sees the honest shares in the reveal process which is not the case here.


Your Answer

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

Browse other questions tagged or ask your own question.