Mesh Signatures
How to Leak a Secret with Unwitting and Unwilling Participants

By Xavier Boyen.

In Advances in Cryptology (EUROCRYPT 2007), volume 4515 of Lecture Notes in Computer Science, pages 210-227. Springer, 2007.


We introduce the mesh signature primitive as an anonymous signature that borrows from ring signatures, but with added modularity and a much richer language for expressing signer ambiguity. The language can represent complex access structures, and in particular allows individual signature components to be replaced with modular certificate chains. As a result, withholding one's public key from view is no longer a shield against being named as a possible cosignatory; and hence, a mesh signature may be used as a ring signature substitute with compulsory enrollment.

We give an efficient construction based on bilinear maps in the common random string model. Our mesh signatures have linear size, achieve everlasting perfect anonymity, and as a special case induce the most efficient and first unconditionally anonymous ring signatures without random oracles or trusted setup authorities. We prove non-repudiation from a mild extension of the SDH assumption, which we introduce and justify meticulously.


- published paper (PS) (PDF) (also accessible from the publisher) © IACR
- full version (PS) (PDF)
- presentation slides (HTML)


  author = {Xavier Boyen},
  title = {Mesh Signatures},
  booktitle = {Advances in Cryptology---EUROCRYPT 2007},
  series = {Lecture Notes in Computer Science},
  volume = {4515},
  pages = {210--227},
  publisher = {Berlin: Springer-Verlag},
  year = {2007},
  note = {Available at \url{}}

Unless indicated otherwise, these documents are Copyright © Xavier Boyen; all rights reserved in all countries.
Back to Xavier's homepage