International Association
for Cryptologic Research

Multi-signatures allow a given set of parties to cooperate in order to create a digital signature whose size is independent of the number of signers. At the same time, no other set of parties can create such a signature. While non-interactive multi-signatures are known (e.g. BLS from pairings), many popular multi-signature schemes such as MuSig2 (which are constructed from pairing-free discrete logarithm-style assumptions) require interaction. Such interactive multi-signatures have recently found practical applications e.g. in the cryptocurrency space. Motivated by classical and emerging use cases of such interactive multi-signatures, we introduce the first systematic treatment of interactive multi-signatures in the universal composability (UC) framework. Along the way, we revisit existing game-based security notions and prove that constructions secure in the game-based setting can easily be made UC secure and vice versa. In addition, we consider interactive multi-signatures where the signers must interact in a fixed pattern (so-called ordered multi-signatures). Here, we provide the first construction of ordered multi-signatures based on the one-more discrete logarithm assumption, whereas the only other previously known construction required pairings. Our scheme achieves a stronger notion of unforgeability, guaranteeing that the adversary cannot obtain a signature altering the relative order of honest signers. We also present the first formalization of ordered multi-signatures in the UC framework and again show that our stronger game-based definitions are equivalent to UC security.

Privacy-preserving blueprint schemes (Kohlweiss et al., EUROCRYPT'23) offer a mechanism for safeguarding user's privacy while allowing for specific legitimate controls by a designated auditor agent. These schemes enable users to create escrows encrypting the result of evaluating a function y=P(t,x), with P being publicly known, t a secret used during the auditor's key generation, and x the user's private input. Crucially, escrows only disclose the blueprinting result y=P(t,x) to the designated auditor, even in cases where the auditor is fully compromised. The original definition and construction only support the evaluation of functions P on an input x provided by a single user. We address this limitation by introducing updatable privacy-preserving blueprint schemes (UPPB), which enhance the original notion with the ability for multiple users to non-interactively update the private user input x while blueprinting. Moreover, UPPBs contain a proof that y is the result of a sequence of valid updates, while revealing nothing else about the private inputs {x_i} of updates. As in the case of privacy-preserving blueprints, we first observe that UPPBs can be realized via a generic construction for arbitrary predicates P based on FHE and NIZKs. Our main result is uBlu, an efficient instantiation for a specific predicate comparing the values x and t, where x is the cumulative sum of users' private inputs and t is a fixed private value provided by the auditor in the setup phase. This rather specific setting already finds interesting applications such as privacy-preserving anti-money laundering and location tracking, and can be extended to support more generic predicates. From the technical perspective, we devise a novel technique to keep the escrow size concise, independent of the number of updates, and reasonable for practical applications. We achieve this via a novel characterization of malleability for the algebraic NIZK by Couteau and Hartmann (CRYPTO’20) that allows for an additive update function.

<p>We study signatures well suited for sensitive applications (e.g. whistleblowing) where both the signer's anonymity and deniability are important. Two independent lines of work have tackled these two goals: ring signatures ensure the signer's anonymity (within a set of signers, called a ring), and — separately — multi designated verifier signatures ensure that all the intended recipients agree on whether a signature is valid, while maintaining the signer's deniability by preventing the intended recipients from convincing an outsider of the validity of the signature. In this paper, we introduce multi designated verifier ring signatures (MDVRS), which simultaneously offer both signer anonymity and deniability. This makes MDVRS uniquely suited for sensitive scenarios.</p><p>Following the blueprint of Damgård et al (TCC'20) for multi designated verifier signatures, we introduce provably simulatable designated verifier ring signatures (PSDVRS) as an intermediate building block which we then compile into an MDVRS. We instantiate PSDVRS in a concretely efficient way from discrete logarithm based sigma protocols, encryption and commitments.</p>

Ring signatures enable a signer to sign a message on behalf of a group anonymously, without revealing her identity. Similarly, threshold ring signatures allow several signers to sign the same message on behalf of a group; while the combined signature reveals that some threshold t of group members signed the message, it does not leak anything else about the signers’ identities. Anonymity is a central feature in threshold ring signature applications, such as whistleblowing, e-voting and privacy-preserving cryptocurrencies: it is often crucial for signers to remain anonymous even from their fellow signers. When the generation of a signature requires interaction, this is diffcult to achieve. There exist threshold ring signatures with non-interactive signing — where signers locally produce partial signatures which can then be aggregated — but a limitation of existing threshold ring signature constructions is that all of the signers must agree on the group on whose behalf they are signing, which implicitly assumes some coordination amongst them. The need to agree on a group before generating a signature also prevents others — from outside that group — from endorsing a message by adding their signature to the statement post-factum. We overcome this limitation by introducing extendability for ring signatures, same-message linkable ring signatures, and threshold ring signatures. Extendability allows an untrusted third party to take a signature, and extend it by enlarging the anonymity set to a larger set. In the extendable threshold ring signature, two signatures on the same message which have been extended to the same anonymity set can then be combined into one signature with a higher threshold. This enhances signers’ anonymity, and enables new signers to anonymously support a statement already made by others. For each of those primitives, we formalize the syntax and provide a meaningful security model which includes different flavors of anonymous extendability. In addition, we present concrete realizations of each primitive and formally prove their security relying on signatures of knowledge and the hardness of the discrete logarithm problem. We also describe a generic transformation to obtain extendable threshold ring signatures from same-message-linkable extendable ring signatures. Finally, we implement and benchmark our constructions.