Paper 2024/445

Threshold Structure-Preserving Signatures: Strong and Adaptive Security under Standard Assumptions

Aikaterini Mitrokotsa, University of St. Gallen, St. Gallen, Switzerland
Sayantan Mukherjee, Indian Institute of Technology, Jammu, India
Mahdi Sedaghat, COSIC, KU Leuven, Leuven, Belgium
Daniel Slamanig, Research Institute CODE, Universität der Bundeswehr München
Jenit Tomy, University of St. Gallen, St. Gallen, Switzerland

Structure-preserving signatures (SPS) have emerged as an important cryptographic building block, as their compatibility with the Groth-Sahai (GS) NIZK framework allows to construct protocols under standard assumptions with reasonable efficiency. Over the last years there has been a significant interest in the design of threshold signature schemes. However, only very recently Crites et al. (ASIACRYPT 2023) have introduced threshold SPS (TSPS) along with a fully non-interactive construction. While this is an important step, their work comes with several limitations. With respect to the construction, they require the use of random oracles, interactive complexity assumptions and are restricted to so called indexed Diffie-Hellman message spaces. Latter limits the use of their construction as a drop-in replacement for SPS. When it comes to security, they only support static corruptions and do not allow partial signature queries for the forgery. In this paper, we ask whether it is possible to construct TSPS without such restrictions. We start from an SPS from Kiltz, Pan and Wee (CRYPTO 2015) which has an interesting structure, but thresholdizing it requires some modifications. Interestingly, we can prove it secure in the strongest model (TS-UF-1) for fully non-interactive threshold signatures (Bellare et al., CRYPTO 2022) and even under fully adaptive corruptions. Surprisingly, we can show the latter under a standard assumption without requiring any idealized model. All known constructions of efficient threshold signatures in the discrete logarithm setting require interactive assumptions and idealized models. Concretely, our scheme in type III bilinear groups under the SXDH assumption has signatures consisting of 7 group elements. Compared to the TSPS from Crites et al. (2 group elements), this comes at the cost of efficiency. However, our scheme is secure under standard assumptions, achieves strong and adaptive security guarantees and supports general message spaces, i.e., represents a drop-in replacement for many SPS applications. Given these features, the increase in the size of the signature seems acceptable even for practical applications.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2024
Threshold SignaturesStructure-Preserving Signatures
Contact author(s)
katerina mitrokotsa @ unisg ch
csayantan mukherjee @ gmail com
ssedagha @ esat kuleuven be
daniel slamanig @ unibw de
jenit tomy @ unisg ch
2024-03-15: approved
2024-03-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aikaterini Mitrokotsa and Sayantan Mukherjee and Mahdi Sedaghat and Daniel Slamanig and Jenit Tomy},
      title = {Threshold Structure-Preserving Signatures: Strong and Adaptive Security under Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/445},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.