Paper 2012/285

Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions

Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, and Miyako Ohkubo

Abstract

This paper presents efficient structure-preserving signature schemes based on assumptions as simple as Decision-Linear. We first give two general frameworks for constructing fully secure signature schemes from weaker building blocks such as two-tier signatures and random-message secure signatures. They can be seen as refinements of the Even-Goldreich-Micali framework, and preserve many desirable properties of the underlying schemes such as constant signature size and structure preservation. We then instantiate them based on simple (i.e., not q-type) assumptions over symmetric and asymmetric bilinear groups. The resulting schemes are structure-preserving and yield constant-size signatures consisting of 11 to 17 group elements, which compares favorably to existing schemes relying on q-type assumptions for their security.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Structure-preserving signaturesOne-time signaturesGroth-Sahai proof systemRandom message attacks
Contact author(s)
abe masayuki @ lab ntt co jp
History
2012-06-27: revised
2012-05-29: received
See all versions
Short URL
https://ia.cr/2012/285
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/285,
      author = {Masayuki Abe and Melissa Chase and Bernardo David and Markulf Kohlweiss and Ryo Nishimaki and Miyako Ohkubo},
      title = {Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/285},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/285}},
      url = {https://eprint.iacr.org/2012/285}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.