[논문 리뷰] Asychronous Secure Computations with Optimal Resilience

Author: Ben-Or, M., Kelmer, B., & Rabin, T.

Journal/Conference:  In Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing.

source: https://dl.acm.org/doi/pdf/10.1145/197917.198088

 

 

---

[Abstract]

  We investigate the problem of multiparty computations in a fully connected, asynchronous network of n players, in which up to t Byzantine faults may occur. It was shown in [BCG93] that secure error-less multiparty computation is possible in this setting if and only if t < n/4. We show that when exponentially small probability of error is allowed, this task can be achieved even when the number of faults is in the range n/4 ~ t < n/3. From the lower bounds of [BCG93] for the asynchronous fail-stop model it follows that the resilience, t < n/3, of our protocol is optimal.

 

  We describe an ([n/31 – 1)-resilient protocol that securely computes any function F. With overwhelming probability all the non-faulty players complete the execution of the protocol. Given that all the honest players terminate the protocol, they do so in time polynomial in n, in the boolean complexity of 3, and in Pog -$1, where c is the error probability.

 

  Our protocol follows the scheme of [BGW88, RB89] for multiparty computations in synchronous networks, in which the intermediary results of a circuit for F are always kept shared among the players as a verifiable secret. As the asynchronous network makes it impossible to use a regular Verifiable Secret Sharing scheme for computations, we introduce a new secret sharing scheme called Ultimate Secret Sharing. This scheme guarantees that all the honest players will obtain their share of the secret, and it enables the players to verify that the shares are genuine.

---

[Introduction]

• Each process $p_i$ inputs $x$, and outputs $x^{\prime }$
• Multiparty computation to compute $F(y_1,...,y_n)$ where $y_i=x^{\prime }$ for $p_i\in ACS$ otherwise $y_i=0$.
• core concepts : "During the computation state, ther are times that players need to decide on a subset of honest players, of size at least $2t+1$. ~~~. The problem is that all the honest player need to agree on the same subset (which contains a list of honest players)." => ACS problem (asynchronous common subset)

---

[ACS solution]

There are n players in the network, and each player has n parallel RBC and BA(asynchronous binary Byzantine Agreement) processes respectively which communicate with other players.

BA code for BA processes of player

• Reduce ACS to RBC(asynchronous reliable broadcast, Bracha, G. (1984, August). An asynchronous [(n-1)/3]-resilient consensus protocol. In Proceedings of the third annual ACM symposium on Principles of distributed computing) and BA(asynchronous binary Byzantine agreement, Canetti, R., & Rabin, T. (1993, June). Fast asynchronous Byzantine agreement with optimal resilience. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing).
• Each player RBC-broadcasts its $x^{\prime }$ with encrypted, triggering other players RBC protocols. Finally the RBC protocol decides as RBC-deliver is successfully done and proposes 1 to corresponding BA process.
• After that, BA process run the code decribed in above figure, which resulting binary value (1-accepting the player, 0-excluding the player).