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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .