International Association for Cryptologic Research

International Association
for Cryptologic Research


Threshold Structure-Preserving Signatures

Elizabeth Crites , University of Edinburgh
Markulf Kohlweiss , University of Edinburgh and IOG
Bart Preneel , Cosic, KU Leuven, Belgium
Mahdi Sedaghat , Cosic, KU Leuven, Belgium
Daniel Slamanig , AIT Austrian Institute of Technology
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: Structure-preserving signatures (SPS) are an important building block for privacy-preserving cryptographic primitives, such as electronic cash, anonymous credentials, and delegatable anonymous credentials. In this work, we introduce the first threshold structure-preserving signature scheme (TSPS). This enables multiple parties to jointly sign a message, resulting in a standard, single-party SPS signature, and can thus be used as a replacement for applications based on SPS. We begin by defining and constructing SPS for indexed messages, which are messages defined relative to a unique index. We prove its security in the random oracle model under a variant of the generalized Pointcheval-Sanders assumption (PS). Moreover, we generalize this scheme to an indexed multi-message SPS for signing vectors of indexed messages, which we prove secure under the same assumption. We then formally define the notion of a TSPS and propose a construction based on our indexed multi-message SPS. Our TSPS construction is fully non-interactive, meaning that signers simply output partial signatures without communicating with the other signers. Additionally, signatures are short: they consist of 2 group elements and require 2 pairing product equations to verify. We prove the security of our TSPS under the security of our indexed multi-message SPS scheme. Finally, we show that our TSPS may be used as a drop-in replacement for UC-secure Threshold-Issuance Anonymous Credential (TIAC) schemes, such as Coconut, without the overhead of the Fischlin transform.
  title={Threshold Structure-Preserving Signatures},
  author={Elizabeth Crites and Markulf Kohlweiss and Bart Preneel and Mahdi Sedaghat and Daniel Slamanig},