Secure Computation in 2029: Boom, Bust, or Bonanza (keynote speech), David Evans, University of Virginia

In order to predict the development of MPC in 2029, David estimated the U.S. government investment on MPC in the past 1-2 years to be about $100 million, which is roughly about the annual investment spent by the government on art fields [A] . He then made three exciting predictions about MPC in 2029.

• Claim 1. The MPC industry should be bigger than anti-malware industry in 2029. David justified this by extrapolating investments on IT security and predicting that it will probably decrease by 2029 due to progress in developing secure software.
• Claim 2. High cost will no longer be the main impediment to the widespread use of MPC (at least for two-party computation). He explained this by estimating the cost of securely comparing two genomes (e.g. in genetic matchmaking) using MPC in 2004 (which is about $100 million) and estimating its cost in 2029 (which is about $0.001). For security against a malicious adversary, this cost in 2004 is estimated to be about $80 billion while in 2029 it is predicted to be about $0.005 per secure comparison.

In order to perform VSS in a point-to-point network, parties should have access to a broadcast channel, which ensures that all parties receive the same message broadcast by the sender. Juan argues that due to the lack of an efficient broadcast channel, VSS schemes should be measured in terms of broadcast complexity, and the goal should be to minimize the number of broadcasts in VSS. Juan defined a relaxed type of secret sharing called Weak Secret Sharing (WSS), where the recipients reconstruct either the value jointly held by them or a special symbol ⊥ indicating that the dealer is malicious. He then defines VSS by extending the definition of WSS such that the recipients always reconstruct the joint value even if there is cheating in the reconstruction phase.

Juan presented a linear VSS protocol for an unbounded static adversary (t<n/2 ). The protocol uses only two broadcasts in the sharing phase and none in the reconstruction—what he calls a (2,0)-broadcast VSS. This is achieved by increasing the number of rounds in the sharing phase, which makes their protocol (20,1)-round. He compares this to the state-of-the-art VSS protocol of Kumaresan et al. [10] that is a (2,2)-broadcast and (3,2)-round VSS. They first construct a (2,1)-broadcast WSS protocol and then use its sharing phase to build a (3,0)-broadcast, (9,1)-round VSS based on the construction of Rabin and Ben-Or [13]. The number of broadcasts is reduced further to build a (2,0)-broadcast VSS using the moderated VSS of Katz and Koo [8], where the dealer acts as the moderator to simulate broadcast. Such a broadcast is called a modercast. At the end of his talk, Juan explained that their VSS scheme can be used for constructing efficient pseudosignatures, an information-theoretic analogue of digital signatures introduced by [4]. Such signatures can be created in a setup phase to be used for simulating future invocations of broadcast or constructing efficient anonymous channels. Watch Juan’s presentation video here.

 Asynchronous MPC with t<n/2 Using Non-Equivocation, Aniket Kate, MMCI, Saarland University

Aniket presented work on Asynchronous MPC (AMPC), where it is assumed that all messages sent by the parties are eventually delivered but with indefinite delays. In the synchronous setting, MPC has been solved with t<n/2 malicious parties (with cryptographic assumptions) but in the asynchronous setting, the best known algorithm tolerates t<n/3 malicious corruptions. These resiliency bounds are primarily due to the limitations of implementing a reliable broadcast channel that is necessary for constructing an Asynchronous Verifiable Secret Sharing (AVSS) protocol.

In order to verify correctness of a sharing, parties need to prevent the adversary from equivocation, which means making conflicting statements to different parties. A mechanism that makes equivocation impossible is called non-equivocation, which can also be transferable to allow a receiver to verifiably transfer the authenticated statement to other parties. Non-equivocation can be implemented using an increment-only counter and a digital signature oracle, which can be constructed using trusted hardware modules readily available in commodity computers and smartphone devices [12].

Mahnush motivated her talk by the fact that guaranteeing synchrony in most real applications is difficult and even impractical. Thus, in order to use MPC in such applications, certain techniques are required to deal with asynchrony in a malicious setting. One can design a scalable MPC protocol in this setting by delegating computation of each gate to a logarithmic set of parties called a quorum, in which at most a certain fraction of parties are malicious. The quorum then computes the gate using any MPC protocol. Mahnush explained that distribution of communications and computations among several quorums requires incorporating extra coordination efforts between parties, which they handle using a number of efficient tools and techniques.

In a setup phase, a set of n quorums are created using the quorum building algorithm of King et al. [9] optimized with the Byzantine agreement scheme of Braud-Santoni et al. [6], which costs soft-O(1) bits per party. Mahnush argued that the parties in each quorum require a mechanism to coordinate with other quorums on when to start computation on asynchronous inputs. In other words, they need to wait for sufficient number of inputs to be received until they start the computation.

To this end, they propose to count the number of ready inputs using a distributed data structure called a τ -counter, where τ=n−t is the threshold on the number inputs to be received before the circuit is evaluated, and t<n/8 is the number of malicious parties. Using a τ -counter, MPC can be solved without assuming any synchrony points in the algorithm.

