Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I was wondering how we can get a secret sharing of $a+b$ from the sharing of secrets $a$ and $b$ themselves by using an XOR secret sharing scheme, where $a_1,...,a_n$ and $b_1,...,b_n$ are the shares for $a$ and $b$ respectively. Can anyone give me any suggestion?

share|improve this question
    
What do you mean $a_1, ..., a_n$ are the shares for $a$? Do you mean that you want someone to be able to reconstruct the ultimate secret $a+b$ if he have enough $a_i$ and $b_j$ shares? If not, what do you mean? –  poncho Oct 29 '13 at 15:53
    
$a_1,...a_n$ are the shares distributed to players 1 to $n$ for the secret $a$, and $b_1,...b_n$ are the shares distributed to players 1 to $n$ for the secret $b$ @poncho –  freak_warrior Oct 29 '13 at 15:58
    
I don't think you can with xor sharing. You could with additive secret sharing or shamir secret sharing. You can certainly get the xor of a and b. –  mikeazo Oct 29 '13 at 15:59
    
What are you trying to solve? If player $i$ has both share $a_i$ and $b_i$, then the same subset of players with shares can reconstruct both $a$ and $b$ individually; with both $a$ and $b$, we can recompute $a+b$. Or, are you asking "how can each individual player construct a share for the secret $a+b$ (and, if so, why)? –  poncho Oct 29 '13 at 16:04
2  
if $a=a_1\oplus a_2\oplus\dots\oplus a_n$, if you have less than $n$ shares you cannot reconstruct $a$. Are you sure you aren't wanting shamir secret sharing? –  mikeazo Oct 29 '13 at 16:19
show 3 more comments

1 Answer

up vote 1 down vote accepted

The answer is almost definitely no for what I think you want (question is still unclear). I was hoping someone else could give a definite no, but since they haven't I figured I'd write this up.

Your exact secret sharing method probably needs to be fully described in the question. I'm going to assume that $a=a_1\oplus a_2\oplus\dots\oplus a_n$ and similarly for $b$. Party $p_i$ is given $a_i,b_i$ and you want the parties to be able to compute shares, say $c_i$ of $c=a+b$ without reconstructing $a$ or $b$. I'll assume we are working in some finite field $\mathbb{F}$ and that $a_1,\dots,a_{n-1}$ are chosen randomly from the field and $a_n=a\oplus a_1\oplus\dots\oplus a_{n-1}$. The shares of $b$ are chosen similarly.

Note that this is basically additive secret sharing in a field of characteristic two. But, when you say you want to compute shares of the sum of $a+b$, I'm assuming you don't mean field-of-characteristic-2 addition (which is just xor). If that is what you mean, then the answer is simple (each party $p_i$ simply computes $c_i=a_i\oplus b_i$). I'm assuming you want something like 32 bit addition (i.e., addition mod $2^{32}$ or something very similar like addition in $\mathbb{Z}_p$ where $p$ is possibly the next prime after $2^{32}$).

To see why I don't believe it is possible, lets use $n=2$.

So, $p_1$ gets $a_1,b_1$ and $p_2$ gets $a_2,b_2$ where $a=a_1\oplus a_2$ and $b=b_1\oplus b_2$.

Therefore, the problem reduces to the following, we need some operation, say $\boxplus$, such that $(a_1\boxplus b_1)\oplus(a_2\boxplus b_2) = a+b$

So, what are the possibilities for $\boxplus$. If we allow for communication to take place between $p_1$ and $p_2$, then the answer is yes, it can be done. In this case, we can do multiparty computation in the characteristic 2 field and construct a 32 bit adder circuit. This should be possible as far as I understand MPC.

Now, assuming you do not allow communication between the parties after the shares are distributed (which I'm guessing is what you wanted), I just don't see a way to do it (though I haven't been able to fully prove it, if nothing else hopefully my answer will bring some good discussion). If we take the approach of MPC, all we can do on the shares is compute the xor and multiply by a constant. Given those operations I don't see how you would construct an adder.

Another temptation might be to simply add $a_i,b_i$ using regular addition. In which case you get $(a_1+b_1)\oplus(a_2+b_2)$ which will not be $a+b$. Really we need an operation $\boxplus$ which is commutative and associative with $\oplus$ in which case you could do $(a_1\boxplus b_1)\oplus(a_2\boxplus b_2)=(a_1\boxplus b_1)\oplus(b_2\boxplus a_2)=a_1\boxplus (b_1\oplus b_2)\boxplus a_2=a_1\boxplus b\boxplus a_2$. It is unclear where to go from there. This is where I ended up and couldn't go any further and why I believe the answer is no in the case of no communication.

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.