You are looking at a specific version 20140214:154243 of this paper. See the latest version.

Paper 2014/095

Unified, Minimal and Selectively Randomizable Structure-Preserving Signatures

Masayuki Abe and Jens Groth and Miyako Ohkubo and Mehdi Tibouchi

Abstract

We construct a structure-preserving signature scheme that is selectively randomizable and works in all types of bilinear groups. We give matching lower bounds showing that our structure-preserving signature scheme is optimal with respect to both signature size and public verification key size. State of the art structure-preserving signatures in the asymmetric setting consist of 3 group elements, which is known to be optimal. Our construction preserves the signature size of 3 group elements and also at the same time minimizes the verification key size to 1 group element. Depending on the application, it is sometimes desirable to have strong unforgeability and in other situations desirable to have randomizable signatures. To get the best of both worlds, we introduce the notion of selective randomizability where the signer may for specific signatures provide randomization tokens that enable randomization. Our structure-preserving signature scheme unifies the different pairing-based settings since it can be instantiated in both symmetric and asymmetric groups. Since previously optimal structure-preserving signatures had only been constructed in asymmetric bilinear groups this closes an important gap in our knowledge. Having a unified signature scheme that works in all types of bilinear groups is not just conceptually nice but also gives a hedge against future cryptanalytic attacks. An instantiation of our signature scheme in an asymmetric bilinear group may remain secure even if cryptanalysts later discover an efficiently computable homomorphism between the source groups.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in TCC 2014
Keywords
Structure-preserving signaturesautomorphic signaturesselective randomizability
Contact author(s)
mehdi tibouchi @ normalesup org
History
2014-02-14: received
Short URL
https://ia.cr/2014/095
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.