Garbled circuit play a key role in secure computation, but existing implementations do not scale and are not modular. In this paper we present VMCrypt, a library for secure computation. This library introduces novel algorithms that, regardless of the circuit being garbled or its size, have a very small memory requirement and use no disk storage. By providing an API (Abstract Programming Interface), VMCrypt can be integrated into existing projects and customized without any modifications to its source code. We measured the performance of VMCrypt on several circuits with undreds of millions of gates. These are the largest scalable secure computations done to date.

Motivated by the problem of private DNA matching, we consider the design of efficient protocols for secure text processing. Here, informally, a party P1 holds a text T and a party P2 holds a pattern p and some additional information y, and P2 wants to learn {f(T,j,y)} for all locations j where p is found as a substring in T. (In particular, this generalizes the basic pattern matching problem.) We aim for protocols with full security against a malicious P2 that also preserve privacy against a malicious P1 (i.e., one-sided security). We show how to modify Yao's garbled circuit approach to obtain a protocol where the size of the garbled circuit is linear in the number of occurrences of p in T (rather than linear in $|T|$). Along the way we show a new keyword search protocol that may be of independent interest.

Reliable communication between parties in a network is a basic requirement for executing any protocol. Dolev [4] and Dolev et al. [5] showed that reliable communication is possible if and only if the communication network is sufficiently connected. Beimel and Franklin [1] showed that the connectivity requirement can be relaxed if some pairs of parties share authentication keys. That is, costly communication links can be replaced by authentication keys.In this work, we continue this line of research. We consider the scenario where there is a speciiic sender and a specific receiver. In this case, the protocol of [1] has no(n) rounds even if there is a single Byzantine processor. We present a more efficient protocol with round complexity of (n/t)o(t), where n is the number of processors in the network and t is an upper bound on the number of Byzantine processors in the network. Specifically, our protocol is polynomial when the number of Byzantine processors is O(1), and for every t its round complexity is bounded by 2O(n). The same improvements hold for reliable and private communication. The improved protocol is obtained by analyzing the properties of a "communication and authentication graph" that characterizes reliable communication.