Paper 2017/025
Improved Structure Preserving Signatures under Standard Bilinear Assumptions
Charanjit S. Jutla and Arnab Roy
Abstract
We show that the recent structure-preserving signature (SPS) scheme of Kiltz, Pan and Wee [CRYPTO 2015], provably secure under the standard bilinear pairings group assumption SXDH, can be improved to have one less group element and one less pairing product equation in the signature verification step. Our improved SPS scheme only requires six group elements (five in one group, and one in the other), and two pairing product equations for verification. The number of pairing product equations is optimal, as it matches a known lower bound of Abe et al [CRYPTO 2011]. The number of group elements in the signature also approaches the known lower bound of four for SXDH assumption. Further, while the earlier scheme had a security reduction which incurred a security loss that is quadratic in number of queries $Q$, our novel security reduction incurs only a $Q \log{Q}$ factor loss in security. Structure-preserving signatures are used pervasively in group signatures, group encryptions, blind signatures, proxy signatures and many other anonymous credential applications. Our work directly leads to improvements in these schemes. Moreover, the improvements are usually of a higher multiplicative factor order, as these constructions use Groth-Sahai NIZK proofs for zero-knowledge verification of pairing-product equations. We also give our construction under the more general and standard $\D_k$-MDDH (Matrix-DDH) assumption. The signature size in our scheme is $3k+2$ elements in one group, and one element in the other. The number of pairing product equations required for verification is only $2k$, whereas the earlier schemes required at least $2k+1$ equations.
Metadata
- Available format(s)
- Publication info
- Published by the IACR in PKC 2017
- Keywords
- QA-NIZKSXDHMDDHgroup signaturesblind signaturesCramer-Shoup encryption
- Contact author(s)
-
csjutla @ us ibm com
arnabr @ gmail com - History
- 2017-01-13: received
- Short URL
- https://ia.cr/2017/025
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/025, author = {Charanjit S. Jutla and Arnab Roy}, title = {Improved Structure Preserving Signatures under Standard Bilinear Assumptions}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/025}, year = {2017}, url = {https://eprint.iacr.org/2017/025} }