Cryptology ePrint Archive: Report 2017/905

A Ring Signature of size $\Theta(\sqrt[3]{n})$ without Random Oracles

Alonso González

Abstract: Ring signatures, introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), allow to sign a message on behalf of a set of users (called a ring) while guaranteeing authenticity, i.e. only members of the ring can produce valid signatures, and anonymity, i.e. signatures hide the actual signer. In terms of efficiency, the shortest ring signatures are of size $\Theta(\log n)$, where $n$ is the size of the ring, and are due to Groth and Kohlweiss (EUROCYPT 2015) and Libert et al. (EUROCRYPT 2016). But both schemes are proven secure in the random oracle model. Without random oracles the most efficient construction remains the one of Chandran et al. (ICALP 2007) with a signature of size $\Theta(\sqrt{n})$.

In this work we construct a ring signature of size $\Theta(\sqrt[3]{n})$ without random oracles. Our construction uses bilinear groups and we prove its security under the permutation pairing assumption, introduced by Groth and Lu (ASIACRYPT 2007).

Category / Keywords: Ring Signature, Non-Interactive Zero-Knowledge Proofs

Date: received 19 Sep 2017, last revised 30 Sep 2017

Contact author: alonso gonzalez at ens-lyon fr

Available format(s): PDF | BibTeX Citation

Note: Correction of some typos

Version: 20170930:061149 (All versions of this report)

Short URL: ia.cr/2017/905

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]