Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download
Contributor : Benoit Libert Connect in order to contact the contributor
Submitted on : Tuesday, July 24, 2018 - 12:50:40 PM
Last modification on : Monday, May 16, 2022 - 4:58:02 PM
Long-term archiving on: : Thursday, October 25, 2018 - 1:53:34 PM


Files produced by the author(s)



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⟩



Record views


Files downloads