abstract.tex

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).