At the start of his talk, Tomas described how MPC can be used to implement a secure collaborative credit rating for Danish dairy farmers who are willing to get loans. Credit rating is one of the interesting classical problems that is solved using MPC. Tomas described how this problem can be modeled by linear programming. A linear program consists of n variables and m constraints and the goal is to maximize an objective function. A solution for a linear program is an assignment to the variables such that the constraints hold.

To solve a linear program for n=285 variables and m=4 constraints, the presented protocol requires 2mn+6m2+n≃2700 multiplications and n+3m≃300comparisons. A Java implementation of their protocol that uses Amazon’s cloud services shows that the running time for this computation is around 5 minutes. The implementation is being demoed for actual banks using real data which allows bankers to jointly rank the farmers based on their credit scores. For more information about Tomas motivation for this problem see another blog post about his talk here.

Abdel introduced a new class of problems in which a graph is shared between parties as their inputs. The parties want to evaluate a function such as max-flow or shortest path over this shared graph. In most combinatorial problems such as various graph problems, the execution path depends on the input data. Thus, even if all input data are appropriately shared or encrypted among the parties, the execution path itself may reveal some information to the adversary.

Mahdi proposed a method to reduce the communication cost of their protocol by performing local communications in logarithmic-size groups of parties called quorums, where the number of adversary-controlled parties in each quorum is at most a certain fraction. The quorums are created in an offline phase using the Byzantine agreement protocol of Santoni et al. [6]. The offline phase also uses the fully homomorphic encryption protocols of Brakerski et al. [5] to evaluate a small-depth circuit. This is done to generated a sufficient number of Beaver [2] multiplication triples.

In the online phase, each input is secret shared in a quorum using Shamir’s secret sharing scheme. Each gate of the circuit is computed by a quorum over shares, where multiplication is performed using Beaver’s triples. Parties in the quorum send the result of this computation to all quorums associated with gates that need this result as input. It is necessary to securely send the output from one quorum to another without revealing any information to any individual party or to any coalition of adversarial parties. Mahdi solves this by creating fresh shares of the output for the target quorum, where the new shares are values of a new random polynomial that still evaluates to the (secret) output at 0.

Koki described an implementation of an MPC protocol called MEVAL (Multi-party EVALuator), which is optimized for statistical analyses. His talk described the techniques they have used to make their protocol efficient and the experiments conducted for evaluating the system. The computation in MEVAL is performed over values shared using Shamir’s secret-sharing scheme among three parties, where at most one of them is controlled by a passive adversary. MEVAL can also be used in a server-based setting, where all clients share their inputs between three servers. One application of such a setting is secure outsourcing of data storage.

References

[1] K. E. Batcher: “Sorting networks and their applications”, Proceedings of the April 30—May 2, 1968, spring joint computer conference, pp. 307—314, 1968.

[2] Donald Beaver: Efficient Multiparty Protocols Using Circuit Randomization inAdvances in Cryptology — CRYPTO ’91 (Feigenbaum, Joan, ed.). Springer Berlin Heidelberg, 1991.

[3] Zuzana Beerliová-Trubı́niová, Martin Hirt, Jesper Buus Nielsen: “On the Theoretical Gap Between Synchronous and Asynchronous MPC Protocols”, Proceedings of the 29th Symposium on Principles of Distributed Computing, pp. 211—218, 2010.

[4] Birgit Pfitzmann, Michael Waidner: Information-theoretic Pseudosignatures and Byzantine Agreement for t≥n/3 . 1996. Technical Report RZ 2882 (#90830), IBM Research.

[5] Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan: “Fully Homomorphic Encryption Without Bootstrapping”, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 309—325, 2012.

[6] Nicolas Braud-Santoni, Rachid Guerraoui, Florian Huc: “Fast Byzantine Agreement”, Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 57—64, 2013.

[7] Ivan Damgård, Valerio Pastro, Nigel P. Smart, Sarah Zakarias: “Multiparty Computation from Somewhat Homomorphic Encryption”, Advances in Cryptology — CRYPTO 2012, pp. 643—662, 2012.

[8] Jonathan Katz, Chiu-Yuen Koo: On Expected Constant-Round Protocols for Byzantine Agreement in Advances in Cryptology – CRYPTO 2006 (Dwork, Cynthia, ed.). Springer Berlin Heidelberg, 2006.

[9] V. King, S. Lonergan, J. Saia, A. Trehan: “Load balanced Scalable Byzantine Agreement through Quorum Building, with Full Information”,International Conference on Distributed Computing and Networking (ICDCN), 2011.

[10] Ranjit Kumaresan, Arpita Patra, C.Pandu Rangan: The Round Complexity of Verifiable Secret Sharing: The Statistical Case in Advances in Cryptology – ASIACRYPT 2010 (Abe, Masayuki, ed.). Springer Berlin Heidelberg, 2010.

[11] Helger Lipmaa, Tomas Toft: Secure Equality and Greater-Than Tests with Sublinear Online Complexity in Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013. URL http://dx.doi.org/10.1007/978-3-642-39212-2_56.

[12] Michael Backes, Fabian Bendun, Ashish Choudhury, Aniket Kate: Asynchronous MPC with t<n/2 Using Non-equivocation. Cryptology ePrint Archive, Report 2013/745, 2013.

[13] Tal Rabin, Michael Ben-Or: “Verifiable secret sharing and multiparty protocols with honest majority”, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 73—85, 1989.