Cayrel, Pierre-Louis ; Véron, Pascal ; Yousfi Alaoui, Sidi Mohamed el (2010)
A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem.
SAC2010
Konferenzveröffentlichung, Bibliographie
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 ; Yousfi Alaoui, Sidi Mohamed el |
| Art des Eintrags: | Bibliographie |
| Titel: | A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem |
| Sprache: | Deutsch |
| Publikationsjahr: | August 2010 |
| Buchtitel: | Proceedings of the Seventeenth Workshop on Selected Areas in Cryptography(SAC2010) |
| Veranstaltungsort: | SAC2010 |
| Zugehörige Links: | |
| 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. |
| Freie Schlagworte: | Secure Data |
| ID-Nummer: | TUD-CS-2010-0188 |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra LOEWE LOEWE > LOEWE-Zentren LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt |
| Hinterlegungsdatum: | 30 Dez 2016 20:23 |
| Letzte Änderung: | 06 Aug 2021 17:49 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum