# Is there a two-party multiplicative and additive secret sharing scheme ?

A secret sharing scheme such as Shamir's secret sharing allow to perform addition and multiplication for secret values so far as there is at least 3 participants. Addition of two secret values is done locally at each party by adding the corresponding local shares, so it is possible to do addition even with only 2 parties. In the case of multiplication, a degree reduction step is obligatory, because multiplication increases the degree of the shares and this makes it impossible for 2 parties to perform multiplications without the aid of a third one.

It is possible to construct a multiplicative sharing scheme that works for two parties, but it wouldn't be additive.

Is any one aware of a secret sharing scheme for two parties (without the need for a third party) that is BOTH additive and multiplicative, or is it impossible ?

So far I know that it is impossible to construct scalar product protocol with unconditional security for two parties. But I don't suppose that it necessarily prevents the construction of an algebraic (additive+multiplicative) secret sharing scheme.

Update: I am aware of homomorphic encryption and the existence of algebraic homomorphic encryption schemes. However homomorphic encryption is not unconditionally secure unlike secret sharing which is.

-

Unconditionnaly secure 2-party computation does not exist (unfortunately). This is derived from the impossibility of Oblivious Transfer. Also note that unconditionnaly secure OT is also impossible if the 2 parties are quantum.

-
Do you have a reference for the impossibility of OT in both classical and quantum case ? –  M. Alaggan Aug 3 '10 at 17:52
I do not know much about classical cryptography. The sketch of the proof I know: classical OT is not unconditionally secure because quantum OT is not. Quantum OT is equivalent to Quantum Bit-Commitment. Quantum Bit-Commitment is not unconditionally secure (First proof by Mayers [PRL 78, 3414] and Lo and Chau [PRL 78, 3410]. Most complete paper by d'Ariano et al.[arxiv 0905.3801]) Please note that classical OT and classical bit-commitment are NOT equivalent, bit-commitment is a weaker primitive. I guess there are direct proofs of these no-go result without going through all these reductions) –  Loick Aug 4 '10 at 15:46

Yes, there is such scheme. It was recently suggested by Craig Gentry.

Reference: "Fully Homomorphic Encryption Using Ideal Lattices" by Craig Gentry. http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.homoenc.html/\$FILE/stocdhe.pdf

-
Thanks for you answer. I am sorry that I forgot to note that I am aware of those schemes. Homomorphic encryption depend on hardness assumptions, while secret sharing is unconditionally secure (and thus provides much better cipher-text size and less computations (since there is no big integer exponentiations). –  M. Alaggan Jul 21 '10 at 14:39

I believe the answer to your question is yes. See Cramer, Damgard, Maurer, "General Secure Multi-party Computation from any Linear Secret-Sharing Scheme," Eurocrypt 2000.

-
What you said is in way correct to achieve function sharing, but not exact answer for the question asked –  sashank Jul 5 '13 at 10:28

Two operation homomorphic secret sharing scheme has been proposed by Benaloh in the paper , "Secret sharing homomorphisms: Keeping shares of the secret secret" . This scheme allows homomorphic properties at two levels of dividing the secrets ( and their sub secrets) .

Note: This is not same as Homomorphic secret sharing with both add and mult at same level of. This means add at one secret level and mult at sub secret level .

-