Compact Structure-Preserving Signatures with Almost Tight Security

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 presen...

Full description

Saved in:
Bibliographic Details
Published in:Journal of cryptology 2023-10, Vol.36 (4), Article 37
Main Authors: Abe, Masayuki, Hofheinz, Dennis, Nishimaki, Ryo, Ohkubo, Miyako, Pan, Jiaxin
Format: Article
Language:English
Subjects:
Coding and Information Theory
Combinatorics
Communications Engineering
Computational Mathematics and Numerical Analysis
Computer Science
Cryptography
Networks
Parameters
Partitioning
Probability Theory and Stochastic Processes
Queries
Research Article
Security
Signatures
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0933-2790
1432-1378
DOI:10.1007/s00145-023-09477-z