**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

[ Cryptology ePrint archive ]