Paper 2018/042

Improved (Almost) Tightly-Secure Structure-Preserving Signatures

Charanjit S. Jutla, Miyako Ohkubo, and Arnab Roy


Structure Preserving Signatures (SPS) allow the signatures and the messages signed to be further encrypted while retaining the ability to be proven valid under zero-knowledge. In particular, SPS are tailored to have structure suitable for Groth-Sahai NIZK proofs. More precisely, the messages, signatures, and verification keys are required to be elements of groups that support efficient bilinear-pairings (bilinear groups), and the signature verification consists of just evaluating one or more bilinear-pairing product equations. Since Groth-Sahai NIZK proofs can (with zero-knowledge) prove the validity of such pairing product equations, it leads to interesting applications such as blind signatures, group signatures, traceable signatures, group encryption, and delegatable credential systems. In this paper, we further improve on the SPS scheme of Abe, Hofheinz, Nishimaki, Ohkubo and Pan (CRYPTO 2017) while maintaining only an $O(\lambda)$-factor security reduction loss to the SXDH assumption. In particular, we compress the size of the signatures by almost 40%, and reduce the number of pairing-product equations in the verifier from fifteen to seven. Recall that structure preserving signatures are used in applications by encrypting the messages and/or the signatures, and hence these optimizations are further amplified as proving pairing-product equations in Groth-Sahai NIZK system is not frugal. While our scheme uses an important novel technique introduced by Hofheinz (EuroCrypt 2017), i.e., structure-preserving adaptive partitioning, our approach to building the signature scheme is different and this leads to the optimizations mentioned. Thus we make progress towards an open problem stated by Abe et al (CRYPTO 2017) to design more compact SPS-es with smaller number of group elements.

Note: Fixed a small bug.

Available format(s)
Publication info
Preprint. MINOR revision.
Structure preserving signaturesbilinear pairingsSXDHMatrix-DDHGroth-SahaiCramer-ShoupQA-NIZK
Contact author(s)
csjutla @ us ibm com
arnabr @ gmail com
m ohkubo @ nict go jp
2019-01-31: last of 2 revisions
2018-01-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charanjit S.  Jutla and Miyako Ohkubo and Arnab Roy},
      title = {Improved (Almost) Tightly-Secure Structure-Preserving Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/042},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.