A New Efficient Threshold Ring Signature Scheme Based on Coding Theory

Ring signatures were introduced by Rivest, Shamir and Tauman in 2001. Bresson, Stern and Szydlo extended the ring signature concept to t-out-of-N threshold ring signatures in 2002. We present in this paper a generalization of Stern's code based authentication (and signature) scheme to the case of t-out-of-N threshold ring signature. The size of our signature is in O(N) and does not depend on t. Our protocol is anonymous and secure in the random oracle model, it has a very short public key and has a complexity in O(N). This protocol is the first efficient code-based ring signature scheme and the first code-based threshold ring signature scheme. Moreover it has a better complexity than number-theory based schemes which have a complexity in O(Nt).