# Machinations

Simon’s Institute Workshop on Securing Computation
June 20, 2015, 6:28 am
Filed under: Uncategorized | Tags: ,

[The following report on the Securing Computation Workshop at the Simons Institute was written by my students Mahnush Movahedi and Mahdi Zamani. A polished version of this report is available HERE.]

### Lower Bounds for Information-Theoretic MPC, Ivan Damgård, Aarhus University

Ivan started his talk by comparing unconditional multi-party computation (MPC) protocols to cryptographic techniques such as FHE: The unconditional protocols are usually much more computationally-efficient than FHE protocols. On the other hand, unconditional techniques usually require lots of interactions and their round complexity is usually large. One interesting question to ask here is that “Is it possible to design an unconditionally-secure FHE that has the benefits of both schemes?” The answer is, unfortunately, still unknown, but we have some partial answers. The goal here is to determine how many messages we need to transmit in order to compute a non-trivial function (such as the AND of bits each coming from one player) securely. Ivan argued that if there are players with semi-honest corruptions, the protocol must send messages. For example, for and , we need to send at least six messages to compute the AND functionality. The intuition behind this is that every player must communicate with at least players, and must later receive another message to compute the output. So, for each player we count messages sent or received, and thus the total becomes at least messages sent. One thing that I should point out here (and which my own research touches on) is that they assume all-to-all communication. Several protocols (such as ) break this lower bound by requiring each party to only communicate with a small (polylog size) set of parties (see [SZ15] for a complete discussion on sublinear MPC results).
Bounding the communication and rounds needed in general seems hard. But, it might be possible to bound these for the gate-by-gate protocols, where a circuit is evaluated gate-by-gate: the invariant is that we secret-share the inputs to each gate, and then evaluate the gate functionality over the secret-shared inputs to generate the gate output. Known protocols with this strategy have communication complexity and round complexity, where is the circuit size. But, are these optimal? The bottleneck for gate-by-gate protocols is the multiplication gate, which Ivan argues to take at least message to be evaluated. Thus, the best known results are asymptotically optimal. Ivan then finished his talk by showing that the same lower bounds exist for the case of dishonest majority, where a preprocessing phase is necessary for MPC. Thus, to really improve the existing protocols, we need a fundamentally different approach.

### Obfuscation: Past, Present, and Possible Futures, Amit Sahai, UCLA

In program obfuscation, a given program is converted to another program that represents the same functionality (i.e., the same I/O) while an adversary who can see cannot understand its logic. From a cryptographic perspective, this is like having a software that can keep a secret. This leads to a new notion of program obfuscation called indistinguishability obfuscation (iO), where a polynomial-time adversary cannot distinguish between the obfuscations of two equivalent programs. The first mathematical construction of an indistinguishability obfuscator was proposed by Garg-Gentry-Halevi in 2013. The main idea to obfuscate programs using structured noise rather than just random noise. When the program is evaluated, the noise cancels out and the correct output is obtained.

To this end, a multilinear map can be used to encode field elements with specific algebraic manipulations and a Boolean function that returns Yes/No when the encoded value is zero or not. The program is first converted to a sequence matrices using a technique called oblivious matrix branching program. Then, the Kilian’s randomization technique is used to generate structured noise: the matrices are multiplied by a sequence of random matrices. The key challenge to the current obfuscation scheme is the input-mixing attack. A technique is required to enforce honest behavior in some way. Amit finished his talk by arguing that multilinear maps provide a new hardness generating technique at the level of Diffie-Hellman and learning with error hardness assumptions, but they have mainly been used for obfuscation. One open question is that can multilinear maps be used for solving other security problems?

### Two-Round MPC via Multi-Key FHE, Daniel Wichs, Northeastern University

