A New Efficient Threshold Ring Signature Scheme based on Coding Theory

Aguilar Melchor, C. and Cayrel, Pierre-Louis and Gaborit, Philippe and Laguillaumie, F. :
A New Efficient Threshold Ring Signature Scheme based on Coding Theory.
In: IEEE IT
[Article] , (2010)

Abstract

Ring signatures were introduced by Rivest, Shamir and Tauman in 2001 [26]. 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 [8]. We propose in this article a generalisation of Stern’s code based identification (and signature) scheme [30] 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, it 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 [2] with complete proofs and definitions.

Optionen (nur für Redakteure)

View Item