Cryptology ePrint Archive: Report 2012/285

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

Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, 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.

Category / Keywords: public-key cryptography / Structure-preserving signatures, One-time signatures, Groth-Sahai proof system, Random message attacks

Date: received 21 May 2012, last revised 27 Jun 2012

Contact author: abe masayuki at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20120627:171015 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]