Daniel started his talk by asking two motivating questions: (1) Can we construct MPC with minimal round complexity? (2) Can we construct MPC directly using FHE techniques? A fully homomorphic encryption (FHE) scheme allows to perform secure computation over encrypted data without decrypting it [Gen09]. Asharov et al. [AJLTVW12] show how FHE can be used to construct constant-round MPC by designing a threshold FHE (TFHE) technique that provides Byzantine-resilience and circuit-independent communication cost. All parties first encrypt their inputs under an FHE scheme (such as that of [BGV12]) and send the encrypted values to all other parties. Then, each party evaluates the desired function over the encrypted inputs via homomorphism, and eventually participates in a distributed decryption protocol to decrypt the output. This protocol requires a distributed key generation algorithm to agree on a common public key and a secret-shared private key. While the MPC protocol of [AJLTVW12] requires three rounds of communication, Daniel described a new FHE-based MPC protocol that requires only two rounds of communication. This result as well as [AJLTVW12] are secure in the common random string (CRS) model  ( an algorithm is secure in the CRS model if it assumes that all parties have access to a common random string taken from a predetermined distribution). This assumption is required for malicious security in both work. Also, both results require a non-interactive zero-knowledge (NIZK) technique to enforce honest behavior in the malicious setting.
The idea of the new result is to remove the first round (distributed key generation) of the protocol: Each party chooses its own individual public key and secret key pair with coordinating with other parties, encrypts its input under that public key, and broadcasts the ciphertext. But how to compute over ciphertext generated by these uncoordinated keys and decrypt the result? The key idea is to use a multi-key FHE scheme that can compute over a set ciphertext each encrypted with a different key. The result will be another ciphertext that can only be decrypted with a certain number of private keys. Recently, Clear and McGoldrick [CM14] proposed a multi-key FHE scheme using the learning with error (LWE) hardness assumption  (the LWE problem asks to recover a secret from a sequence of “approximate” random linear equations. Algorithms based on the LWE assumption belong to the so-called post-quantum cryptography, where the security cannot be broken in feasible time even using a quantum computer).

### Efficient Multiparty Protocols via Log-Depth Threshold Formulae, Ron Rothblum, Weizmann Institute

Ron presented a new approach for designing multi-party computation protocols when there are more than two parties. Their approach is motivated by the fact that the huge body of work on MPC are very complicated; there is a need for a simple and flexible approach. The basic technique that they propose is called player emulation; the computational task run by a player is emulated by other players. This allows us to reduce the construction of an -party protocol to the construction of (small) constant-party protocols which are much easier to design. This idea consists of two steps:
1. Design a protocol for a small number of parties (say, 3 or 4) which achieves security against a single corrupted party. Such protocols are typically easy to construct as they may employ techniques that do not scale well with the number of corrupted parties.
2. Recursively compose with itself to obtain an efficient n-party protocol which achieves security against a constant fraction of corrupted parties.

The reduction idea is described in the following. First, consider a trivial -party setting that includes a trusted party . The parties send their inputs to whom locally computes the MPC functionality and returns the output back to all parties. Now, replace the trusted party with a small constant number of virtual parties, say , which emulate the behavior of . The new protocol is secure as long as the adversary does not control a majority of the virtual parties. We now proceed by replacing by with three new virtual parties . The new protocol is secure even if the adversary controls either one of and one of the ’s, or two of the ’s. Using this, Ron constructed a formula as shown in Figure 2↑, which can be used to build a formula for the entire protocol as shown in Figure 3↓, where the leaves are the real parties.

Two things that are necessary for the new model to result in efficient MPC protocols are (1) a secure 3-party protocol; and (2) a logarithmic-depth formula that computes majority using only gates. For the first requirement we can simply use the protocol of [BGW88] over three parties. For the second one, Ron proposed two techniques. One is to use a randomized majority-from-majorities algorithm (this results in statistical security) and one using a deterministic but only close to optimal solution (see his talk for more details). The new approach that Ron presented allows us to give new and conceptually simple proofs of classical MPC results such as [BGW88], and also design simple MPC protocols in the future.

### Rethinking Secure Computation – A Greedy Approach, Muthu Venkitasubramaniam, University of Rochester

