Cryptology ePrint Archive: Report 2017/524

Compact Structure-preserving Signatures with Almost Tight Security

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

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

Category / Keywords: Structure-preserving signatures, Tight reduction, Adaptive partitioning

Original Publication (in the same form): IACR-CRYPTO-2017

Date: received 4 Jun 2017, last revised 1 Jul 2017

Contact author: nanacov at gmail com, dennis hofheinz@kit edu, ryo nishimaki@gmail com, omiyako@apricot ocn ne jp, jiaxin pan@kit edu

Available format(s): PDF | BibTeX Citation

Version: 20170701:151903 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]