CWI Cryptology Group

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.

Abstract: Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the belief that quantum algorithms are not helpful in this less structured setting. Famously, some isogeny constructions use the action of an ideal class group on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures. Previous works hence presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is infinite (in fact, not even compact) and non-commutative. We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signature and strong designated-verifier signature with non-delegatability constructions from standard assumptions corresponding to a generalised group action inverse problem.