Paper 2017/524

Compact Structure-preserving Signatures with Almost Tight Security

Masayuki Abe, Dennis Hofheinz, Ryo Nishimaki, Miyako Ohkubo, and Jiaxin Pan


In structure-preserving cryptography, every building block shares the same bilinear groups. These groups must be generated for a specific, a prior fixed security level, and thus it is vital that the security reduction of all involved building blocks is as tight as possible. In this work, we present the first generic construction of structure-preserving signature schemes whose reduction cost is independent of the number of signing queries. Its chosen-message security is almost tightly reduced to the chosen-plaintext security of a structure-preserving public-key encryption scheme and the security of Groth-Sahai proof system. Technically, we adapt the adaptive partitioning technique by Hofheinz (Eurocrypt 2017) to the setting of structure-preserving signature schemes. To achieve a structure-preserving scheme, our new variant of the adaptive partitioning technique relies only on generic group operations in the scheme itself. Interestingly, however, we will use non-generic operations during our security analysis. Instantiated over asymmetric bilinear groups, the security of our concrete scheme is reduced to the external Diffie-Hellman assumption with linear reduction cost in the security parameter, independently of the number of signing queries. The signatures in our schemes consist of a larger number of group elements than those in other non-tight schemes, but can be verified faster, assuming their security reduction loss is compensated by increasing the security parameter to the next standard level.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2017
Structure-preserving signaturesTight reductionAdaptive partitioning
Contact author(s)
nanacov @ gmail com
dennis hofheinz @ kit edu
ryo nishimaki @ gmail com
omiyako @ apricot ocn ne jp
jiaxin pan @ kit edu
2017-07-01: revised
2017-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Masayuki Abe and Dennis Hofheinz and Ryo Nishimaki and Miyako Ohkubo and Jiaxin Pan},
      title = {Compact Structure-preserving Signatures with Almost Tight Security},
      howpublished = {Cryptology ePrint Archive, Paper 2017/524},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.