Cryptology ePrint Archive: Report 2018/042

Improved (Almost) Tightly-Secure Structure-Preserving Signatures

Charanjit S. Jutla and Miyako Ohkubo and Arnab Roy

Abstract: 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.

Category / Keywords: Structure preserving signatures, bilinear pairings, SXDH, Matrix-DDH, Groth-Sahai, Cramer-Shoup, QA-NIZK

Date: received 8 Jan 2018, last revised 31 Jan 2019

Contact author: csjutla at us ibm com, arnabr at gmail com, m ohkubo at nict go jp

Available format(s): PDF | BibTeX Citation

Note: Fixed a small bug.

Version: 20190131:201941 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]