In this paper we provide the first provably secure blind ring signature construction that does not rely on random oracles, which solves an open problem raised by Herranz and Laguillaumie at ISC 2006. We present different instantiations all of which are round-optimal (i.e.\ have a two-move signing protocol), yield sub-linear size signatures, and meet strong security requirements. In order to realize our constructions efficiently, we construct a sub-linear size set membership proof which works in the different bilinear group settings, which may be of independent interest.
As a secondary contribution, we show how to generically combine our set membership proof with any secure signature scheme meeting some conditions to obtain ring signatures whose security does not rely on random oracles. All our constructions work over the efficient prime-order bilinear group setting and yield signatures of sub-linear size. In addition, our constructions meet strong security requirements: namely, anonymity holds under full key exposure and unforgeability holds against insider-corruption. Finally, we provide some example instantiations of the generic construction.Category / Keywords: ring signatures, blind ring signatures, standard model Original Publication (with major differences): IMA Cryptography and Coding 2013 Date: received 22 Sep 2013, last revised 26 Sep 2013 Contact author: eg6947 at googlemail com Available format(s): PDF | BibTeX Citation Note: Full paper Version: 20130926:184556 (All versions of this report) Discussion forum: Show discussion | Start new discussion