Résumé
Ring signatures were introduced by Rivest, Shamir, and Tauman in 2001. These signatures allow a signer to anonymously authenticate a message on behalf of a group of his choice. This concept was then extended by Bresson, Stern, and Szydlo into t-out-of-N (threshold) ring signatures in 2002. We propose in this article a generalization of Stern's code-based identification (and signature) scheme to design a practical t-out-of-N threshold ring signature scheme. The size of the resulting signatures is in O(N) and does not depend on t, contrary to most of the existing protocols. Our scheme is existentially unforgeable under a chosen message attack in the random oracle model assuming the hardness of the minimum distance problem, is unconditionally source hiding, has a very short public key and has an overall 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). This paper is an extended version of a paper published in the conference PQCrypto 2008, with complete proofs and definitions.