Paper 2022/839

Structure-Preserving Threshold Signatures

Mahdi Sedaghat, imec-COSIC, KU Leuven, Leuven, Belgium
Daniel Slamanig, AIT Austrian Institute of Technology, Vienna, Austria
Markulf Kohlweiss, University of Edinburgh and IOHK, Edinburgh, UK
Bart Preneel, imec-COSIC, KU Leuven, Leuven, Belgium

The by now broadly accepted reliance of society on online services, led to a push for decentralization to mitigate the societal and technical risks caused by single points of failure (PoF). One such PoF are cryptographic keys. Thus there is renewed interest in threshold cryptography to distribute the generation and use of such keys. Structure-preserving signatures (SPS) are an important building block for privacy-preserving cryptographic protocols such as electronic cash and (delegatable) anonymous credentials. However, to date, no structure-preserving threshold signatures (SPTS) are available. This is unfortunate, as another PoF is centralized identity management, which could be mitigated by anonymous credentials. In this work we aim to close this gap by introducing a notion and constructions of (non-) interactive SPTS. While it is relatively easy to devise interactive SPTS supporting static corruptions, e.g., based on the SPS of Ghadafi (CT-RSA'16), constructing non-interactive SPTS is a much more delicate task. Due to their structural properties, starting from existing SPS does not yield secure schemes. Thus, we take a different path and first introduce the notion of message-indexed SPS, a variant of SPS that is parameterized by a message indexing function. Inspired by Pointcheval-Sanders (PS) signatures (CT-RSA'16) and the SPS of Ghadafi, we then present a message-indexed SPS, which is non-interactive threshold-friendly. We prove its security in the random oracle model based on a variant of the generalized PS assumption. Based on our message-indexed SPS we then propose the first non-interactive message-indexed SPTS, which we prove to be secure under adaptive corruption. Finally, we discuss applications of SPTS to privacy-preserving primitives.

Available format(s)
Public-key cryptography
Publication info
Threshold Signatures Structure-Preserving Signatures
Contact author(s)
ssedagha @ esat kuleuven be
daniel slamanig @ ait ac at
mkohlwei @ inf ed ac uk
bart preneel @ esat kuleuven be
2022-06-27: approved
2022-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mahdi Sedaghat and Daniel Slamanig and Markulf Kohlweiss and Bart Preneel},
      title = {Structure-Preserving Threshold Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/839},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.