Re: Jointly calculating the sum

From: Ann Brandon (ann_brandon_spamfree_at_yahoo.com)
Date: 07/27/05 

Date: Wed, 27 Jul 2005 22:56:27 +0200

David Wagner wrote:
> Ann Brandon wrote:
>
>>assume we have 3 partys Alice, Bob and Carol. Each party chooses a
>>random value r_A, r_B, r_C \in Z_p (where p is prime). Now the partys
>>want to calculate the sum r=r_A + r_B + r_C, so that each party only
>>knows its own value and the sum r.
>
>
> This is a classic multi-party secure computation problem. There are
> methods for multi-party secure computation that are very efficient for
> linear computations (like this one); I believe that most or all of the
> verifiable secret sharing (VSS) based schemes fall into this camp.
> I'd look into the literature on that topic.
>
> It may be as simple as Alice distributing shares of r_A to Bob and Carol;
> Bob distributes shares of r_B; Carol distributing shares of r_C; having
> each party sum up their shares and publish the sum; and finally publicly
> interpolating to recover r. However, I haven't tried to check the details.
Ok, but I hoped there is something more efficient, cause such a scheme
needs the following steps:
1. Each party distributes verification-values for the shares.
2. Each party distributes its shares.
Assuming not only 3 partys, rather n, the problem is now, that in the
first step each party has to do n broadcasts, so over all the scheme
needs n^2 broadcasts. Assuming a broadcast needs only n-1 messages, then
we need for the first step n^2 (n-1) messages, which is for a large n
not possible, or am I doing something wrong?

I thought of using a threshold encryption scheme which is additive
homomorphic. Then each party encrypts its value r_i to E(r_i). The
values are then broadcasted to each party (so we have n broadcasts).
Each party then computes E(r)=E(r_1)*..*E(r_n) and computes her
part-decryption of E(r). She broadcasts this, so that each party can
decrypt to r.

What do you think of this? In fact it needs a setup-phase for setting up
the threshold-scheme, but after that it only needs 2n broadcasts,
instead of n^2. Is there maybe another solution which is simpler or
needs another setup-phase?

Thanks for help,
Ann

Relevant Pages

  • Re: Jointly calculating the sum
    ... >Ok, but I hoped there is something more efficient, cause such a scheme ... Each party distributes verification-values for the shares. ... I would have thought that in step 1, each party broadcasts a single ... Maybe you're worried about the cost of robustness? ...
    (sci.crypt)
  • Re: Attack on Verifiable Secret Sharing scheme
    ... >cause it is not available anymore. ... Have each party of T, say party i, compute a ... verify that each quantity r_they receive is accurate, and after the ... This requires Obroadcasts of messages of size O(you would say ...
    (sci.crypt)
  • Re: Canadian Action Party: Canadian Election: Loonies will Win
    ... >>> They weren't running a candidate in my riding, even the Rhinoceros Party ... >>> Dennis (flame suit on, and waiting for the aluminum foil beanie ... the government is about to spend hundreds of millions ... >To bring this back on topic, I worry about a scheme called the National Diabetes Services ...
    (alt.support.diabetes)
  • Re: Jointly calculating the sum
    ... >knows its own value and the sum r. ... It may be as simple as Alice distributing shares of r_A to Bob and Carol; ... each party sum up their shares and publish the sum; ...
    (sci.crypt)
  • Re: Attack on Verifiable Secret Sharing scheme
    ... >>Yes, of course, but I assume in this example, that the dealer is honest. ... But why would you design your scheme ... Some time later a new party P_wants ... then the adversary gets all shares from honest ...
    (sci.crypt)