Talk starts at 2PM
Join online: https://cwi-cr.digitalsamba.com/cr_seminar
Title: Tightly Unique Signature Schemes in the Random Oracle Model via Hash-and-Subset-Sign
Abstract: Unique signatures are digital signature schemes, where each message has exactly one valid signature. The uniqueness property typically comes at a price: Most unique signature schemes are known to have a security loss at least linear in the number of signature queries when aiming for existential unforgeability under chosen message attacks (EUF-CMA) security, which was shown to be inherent in the standard model by Coron (EUROCRYPT 2002) for signature schemes where public keys are verifiable (i.e., where it can be efficiently checked whether a public key has unique signatures).
The only known tight unique signature schemes in literature that support verifiable public keys are variants of chain-based signatures (CRYPTO 2017, FC 2018, EUROCRYPT 2022), which achieve tight security in the random oracle model. To achieve constant security loss, however, these schemes require
log q calls of the random oracle to sign and verify, where q is an upper bound on the number of signatures computed using the scheme.
In this work, we provide the first tight unique signature scheme with verifiable public keys which requires only a constant number (namely, six) random oracle queries to sign and verify. Specifically, we provide a general transformation akin to hash-and-sign which transforms a signature scheme with much weaker security (a variant of random unforgeability) into an EUF-CMA secure scheme. Signatures of our resulting scheme consist of at most 3 sub-signatures in parallel. Towards achieving this construction we present a generic transformation, which we refer to as hash-and-subset-sign, that transforms any unique signature scheme satisfying the weak notion of random unforgeability under random message attacks tightly into an EUF-CMA secure unique signature scheme.
