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

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

Research output: Contribution to journalArticlepeer-review


This paper presents efficient structure-preserving signature schemes based on simple assumptions such as decisional linear. We first give two general frameworks for constructing fully secure signature schemes from weaker building blocks such as variations of one-time 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–14 group elements, which compares favorably to existing schemes whose security relies on q-type assumptions.
Original languageEnglish
Pages (from-to)833-878
Number of pages46
JournalJournal of Cryptology
Issue number4
Early online date8 Jul 2015
Publication statusPublished - 1 Oct 2016


Dive into the research topics of 'Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions'. Together they form a unique fingerprint.

Cite this