UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Structure-preserving signatures from type II pairings

Abe, M; Groth, J; Ohkubo, M; Tibouchi, M; (2014) Structure-preserving signatures from type II pairings. In: Garay, J and Gennaro, R, (eds.) Advances in Cryptology – CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I. (pp. 390 - 407). Springer Berlin Heidelberg: Berlin, Germany. Green open access

[thumbnail of Groth_Type2Sign.pdf]

Download (399kB) | Preview


We investigate structure-preserving signatures in asymmetric bilinear groups with an efficiently computable homomorphism from one source group to the other, i.e., the Type II setting. It has been shown that in the Type I and Type III settings, structure-preserving signatures need at least 2 verification equations and 3 group elements. It is therefore natural to conjecture that this would also be required in the intermediate Type II setting, but surprisingly this turns out not to be the case. We construct structure-preserving signatures in the Type II setting that only require a single verification equation and consist of only 2 group elements. This shows that the Type II setting with partial asymmetry is different from the other two settings in a way that permits the construction of cryptographic schemes with unique properties. We also investigate lower bounds on the size of the public verification key in the Type II setting. Previous work on structure-preserving signatures has explored lower bounds on the number of verification equations and the number of group elements in a signature but the size of the verification key has not been investigated before.We show that in the Type II setting it is necessary to have at least 2 group elements in the public verification key in a signature scheme with a single verification equation. Our constructions match the lower bounds so they are optimal with respect to verification complexity, signature sizes and verification key sizes. In fact, in terms of verification complexity, they are the most efficient structure preserving signature schemes to date. We give two structure-preserving signature schemes with a single verification equation where both the signatures and the public verification keys consist of two group elements each. One signature scheme is strongly existentially unforgeable, the other is fully randomizable. Having such simple and elegant structure-preserving signatures may make the Type II setting the easiest to use when designing new structure-preserving cryptographic schemes, and lead to schemes with the greatest conceptual simplicity.

Type: Proceedings paper
Title: Structure-preserving signatures from type II pairings
Event: Advances in Cryptology - CRYPTO 2014
Location: Santa Barbara, US
Dates: 2014-08-17 - 2014-08-21
ISBN-13: 9783662443705
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-662-44371-2_22
Publisher version: http://dx.doi.org/10.1007/978-3-662-44371-2_22
Language: English
Additional information: The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-44371-2_22.
Keywords: Structure-preserving signatures, Type II pairings, strong existential unforgeability, randomizability, lower bounds
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1448354
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item