Cryptology ePrint Archive: Report 2019/1153

Stronger Security and Constructions of Multi-Designated Verifier Signatures

Ivan Damgård and Helene Haagh and Rebekah Mercer and Anca Nițulescu and Claudio Orlandi and Sophia Yakoubov

Abstract: Off-the-Record (OTR) messaging is a two-party message authentication protocol that also provides plausible deniability: there is no record that can later convince a third party what messages were actually sent. To extend OTR to group messaging we need to consider issues that are not present in the 2-party case. In group OTR (as in two-party OTR), the sender should be able to authenticate (or sign) his messages so that group members can verify who sent a message (that is, signatures should be unforgeable, even by group members). Also as in the two-party case, we want the off-the-record property: even if some verifiers are corrupt and collude, they should not be able to prove the authenticity of a message to any outsider. Finally, we need consistency, meaning that a corrupt sender cannot create confusion in the group as to what he said: if any group member accepts a signature, then all of them do.

To achieve these properties it is natural to consider Multi-Designated Verifier Signatures (MDVS), which intuitively seem to target exactly the properties we require. However, existing literature defines and builds only limited notions of MDVS, where (a) the off-the-record property (referred to as source hiding) only holds when all verifiers could conceivably collude, and (b) the consistency property is not considered.

The contributions of this paper are two-fold: stronger definitions for MDVS, and new constructions meeting those definitions. We strengthen source-hiding to support any subset of corrupt verifiers, and give the first formal definition of consistency.

We give several constructions of our stronger notion of MDVS: one from generic standard primitives such as pseudorandom functions, pseudorandom generators, key agreement and NIZKs; one from specific instances of these primitives (for concrete efficiency); and one from functional encryption. The third construction requires an involved trusted setup step — including verification keys derived from a master secret — but this trusted setup buys us verifier-identity-based signing, for which such trusted setup is unavoidable. Additionally, in the third construction, the signature size can be made smaller by assuming a bound on colluding verifiers.

Category / Keywords: cryptographic protocols / signatures, designated verifier signatures, OTR messaging

Date: received 4 Oct 2019, last revised 27 May 2020

Contact author: ivan at cs au dk, orlandi at cs au dk, sophia yakoubov at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200527:065845 (All versions of this report)

Short URL: ia.cr/2019/1153


[ Cryptology ePrint archive ]