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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Digital SignaturesBilinear GroupsLower BoundsStructure-Preserving
Contact author(s)
essam ghadafi @ gmail com
History
2020-04-28: revised
2020-04-28: received
See all versions
Short URL
https://ia.cr/2020/477
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/477,
      author = {Essam Ghadafi},
      title = {Partially Structure-Preserving Signatures: Lower Bounds, Constructions and More},
      howpublished = {Cryptology ePrint Archive, Paper 2020/477},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/477}},
      url = {https://eprint.iacr.org/2020/477}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.