Welcome to MathOverflow

Question

6

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.

edited Jul 21 2010 at 14:36

asked Jul 21 2010 at 14:21

M. Alaggan
61●7

Loick · Accepted Answer · 2010-07-30 02:44:29Z UTC

1

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.

answered Jul 30 2010 at 2:44

Loick
138●10

	Do you have a reference for the impossibility of OT in both classical and quantum case ? – M. Alaggan Aug 3 2010 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 2010 at 15:46

falagar · Answer 2 · 2010-07-21 14:32:17Z UTC

3

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

answered Jul 21 2010 at 14:32

falagar
1,703●4●23

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 2010 at 14:39

David Mandell Freeman · Answer 3 · 2010-07-29 21:47:53Z UTC

2

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.

answered Jul 29 2010 at 21:47

David Mandell Freeman
299●1●6

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.