Miyako Ohkubo

In structure-preserving cryptography, every building block shares the same bilinear groups. These groups must be generated for a specific, a priori fixed security level, and thus, it is vital that the security reduction in 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.

We propose a simple framework for evaluating the performance of pairing-based cryptographic schemes for various types of curves and parameter settings. The framework, which we call ‘Opcount’, enables the selection of an appropriate curve and parameters by estimating the performance of a cryptographic scheme from a pseudo-code describing the cryptographic scheme and an implementation-information database that records the performance of basic operations in curves targeted for evaluation. We apply Opcount to evaluate and compare the computational efficiency of several structure-preserving signature schemes that involve tens of pairing products in their signature verification. In addition to showing the usefulness of Opcount, our experiments also reveal the overlooked importance of taking account of the properties of underlying curves when optimizing computations and demonstrate the impact of tight security reductions.