Cinderella: Turning Shabby X.509 Certificates into Elegant Anonymous Credentials with the Magic of Verifiable Computation

Antoine Delignat-Lavaud, Cédric Fournet, Markulf Kohlweiss, Bryan Parno

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Despite advances in security engineering, authentication in applications such as email and the Web still primarily relies on the X.509 public key infrastructure introduced in 1988. This PKI has many issues but is nearly impossible to replace. Leveraging recent progress in verifiable computation, we propose a novel use of existing X.509 certificates and infrastructure. Instead of receiving and validating chains of certificates, our applications receive and verify proofs of their knowledge, their validity, and their compliance with application policies. This yields smaller messages (by omitting certificates), stronger privacy (by hiding certificate contents), and stronger integrity (by embedding additional checks, e.g. for revocation). X.509 certificate validation is famously complex and error-prone, as it involves parsing ASN.1 data structures and interpreting them against diverse application policies. To manage this diversity, we propose a new format for writing application policies by composing X.509 templates, and we provide a template compiler that generates C code for validating certificates within a given policy. We then use the Geppetto cryptographic compiler to produce a zero-knowledge verifiable computation scheme for that policy. To optimize the resulting scheme, we develop new C libraries for RSA-PKCS#1 signatures and ASN.1 parsing, carefully tailored for cryptographic verifiability. We evaluate our approach by providing two
real-world applications of verifiable computation: a drop-in replacement for certificates within TLS, and access control for the Helios voting protocol. For TLS, we support fine-grained validation policies, with revocation checking and selective disclosure of certificate contents, effectively turning X.509 certificates into anonymous credentials. For Helios, we obtain additional privacy and verifiability guarantees for voters equipped with X.509 certificates, such as those readily available from some national ID cards.
Original languageEnglish
Title of host publicationIEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016
Place of PublicationSan Jose, CA, United States
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages20
ISBN (Electronic)978-1-5090-0824-7
ISBN (Print)978-1-5090-0825-4
Publication statusPublished - 2016
Event2016 IEEE Symposium on Security and Privacy - The Fairmont, San Jose, CA, United States
Duration: 23 May 201625 May 2016


Conference2016 IEEE Symposium on Security and Privacy
Country/TerritoryUnited States
CitySan Jose, CA
Internet address


Dive into the research topics of 'Cinderella: Turning Shabby X.509 Certificates into Elegant Anonymous Credentials with the Magic of Verifiable Computation'. Together they form a unique fingerprint.

Cite this