Paper 2015/076

Fully Structure-Preserving Signatures and Shrinking Commitments

Masayuki Abe, Markulf Kohlweiss, Miyako Ohkubo, and Mehdi Tibouchi


Structure-preserving signatures are schemes in which public keys, messages, and signatures are all collections of source group elements of some bilinear groups. In this paper, we introduce fully structure-preserving signature schemes, with the additional requirement that even secret keys should be group elements. This new type of structure-preserving signatures allows for efficient non-interactive proofs of knowledge of the secret key and is useful in designing cryptographic protocols with strong security guarantees based on the simulation paradigm where the simulator has to extract the secret keys on-line. To gain efficiency, we construct shrinking structure-preserving trapdoor commitments. This is by itself an important primitive and of independent interest as it appears to contradict a known impossibility result. We argue that a relaxed binding property lets us circumvent the impossibility result while still retaining the usefulness of the primitive in important applications as mentioned above.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2015
digital signatures
Contact author(s)
abe masayuki @ lab ntt co jp
2015-02-10: received
Short URL
Creative Commons Attribution


      author = {Masayuki Abe and Markulf Kohlweiss and Miyako Ohkubo and Mehdi Tibouchi},
      title = {Fully Structure-Preserving Signatures and Shrinking Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2015/076},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.