Logarithmic-Size Ring Signatures With Tight Security from the DDH Assumption

Benoît Libert (1, 2, 3) , Thomas Peters (4, 5, 6) , Chen Qian (7)

1 CNRS - Centre National de la Recherche Scientifique
2 ARIC - Arithmetic and Computing
3 LIP - Laboratoire de l'Informatique du Parallélisme
4 FNRS - Fonds National de la Recherche Scientifique [Bruxelles]
5 ICTEAM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
6 UCL - Université Catholique de Louvain = Catholic University of Louvain
7 EMSEC - EMbedded SEcurity and Cryptography

Ring signatures make it possible for a signer to anonymously and, yet, convincingly leak a secret by signing a message while concealing his identity within a flexibly chosen ring of users. Unlike group signatures, they do not involve any setup phase or tracing authority. Despite a lot of research efforts in more than 15 years, most of their realizations require linear-size signatures in the cardinality of the ring. In the random oracle model, two recent constructions decreased the signature length to be only logarithmic in the number N of ring members. On the downside, their suffer from rather loose reductions incurred by the use of the Forking Lemma. In this paper, we consider the problem of proving them tightly secure without affecting their space efficiency. Surprisingly, existing techniques for proving tight security in ordinary signature schemes do not trivially extend to the ring signature setting. We overcome these difficulties by combining the Groth-Kohlweiss Σ-protocol (Eurocrypt'15) with dual-mode encryption schemes. Our main result is a fully tight construction based on the Decision Diffie-Hellman assumption in the random oracle model. By full tightness, we mean that the reduction's advantage is as large as the adversary's, up to a constant factor.

Mots clés: tight security; random oracles; anonymity; Ring signatures

Domaines: Cryptographie et sécurité [cs.CR]

Benoît Libert, Thomas Peters, Chen Qian. Logarithmic-Size Ring Signatures With Tight Security from the DDH Assumption. ESORICS 2018 - 23rd European Symposium on Research in Computer Security, Sep 2018, Barcelone, Spain. pp.288-308, ⟨10.1007/978-3-319-98989-1_15⟩. ⟨hal-01848134⟩