TU Darmstadt / ULB / TUbiblio

A New Efficient Threshold Ring Signature Scheme based on Coding Theory

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

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.

Item Type: Article
Erschienen: 2010
Creators: Aguilar Melchor, C. and Cayrel, Pierre-Louis and Gaborit, Philippe and Laguillaumie, F.
Title: A New Efficient Threshold Ring Signature Scheme based on Coding Theory
Language: German
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.

Journal or Publication Title: IEEE IT
Divisions: Zentrale Einrichtungen > University and State Library Darmstadt (ULB)
Zentrale Einrichtungen
Date Deposited: 30 Dec 2016 20:23
Identification Number: TUD-CS-2010-18795
Related URLs:
Export:

Optionen (nur für Redakteure)

View Item View Item