Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

4 Answers

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|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
add comment

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

share|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
add comment

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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