We developed and are constantly improving on Charm, an extensible framework for rapidly prototyping cryptographic systems. Charm provides a number of features that explicitly support the development of new protocols, including: support for modular composition of cryptographic building blocks, infrastructure for developing interactive protocols, and an extensive library of re-usable code. Our framework also provides a series of specialized tools that enable different cryptosystems to interoperate.
We implemented over forty cryptographic schemes using Charm, including several new ones that to our knowledge have never been built in practice. Our modular architecture includes a built-in benchmarking module to compare the performance of Charm primitives to existing C implementations. Our framework shows that in many cases our techniques result in an order of magnitude decrease in code size, while inducing an acceptable performance impact.
Lastly, the Charm framework is freely available to the research community and to date, we have developed a large, active user base.
Project Webpage: http://charm-crypto.com
AutoBatch: Machine-Generated Algorithms, Proofs and Software for the Batch Verification of Digital Signature Schemes
As devices everywhere increasingly communicate with each other, many security applications will require low-bandwidth signatures that can be processed quickly. Pairing-based signatures can be very short, but are often costly to verify. Fortunately, they also tend to have efficient batch verification algorithms. Finding these batching algorithms by hand, however, can be tedious and error prone.
We address this by presenting AutoBatch, an automated tool for generating batch verification code in either Python or C++ from a high level representation of a signature scheme. AutoBatch outputs both software and, for transparency, a LaTeX file describing the batching algorithm and arguing that it preserves the unforgeability of the original scheme.
We tested AutoBatch on over a dozen pairing-based schemes to demonstrate that a computer could find competitive batching solutions in a reasonable amount of time. Indeed, it proved highly competitive. In particular, it found an algorithm that is significantly faster than a batching algorithm from Eurocrypt 2010. Another novel contribution is that it handles cross-scheme batching, where it searches for a common algebraic structure between two distinct schemes and attempts to batch them together.
AutoBatch is a useful tool for cryptographic designers and implementors, and to our knowledge, it is the first attempt to outsource to machines the design, proof writing and implementation of signature batch verification schemes.
Cloudsourcing: Automatically Enabling Expensive Cryptographic Algorithms on Lightweight Mobile Devices
There has been an explosion in new forms of cryptography in the past few decades. These advances are not simply new schemes of the same type, but rather entirely new paradigms of protecting the confidentiality and integrity of data. Examples include identity-based encryption, attribute-based encryption, functional encryption over regular languages, and broadcast encryption.
Much of this novel research has been made possible by cryptography based on bilinear maps, or pairings. While pairing-based cryptography enables powerful and expressive cryptosystems, it often comes at a cost, as pairings tend to be time-consuming operations. Accordingly, there have been several research efforts in the past aimed at outsourcing some of this heavy computation to an untrusted yet computationally powerful entity, such as a cloud-based provider. A lightweight, trusted client can then complete decryption or signature verification without the cloud provider learning anything about the plaintext data or secret key material.
Up until now, finding the outsourced versions of cryptographic schemes has been done manually. This is often a tedious, long, and error-prone process. We address this by developing CloudSource. CloudSource aims to improve the state of the art by automating the process of outsourcing cryptographic schemes given only a high-level description of the scheme in a Scheme Description Language (SDL). The output is the outsourced version of the scheme in SDL, Python, and C++, as well as a proof showing the transformations used to obtain the outsourced version. We demonstrate the utility of this approach in a variety of pairing-based cryptosystems. Our results indicate that this solution shows promise as the next step in automating efficiency improvements to cryptographic schemes.
Zerocoin: An anonymity scheme for bitcoin
Bitcoin is the first e-cash system to see widespread adoption. While Bitcoin offers the potential for new types of financial interaction, it has significant limitations regarding privacy. Specifically, because the Bitcoin transaction log is completely public, users' privacy is protected only through the use of pseudonyms. Zerocoin is a cryptographic extension to Bitcoin that augments the protocol to allow for fully anonymous currency transactions. It uses standard cryptographic assumptions and does not introduce new trusted parties, or otherwise change the security model of Bitcoin.