Paper 2015/961

Short Structure-Preserving Signatures

Essam Ghadafi

Abstract

We construct a new structure-preserving signature scheme in the efficient Type-III asymmetric bilinear group setting with signatures shorter than all existing schemes. Our signatures consist of 3 group elements from the first source group and therefore have shorter size than all existing schemes as existing ones have at least one component of the signature in the second source group whose elements bit size is at least double their first group counterparts. Besides enjoying short signatures, our scheme is fully re-randomizable which is a useful property for many applications. Our result also constitutes a proof that the impossibility of unilateral structure-preserving signatures in the Type-III setting result of Abe et al.~(Crypto 2011) does not apply to constructions in which the message space is dual in both source groups. Besides checking the well-formedness of the message, verifying a signature in our scheme requires checking $2$ Pairing Product Equations (PPE) and require the evaluation of only $5$ pairings in total which matches the best existing scheme and outperforms many other existing ones. Reducing the number of pairings in the verification equations is very important when combining structure-preserving signature schemes with Groth-Sahai proofs as the number of pairings required for verifying Groth-Sahai proofs for PPE equations grows linearly with the number of pairing monomials in the source equations. We give some examples of how using our new scheme instead of existing ones improves the efficiency of some existing cryptographic protocols such as direct anonymous attestation and group signature related constructions.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. CT-RSA 2016
Contact author(s)
e ghadafi @ ucl ac uk
History
2015-11-25: revised
2015-10-05: received
See all versions
Short URL
https://ia.cr/2015/961
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/961,
      author = {Essam Ghadafi},
      title = {Short Structure-Preserving Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2015/961},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/961}},
      url = {https://eprint.iacr.org/2015/961}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.