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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Masayuki Abe, NTT Secure Platform Laboratories, NTT Corporation
  • ,
  • Melissa Chase, Microsoft Research
  • ,
  • Bernardo David
  • ,
  • Markulf Kohlweiss, Microsoft Research Cambridge
  • ,
  • Ryo Nishimaki, NTT Secure Platform Laboratories, NTT Corporation
  • ,
  • Miyako Ohkubo, NSRI

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
JournalJournal of Cryptology
Pages (from-to)1-46
Number of pages46
Publication statusPublished - 2016

    Research areas

  • Extended random message attacks, Partially one-time signatures, Structure-preserving signatures, Tagged one-time signatures

See relations at Aarhus University Citationformats

ID: 96479573