Jefferson's Wheel

I went to a very interesting meeting at Darmstadt: CROSSING – Where Quantum Physics, Cryptography, System Security and Software Engineering meet. Lots more diversity than my typical computer security meeting, including a lively debate on quantum physics and superfluid vacuum theory between Nicolas Grisin (founder of ID Quantique and Ross Anderson. Interesting to learn that China is building a huge quantum key distribution network.

I gave a talk on Multi-Party Computation for the Masses:

CROSSING is a 12-year project funded by the German Science Foundation (with reviews every 4 years). Gives some context to US funding agencies that talk about long-range visionary projects with 5-year timelines.

Several SRGers were at IEEE Symposium on Security and Privacy (“Oakland” in San Jose).

Yuchen Zhou presented his work on Understanding and Monitoring Embedded Web Scripts. Yuchen graduated with his PhD the day before the conference, and will be joining Palo Alto Networks.

Samee Zahur is a co-author (along with Benjamin Kreuter, who is an “in-progress UVa PhD student” diverted by Google, and several researchers from Microsoft Research) on the paper, Geppetto: Versatile Verifiable Computation, which was presented by Bryan Parno.

Samee also presented a poster on Obliv-C.

Weilin Xu presented a poster on Automatically Evading Classifiers

It was also great to see SRG alums Yan Huang (who is not at Indiana University, and was a co-author on the paper about ObliVM), Jon McCune (who is now working on trusted computing at Google) and Adrienne Felt (who was the keynote speaker for the W2SP workshop, and gave a very interesting talk about user-facing security design and experiments in Google Chrome; Adrienne’s first paper was in W2SP 2008 when she was an undergraduate at UVa).

Surprisingly, it is possible to reduce the data needed for a garbled gate to only two ciphertexts per gate, while preserving free xors. The scheme for doing that is described in our paper, Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates by Samee Zahur and Mike Rosulek and David Evans (now available on eprint).

Abstract. The well-known classical constructions of garbled circuits use four ciphertexts per gate, although various methods have been proposed to reduce this cost. The best previously known methods for optimizing AND gates (two ciphertexts; Pinkas et al., ASIACRYPT 2009) and XOR gates (zero ciphertexts; Kolesnikov & Schneider, ICALP 2008) were incompatible, so most implementations used the best known method compatible with free-XOR gates (three ciphertexts; Kolesnikov & Schneider, ICALP 2008). In this work we show how to simultaneously garble AND gates using two ciphertexts and XOR gates using zero ciphertexts, resulting in smaller garbled circuits than any prior scheme. The main idea behind our construction is to break an AND gate into two half-gates — AND gates for which one party knows one input. Each half-gate can be garbled with a single ciphertext, so our construction uses two ciphertexts for each AND gate while being compatible with free-XOR gates. The price for the reduction in size is that the evaluator must perform two cryptographic operations per AND gate, rather than one as in previous schemes. We experimentally demonstrate that our garbling scheme leads to an overall decrease in time (up to 25%), bandwidth (up to 33%), and energy use (up to 20%) over several benchmark applications. We also initiate a study of lower bounds for garbled gate size, and show that our construction is optimal for a large class of garbling schemes encompassing all known practical garbling techniques.

Yan Huang, who completed his PhD in 2012 and then was a post-doc at the University of Maryland, is now an Assistant Professor at Indiana University. See his IU faculty page and personal blog. IU is the home of several well-known security researchers including
Jean Camp, Steven Myers and XioFeng Wang, as well as one of my favorite authors, Douglas Hofstadter.

Samee Zahur passed in PhD Proposal on Abstractions for Data Oblivious Programs. The abstract is:

While many recent papers have demonstrated the feasibility of secure computation for various interesting applications, such techniques have not yet been widely adopted outside of the research community. In the thesis proposed here, we try to reduce one aspect of this entry barrier: software abstractions. We motivate the problem by showing how secure computation necessarily requires redesigning of even simple software abstractions such as language control structures and data structures. First, we propose a new language that can be easily extended by other researchers for purposes of their investigations. Then, we propose new constructions for common data structures that are efficient in this execution model. Finally, we propose to develop new optimizations for ORAM structures to enable faster computations in the RAM model. Our preliminary investigations are already showing promising results. We have implemented a prototype compiler for our new language that provides significantly higher flexibility compared to existing systems. We demonstrate this flexibility by showing that our language allows implementation of various library-based features that have, in the past, always used compiler modifications in other languages. We have also shown constructions of data structures that can provide over 10x speed improvement even on small data sizes.

Congratulations to Samee on successfully presenting his PhD Proposal. Samee will be spending the summer at Microsoft Research (Redmond).

I gave a keynote talk at the Applied Multi-Party Computation workshop at Microsoft Research Redmond on Multi-Party Computation in 2029: Boom, Bust, or Bonanza?. Despite the risk of being proved horribly wrong in 15 years, my slides are here (also available as [PPTX] and as a video):

There are well-written summaries of the talk by Mahnush Movahedi and Mahdi Zamani and the Aarhus Crypto Group.

Our paper on symmetric cut-and-choose is now available. The paper will be presented at CRYPTO 2013 in August.

Abstract. Beginning with the work of Lindell and Pinkas, researchers have proposed several protocols for secure two-party computation based on the cut-and-choose paradigm. In existing instantiations of this paradigm, one party generates k garbled circuits; some fraction of those are “checked” by the other party, and the remaining fraction are evaluated. We introduce here the idea of symmetric cut-and-choose protocols, in which both parties generate k circuits to be checked by the other party. The main advantage of our technique is that k can be reduced by a factor of 3 while attaining the same statistical security level as in prior work. Since the number of garbled circuits dominates the costs of the protocol, especially as larger circuits are evaluated, our protocol is expected to run up to 3 times faster than existing schemes. Preliminary experiments validate this claim.

Full paper (16 pages): [PDF]

Samee Zahur and I have written a paper on Circuit Structures for Improving Efficiency of Security and Privacy Tools. The paper explores ways to design static circuits (as used in garbled circuit protocols and symbolic execution, among other things) to provide reasonable efficiency for algorithms that use common data structures like arrays. By taking advantage of somewhat predictable access patterns, as well as batching, our circuit structures are able to provide operations with amortized cost that is polylogarithmic in the size of the data structure (in contrast to naive approaches that would require effectively copying the entire data structure for each operation). Samee will present the paper at the IEEE Symposium on Security and Privacy (“Oakland”) in San Francisco in May.

Full paper (15 pages): [PDF]
Project: MightBeEvil.com/netlist

Code: http://github.com/samee/netlist

I was interviewed on Gary McGraw’s Silver Bullet podcast.

Gary and Dave discuss the founding of the Interdisciplinary Major in Computer Science (BA) at UVa and why a broad approach to Computer Science and Computer Security is a good idea, why data privacy gets short shrift in the United States, why people think (for no apparent reason) that their mobile devices are secure, groceries, David’s research on Secure Computation, and the Udacity project. They close out their discussion with a story about David’s trip to the World Cup in Korea and a choice between GEB and scheme.

You can download the podcast from http://www.cigital.com/silver-bullet/show-076/.

Our paper on strengthening secure computation protocols to resist stronger adversaries is now available:

Yan Huang, Jonathan Katz, and David Evans. Quid Pro Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution. In 33rd IEEE Symposium on Security and Privacy (“Oakland” 2012), San Francisco, CA. 20-23 May 2012. [PDF, 13 pages]

Yan Huang will present the paper at the Oakland conference (which will be held in San Francisco for the first time, after being in Berkeley/Oakland for the first 32 years!) in May.

Abstract: Known protocols for secure two-party computation that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party’s input. Correctness of the honest party’s output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing dramatically stronger security guarantees.

Full paper (13 pages): [PDF]
Project site: MightBeEvil.com