The general framework for secure computation consists of two steps: (1) Compile a functionality into one of several standard representations such as a circuit (Boolean or arithmetic) or an oblivious RAM; (2) Use a generic scheme such as [Yao82, GMW87, BGW88, CCD88] to securely evaluate the functionality. However, for some certain problems such as Private Set Intersection, specific solutions can result in significantly more efficient solutions. Inspired by these, Muthu presented a new algorithmic approach for designing secure two-party computation protocols. In their model (join work with Abhi Shelat from UVA), they show that several problems such as convex hull, minimum spanning tree, unit job scheduling, and single source shortest path can be securely computed only by using secure comparison.

The underlying idea among all of these problems is that each of them has some known greedy algorithm. Accordingly, Muthu described a new framework called Greedy-Millionaire Framework, where a function f is defined secure greedy compatible if there exists it has the following three properties:

1. Unique Solution: Given inputs and of Alice and Bob, is unique;
2. Unique Order: There is a unique order in which the output is presented in the greedy algorithm;
3. Local Updatability: The local greedy heuristic can be computed using a comparison operation over the function locally computed over each of the inputs.
Figure 4↑ shows the message complexity of their protocols for solving the listed problem using the Greedy-Millionaire framework. Their model currently supports secure computation in the semi-honest and covert settings. Other than extending their model to the malicious setting, one open problem here is that “Can we adapt their framework to model secure computation using other primitives rather than the secure comparison operation? For example, primitives that work for graph algorithms?”

### Cryptocurrencies and Smart Contracts, Elaine Shi, University of Maryland

Bitcoin is a decentralized cryptocurrency that can be used to perform secure computation using the concept of blockchains. A blockchain is a public ledger of all Bitcoin transactions that have ever been executed. It is constantly growing as “completed” blocks are added to it with a new set of recordings (read more about blockchains here). The blockchain used in bitcoin is guaranteed to be always correct but it does not guarantee privacy of users. Elaine described a universally-composable model of the bitcoin protocol, where the functionality exposes internal state of the blockchain to everyone, and the security proof is conducted in the -hybrid model.
Next, Elaine introduced Ethereum, a new cryptocurrency that consists of a ledger and user-defined smart contracts. The contracts run transactions (e.g., transfer x amount from y) over the ledger and the ledger ensures consensus among all users. A system called Hawk provides privacy-preserving smart contracts. Hawk implements contracts as auctions: each auction receives bids from the users and the auctioneer closes the auction at some point. One challenging problem here is that all bids are visible to the public so, for example, a smart user can wait for others and then submit its bid. In their model, the auctioneer (also called the manager) is assumed to be semi-trusted; it is standard to implement the manager using MPC but for efficiency purposes this is not considered in their model. Hawk supports financial fairness by punishing bad behaviors.

### References

[AJLTVW12] Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, Daniel Wichs. Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In Advances in Cryptology — EUROCRYPT 2012 . Springer Berlin Heidelberg, 2012.

[BGT13] Elette Boyle, Shafi Goldwasser, Stefano Tessaro. Communication locality in secure multi-party computation: how to run sublinear algorithms in a distributed setting. Proceedings of the 10th theory of cryptography conference on Theory of Cryptography, pp. 356—376, 2013.

[BGV12] 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.

[CCD88] David Chaum, Claude Crépeau, Ivan Damgård. Multiparty unconditionally secure protocols. Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 11—19, 1988.

[DKMS12] Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia. Brief announcement: breaking the bit barrier, secure multiparty computation with a static adversary. Proceedings of the 2012 ACM symposium on Principles of distributed computing, pp. 227—228, 2012.

[DKMS14] Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia. Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation. In Distributed Computing and Networking . Springer Berlin Heidelberg, 2014.

