Pairing-based proof systems and applications to anonymous credentials


October 21, 2010


Melissa Chase


Pairing based cryptography has resulted in a number of breakthrough results, including some major developments in the area of zero knowledge proof systems. A zero knowledge proof system allows a party to prove that a statement is true without revealing any other information. Zero knowledge proofs are used in everything from identification protocols (allowing a party to prove that he is who he claims to be) and encryption schemes with stronger security properties, to securing protocols against malicious adversaries, and constructing privacy preserving systems. It has been shown that zero knowledge proofs can be constructed from a variety of number theoretic assumptions (or, more generally from any trapdoor permutation); however most of these constructions are complex and inefficient. In ’06 Groth, Ostrovsky, an Sahai showed how to construct proof systems based on pairings which have much more structure than traditional constructions; this structure in turn has since been shown to result in proof systems with greater efficiency, stronger security, and more functionality. This talk will describe at a high level how pairings allows us to construct zero knowledge proofs with more structure than traditional tools, and then discuss some of the applications that take advantage of this structure, focusing on applications to privacy and anonymity.


Melissa Chase

Melissa Chase is a postdoctoral researcher in the Cryptography group at MSR. Her research focuses on provably secure privacy. Before joining Microsoft she completed a Ph.D. in Computer Science at Brown University. She has worked in a number of different areas, including anonymous credentials, electronic cash, and attribute based encryption as well as the more theoretical problems areas of general non-interactive zero knowledge and Universally Composable security.