TU Darmstadt / ULB / TUbiblio

A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem

Cayrel, Pierre-Louis ; Véron, Pascal ; Alaoui, Sidi Mohamed El Yousfi :
A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem.
Proceedings of the Seventeenth Workshop on Selected Areas in Cryptography(SAC2010)
[ Konferenzveröffentlichung] , (2010)

Kurzbeschreibung (Abstract)

At CRYPTO’93, Stern proposed a 3-pass code-based identification scheme with a cheating probability of 2/3. In this paper, we propose a 5-pass code-based protocol with a lower communication complexity, allowing an impersonator to succeed with only a probability of 1/2. Furthermore, we propose to use double-circulant construction in order to dramatically reduce the size of the public key. The proposed scheme is zero-knowledge and relies on an NP-complete coding theory problem (namely the q-ary Syndrome Decoding problem). The parameters we suggest for the instantiation of this scheme take into account a recent study of (a generalization of) Stern’s information set decoding algorithm, applicable to linear codes over arbitrary fields Fq; the public data of our construction is then 4 Kbytes, whereas that of Stern’s scheme is 15 Kbytes for the same level of security. This provides a very practical identification scheme which is especially attractive for light-weight cryptography.

Typ des Eintrags: Konferenzveröffentlichung
Erschienen: 2010
Autor(en): Cayrel, Pierre-Louis ; Véron, Pascal ; Alaoui, Sidi Mohamed El Yousfi
Titel: A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem
Sprache: Deutsch
Kurzbeschreibung (Abstract):

At CRYPTO’93, Stern proposed a 3-pass code-based identification scheme with a cheating probability of 2/3. In this paper, we propose a 5-pass code-based protocol with a lower communication complexity, allowing an impersonator to succeed with only a probability of 1/2. Furthermore, we propose to use double-circulant construction in order to dramatically reduce the size of the public key. The proposed scheme is zero-knowledge and relies on an NP-complete coding theory problem (namely the q-ary Syndrome Decoding problem). The parameters we suggest for the instantiation of this scheme take into account a recent study of (a generalization of) Stern’s information set decoding algorithm, applicable to linear codes over arbitrary fields Fq; the public data of our construction is then 4 Kbytes, whereas that of Stern’s scheme is 15 Kbytes for the same level of security. This provides a very practical identification scheme which is especially attractive for light-weight cryptography.

Buchtitel: Proceedings of the Seventeenth Workshop on Selected Areas in Cryptography(SAC2010)
Freie Schlagworte: Secure Data
Fachbereich(e)/-gebiet(e): LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
LOEWE > LOEWE-Zentren
20 Fachbereich Informatik
LOEWE
Veranstaltungsort: SAC2010
Hinterlegungsdatum: 30 Dez 2016 20:23
ID-Nummer: TUD-CS-2010-0188
Verwandte URLs:
Export:

Optionen (nur für Redakteure)

Eintrag anzeigen Eintrag anzeigen