8
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have a reference for the impossibility of OT in both classical and quantum case ? $\endgroup$
    – Mohammad Alaggan
    Aug 3, 2010 at 17:52
  • $\begingroup$ 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) $\endgroup$
    – Loick
    Aug 4, 2010 at 15:46
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Mohammad Alaggan
    Jul 21, 2010 at 14:39
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ What you said is in way correct to achieve function sharing, but not exact answer for the question asked $\endgroup$
    – sashank
    Jul 5, 2013 at 10:28
1
$\begingroup$

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 .

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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