Sign up ×

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.

share|cite|improve this question

4 Answers 4

up vote 1 down vote accepted

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.

share|cite|improve this answer
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.$FILE/stocdhe.pdf

share|cite|improve this answer
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.

share|cite|improve this answer
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 .

share|cite|improve this answer

Your Answer


