Logarithmic size ring signatures without random oracles

Ring signatures enable a user to anonymously sign a message on behalf of group of users. In this paper, we propose the first ring signature scheme whose size is O(log2N), where N is the number of users in the ring. We achieve this result by improving Chandran et al.'s ring signature scheme presented at ICALP 2007. Our scheme uses a common reference string and non-interactive zero-knowledge proofs. The security of our scheme is proven without requiring random oracles.