A New Efficient Threshold Ring Signature Scheme Based on Coding Theory

Abstract

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 <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$t$</tex></formula> -out-of- <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$N$</tex></formula> (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 <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$t$</tex> </formula> -out-of- <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$N$</tex></formula> threshold ring signature scheme. The size of the resulting signatures is in <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\cal O}(N)$</tex></formula> and does not depend on <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$t$</tex> </formula> , 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 <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\cal O}(N)$</tex></formula> . 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 <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\cal O}(Nt)$</tex></formula> . This paper is an extended version of a paper published in the conference PQCrypto 2008, with complete proofs and definitions.