Skip to main content

Research Repository

Advanced Search

Partially structure-preserving signatures: Lower bounds, constructions and more

Ghadafi, Essam


Essam Ghadafi
Senior Lecturer in Computer Science


In this work we first provide a framework for defining a large subset of pairing-based digital signature schemes which we call Partially Structure-Preserving Signature (PSPS) schemes. PSPS schemes are similar in nature to structure-preserving signatures with the exception that in PSPS schemes messages are scalars from Zp instead of being group elements. This class encompasses various existing schemes which have a number of desirable features which makes them an ideal building block for many privacy-preserving cryptographic protocols. Such schemes include the widely-used schemes of Camenisch-Lysyanskaya (CRYPTO 2004) and Pointcheval-Sanders (CT-RSA 2016). We then provide various impossibility and lower bound results for variants of this class. Our results include bounds for the signature and verification key sizes as well as lower bounds for achieving strong unforgeability. We also give a generic framework for transforming variants of PSPS schemes into structure-preserving ones. As part of our contribution, we also give a number of optimal PSPS schemes which may be of independent interest. Our results aid in understanding the efficiency of pairing-based signature schemes and show a connection between this class of schemes and structure-preserving ones.


Ghadafi, E. (in press). Partially structure-preserving signatures: Lower bounds, constructions and more

Conference Name 19th International Conference on Applied Cryptography and Network Security
Conference Location Kamakura, Japan
Start Date Jun 21, 2021
End Date Jun 24, 2021
Acceptance Date Mar 22, 2021
Online Publication Date Jun 21, 2021
Deposit Date Apr 6, 2021
Publisher Springer
Keywords Digital Signatures; Bilinear Groups; Lower Bounds; Structure- Preserving
Public URL

This file is under embargo due to copyright reasons.

Contact to request a copy for personal use.

You might also like

Downloadable Citations