Cryptology ePrint Archive: Report 2020/477

Partially Structure-Preserving Signatures: Lower Bounds, Constructions and More

Essam Ghadafi

Abstract: 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 these schemes messages are scalars from $\Z^n_p$ instead of being source 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. They 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 signature schemes and structure-preserving ones.

Category / Keywords: public-key cryptography / Digital Signatures, Bilinear Groups, Lower Bounds, Structure-Preserving

Date: received 23 Apr 2020, last revised 28 Apr 2020

Contact author: essam ghadafi at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200428:154232 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]