Cryptology ePrint Archive: Report 2019/1153

Stronger Notions and Constructions for 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 protocol used to authenticate messages while also giving senders plausible deniability. Multi-Designated Verifier Signatures (MDVS) are a primitive that allows for OTR to be extended to handle group messaging. In group OTR, the sender wants the designated verifiers to be able to authenticate the messages (that is, the signature should be unforgeable), but even if some verifiers are corrupt and collude, they should not be able to prove authenticity to any outsiders (that is, the signature should be source-hiding). We additionally require consistency, meaning that if any one of the designated verifiers can verify an honestly produced signature, then all of them can.

The contributions of this paper are two-fold: stronger definitions, and new constructions meeting those definitions. Existing literature defines and builds limited notions of MDVS, where source-hiding only holds when all verifiers are corrupt. We strengthen source-hiding to support any subset of corrupt verifiers, and give the first formal definition of consistency.

We give two constructions of our stronger notion of MDVS: one from functional encryption, and one from standard primitives such as pseudorandom functions, pseudorandom generators, key agreement and NIZKs. The second construction has somewhat larger signatures, but does not require a trusted setup.

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

Date: received 4 Oct 2019, last revised 10 Oct 2019

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

Available format(s): PDF | BibTeX Citation

Version: 20191010:201826 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]