International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Aikaterini Mitrokotsa , University of St. Gallen, Switzerland
Sayantan Mukherjee , Indian Institute of Technology, Jammu, India
Mahdi Sedaghat , Cosic, KU Leuven
Daniel Slamanig , Universität der Bundeswehr München: Munich, Germany
Jenit Tomy , University of St. Gallen, Switzerland
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
Abstract: 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.
BibTeX
@inproceedings{pkc-2024-33794,
  title={Threshold Structure Preserving Signatures: Strong and Adaptive Security under Standard Assumptions},
  publisher={Springer-Verlag},
  author={Aikaterini Mitrokotsa and Sayantan Mukherjee and Mahdi Sedaghat and Daniel Slamanig and Jenit Tomy},
  year=2024
}