[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of the 41st annual ACM symposium on Theory of computing, pp. 169—178, 2009.

[BGW88] Michael Ben-Or, Shafi Goldwasser, Avi Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computing. Proceedings of the Twentieth ACM Symposium on the Theory of Computing (STOC), pp. 1—10, 1988.

[CM14] Michael Clear, Ciarán McGoldrick: Multi-Identity and Multi-Key Leveled FHE from Learning with Errors. Cryptology ePrint Archive, Report 2014/798, 2014.

[GMW87] Oded Goldreich, Silvio Micali, Avi Wigderson. How to play ANY mental game. Proceedings of the nineteenth annual ACM symposium on Theory of computing, pp. 218—229, 1987.

[SZ15] Jared Saia, Mahdi Zamani. Recent Results in Scalable Multi-Party Computation. In SOFSEM 2015: Theory and Practice of Computer Science (Italiano, GiuseppeF. and Margaria-Steffen, Tiziana and Pokorný, Jaroslav and Quisquater, Jean-Jacques and Wattenhofer, Roger, ed.). Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46078-8_3.

[Yao82] Andrew C. Yao. Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pp. 160—164, 1982.

Secure Multiparty Computation Workshop
June 22, 2014, 10:48 pm
Filed under: Uncategorized | Tags: , ,

Last month I went to a  workshop on secure multiparty computation that was organized by IARPA.  I’ve had mixed luck with these types of workshops that are organized by funding agencies.  However, this one was pretty good, because of the timeliness of the topic, well-prepared talks, and the fact that the participants were some of the big names in security and MPC.

This was also one first times I’ve visited and given a talk at MIT, which was a lot of fun.  Many of the talk slides are included in the workshop link above.

Workshop on Applied Multi-Party Computation

Following is a very nice report of a Workshop on Applied Multiparty Computation at which my students Mahnush Movahedi and Mahdi Zamani gave talks.  Enjoy.    –   Jared

# Workshop on Applied Multi-Party Computation: A Summary

## Mahnush Movahedi and Mahdi Zamani

Recently, we attended a great workshop on applied Multiparty Computation (MPC) hosted by Microsoft Research Redmond and organized by Seny Kamara and Payman Mohassel. The workshop consisted of 21 talks distributed in two days and mostly focused on practical applications of MPC. Although most talks were very interesting and valuable, we decided to summarize only those that were more related to our current research. For a great summary of the entire workshop, see the related posts in MPC Lounge blog by a team from Aarhus Crypto Group.

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

David gave a great talk about the past and future of MPC. He started with a few interesting predictions about where MPC will be in the year 2029 (15 years from now). He explained that the reason for choosing 2029 is inspired by an essay by Neil DeGrasse Tyson and some experiments indicating that scientific developments double every 15 years (see this for example). Using Google Scholar, David showed that until 1999, the number of papers published about MPC was about 160 while this number increases to about 700 until 2013. He justified the doubling time of 15 years again by referring to an interesting paper by Shafi Goldwasser in PODC 1997, where she correctly predicted a similar growth for MPC.

Figure 1. David Evans

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. Figure 2. Estimated cost of building MPC for genome comparison in the semi-honest model (courtesy of David Evans). • Claim 3. We don’t yet know what the “killer app” for MPC is and it’s probably not privacy. David argues that the amount of money people pay for privacy is usually very small. So, he predicts that the killer app for MPC will not just use MPC for privacy, and there are aspects of MPC that will probably be very useful in some applications. There was a panel on the business case for MPC after David’s talk, where people discussed more about the killer app for MPC. The panel’s video is available here. David finally stated three things that really matter for the future of MPC. • What if the outputs leak? In MPC, the output of computation is revealed to everyone. This output may leak some information to the adversary. Is there a way to measure or limit this leakage? • How to ensure users accept and trust the MPC-based application? • How to implement MPC with low (human) cost? David finished his presentation by talking about his recent book Dori-Mic and the Universal Machine!, which is for any “toddler who is falling behind in theoretical computer science” and in general for curious children of all age! Watch David’s presentation here. ### Broadcast (and Round) Efficient Secure Multiparty Computation, Juan Garay, Yahoo! Labs Juan started with a history of MPC for arithmetic circuits using the share-compute-reveal paradigm, where a certain fraction of parties are malicious. In this paradigm, inputs are first secret-shared among all parties using a Verifiable Secret Sharing (VSS) scheme. In order to get the sum of all inputs, each party simply adds its shares locally to find a share of the sum. On the other hand, the product of input shares is not necessarily a valid share of the product of the inputs. Beaver [2] solves this by precomputing a multiplication triple in an offline phase and using it to compute a share of the product in the online phase. Figure 3. Juan Garay 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]. Their AMPC improves the resiliency bound from t<n/3 to t<n/2 and improves the communication complexity from O(n4κ) to O(n3κ) when compared to the state-of-the-art AMPC of Beerliova et al. [3], where κ is the security parameter. The protocol assumes the existence of a transferable non-equivocation mechanism, which the authors believe is more practical than a synchronous broadcast round assumed by [3]. Watch Aniket’s presentation video here. ### Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation, Mahnush Movahedi, University of New Mexico 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. Figure 4. Mahnush Movahedi 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. In order to send the output of each quorum to the next quorum, parties in the first quorum generate a joint random number and simply mask the output by adding it to the random number. This ensure that no coalition of malicious parties can get together to learn the intermediate outputs. Parties of the next quorum then participate in an MPC to unmask the inputs and evaluate the associated gate over the inputs. The protocol requires each party to send soft-O(m/n) bits and compute soft-O(m/n) operations, where m is the size of the circuit. Watch Mahnush’s presentation video here. ### Secure Collaborative Statistics in Credit Rating Using Linear Programming, Tomas Toft, Aarhus University 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. One well-known strategy for solving linear programs is the simplex method. Tomas argued that despite an exponential worst-case complexity, simplex is eﬃcient in practice and can be easily implemented since it only requires integer arithmetic operations and comparisons. Their protocol solves the linear programming problem using black-box access to secure modulo arithmetic of Damgard et al. [7] along with additional sub-protocol for comparison (see Lipmaa and Toft [11]). 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. ### Securely Solving Standard Network Flow Problems with Secure Multi-Party Computation, Abdelrahaman Aly, C.O.R.E., Univesité catholique de Louvain 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. As an example for a branching that depends on a secret input, Abdel mentioned a counter loop, where the stopping condition is dependent on the input. In this example, the adversary can exploit branching patterns and running time of the algorithm in order to obtain some information about the secrets if this loop is implemented in a non-secure traditional way. Thus, it is necessary to translate the traditional (non-secure) algorithms on graphs to secure versions. Unfortunately, this translation process increases the computation cost of the algorithm. This overhead depends on the type of the algorithm and graph. For example, the asymptotic complexity of the traditional Edmonds-Karp algorithm to find max-flow is O(|V|^2|E|) and its optimized version is O(|E|^2|V|) , while the complexity of its secure version is O(|V|^5) , where |V| and |E| are the number of vertices and edges in the graph respectively. Unfortunately, the actual costs of their protocol is still very high for practical purposes. ### MPC in Large Networks with an Application to Anonymous Broadcast, Mahdi Zamani, University of New Mexico Mahdi argued that MPC with many players is becoming of increasingly importance, with the growth of modern networks. He suggested that it is possible to perform secure computations efficiently over such large networks. One motivation is that MPC can be used to protect freedom of speech in large social networks like Twitter by providing anonymous communication. In addition, MPC in large networks could be used for analysis of massive data. He proposed an MPC protocol that is secure against a malicious adversary corrupting up to a 1/10 fraction of the parties. Their protocol sends in average O(mlog^3 n) bits and computes O(mlog^4 n) operations in O(d) rounds, where m is the size of the circuit with depth d . Figure 5. Mahdi’s microbenchmark results 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. Mahdi argued that the anonymous broadcast problem can be reduced to the problem of Multi-Party Sorting (MPS), where parties want to jointly sort their inputs. In order to perform MPS, they compute the sorting network of Batcher [1]. At the end of his talk, Mahdi showed some microbenchmark results for several runs of MPS using their MPC protocol. As an example, for a network with about 30 million parties, each with a 20 -byte input, their protocol requires each party to send 5 kilobytes on average per item sorted. See figure 5. ### MEVAL: A Practically Efficient System for Secure Multi-party Statistical Analysis, Koki Hamada, NTT Secure Platform Laboratories 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. Koki mentioned that the protocol has been carefully implemented in order to achieve high efficiency. Some of the techniques used for this purpose are asynchronous processing, pseudorandom secret sharing, and optimized field operations. Koki argued that the main idea behind asynchronous implementation is to enable better resource usage by using both computation and communication resources at the same time in parallel instead of using them sequentially. This helps MEVAL to decrease its running time significantly. MEVAL achieves 8.7 million multiplications per second, and it can sort one million values in less than 7 seconds. Figure 6. A great dinner with (from right to left) Saeed SadeghianArash AfsharYan Huang, Elaine Shi, and David Evans. # 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 Beerliová-Trubı́niová, 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. Copyright (C) 2014 Mahnush Movahedi and Mahdi Zamani Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear the full citation. Abstracting with credit is permitted. This work may be published or be a basis for publication in the future. Copyright may be transferred without further notice and this version may no longer be accessible. Efficient Secure Multiparty Computation February 27, 2012, 10:31 pm Filed under: Uncategorized | Tags: , , , Attached is a paper on a problem we’ve been working on for a while: an efficient algorithm for Secure Multiparty Computation (SMPC) against a static adversary. In the SMPC problem, n players each have a private input, and their goal is to compute the value of a n-ary function, f, over the inputs, without revealing any information about the inputs. The problem is complicated by the fact that a hidden subset of the players are controlled by an adversary that actively tries to subvert this goal. SMPC abstracts several important problems in distributed security, and so, not surprisingly, there have been thousands of papers written in the last several decades addressing it. However, there is a striking barrier that prevents wide-spread use: current algorithms to solve SMPC are not resource efficient. In particular, if there are n players involved in the computation and the function f can be computed by a circuit with m gates, then most algorithms require each player to send a number of messages and perform a number of computations that is $\Omega(mn)$ We describe scalable algorithms for SMPC against a static adversary. We assume a partially synchronous message passing communication model, but unlike most related work, we do not assume the existence of a broadcast channel. Our main result holds for the case where there are$n\$ players, of which a $1/3-\epsilon$ fraction are controlled by an adversary, for $\epsilon$ any positive constant. We describe a SMPC algorithm for this model that requires each player to send $\tilde{O}(\frac{n+m}{n} + \sqrt n)$ messagesand perform $\tilde{O}(\frac{n+m}{n} + \sqrt n)$ computations to compute any function f, where m is the size of a circuit to compute f.

Yao’s Millionaire Problem
November 18, 2011, 4:27 pm
Filed under: Uncategorized | Tags: , , ,

In this post, I want to talk about a research problem that I think even our new Republican legislatures can get excited about: Yao’s millionaire problem.  In this problem, two millionaires want to determine who is richer, but neither wants to reveal their private net worth.  Can we develop a protocol to help these millionaires?  This problem is important  because it kicked off the the study of secure multiparty computation.

Below is a picture of the protocol originally proposed by Yao.  Alice and Bob are the two millionaires and i and j are the private net worths of Alice and Bob respectively.  The protocol makes use of public key cryptography: Alice is assumed to be able to generate a public encryption key E_a() along with a private decryption key D_a().  To see that the protocol reveals who is richer, note that y_j = D_a(k) = x.  Thus w_j = x if j<= i and w_j = x+1 if j>i.  Showing that the protocol doesn’t reveal any information beyond who is richer is more challenging and is presented in detail in  the paper.

I should point out that this protocol takes exponential time and that this run time has been improved in subsequent papers.  However, there is a question about this problem I haven’t been able to answer.  In the case where there are n players, do we need private channels or cryptographic assumptions to solve the problem?  Are private channels needed even if we’re happy with a Monte Carlo solution?  I’ve seen several papers that remove cryptographic assumptions, but none that seem to remove the need for private channels.  Conversely, I’ve seen no papers that prove that private channels are necessary…