TU Darmstadt / ULB / TUbiblio

A New Efficient Threshold Ring Signature Scheme based on Coding Theory

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

Kurzbeschreibung (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.

Typ des Eintrags: Artikel
Erschienen: 2010
Autor(en): Aguilar Melchor, C. ; Cayrel, Pierre-Louis ; Gaborit, Philippe ; Laguillaumie, F.
Art des Eintrags: Bibliographie
Titel: A New Efficient Threshold Ring Signature Scheme based on Coding Theory
Sprache: Deutsch
Publikationsjahr: Juni 2010
Titel der Zeitschrift, Zeitung oder Schriftenreihe: IEEE IT
Zugehörige Links:
Kurzbeschreibung (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.

ID-Nummer: TUD-CS-2010-18795
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
Hinterlegungsdatum: 30 Dez 2016 20:23
Letzte Änderung: 06 Feb 2020 13:50
PPN:
Zugehörige Links:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen