Vista Equipo: A distinguisher for high rate McEliece cryptosystems

A distinguisher for high rate McEliece cryptosystems

The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field....

Descripción completa

Detalles Bibliográficos
Autores Principales:	Faugère, Jean-Charles, Gauthier-Umanã, Valérie, Otmani, Ayoub, Perret, Ludovic, Tillich, Jean-Pierre
Formato:	Capítulo de libro (Book Chapter)
Lenguaje:	Inglés (English)
Publicado:	IEEE 2011
Materias:	Cryptography Vectors Equations Decoding Generators
Acceso en línea:	https://repository.urosario.edu.co/handle/10336/28909 https://doi.org/10.1109/ITW.2011.6089437

id	ir-10336-28909
recordtype	dspace
spelling	ir-10336-289092020-08-28T15:50:33Z A distinguisher for high rate McEliece cryptosystems Un distintivo para los criptosistemas McEliece de alta velocidad Faugère, Jean-Charles Gauthier-Umanã, Valérie Otmani, Ayoub Perret, Ludovic Tillich, Jean-Pierre Cryptography Vectors Equations Decoding Generators The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GCD problem in polynomial-time provided that the codes have rates sufficiently large. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the dimension of the solution space of a linearized system deduced from a particular polynomial system describing a key-recovery. It turns out that experimentally this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the value of the dimension are provided for “generic” random, alternant, and Goppa code over any alphabet. Finally, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes. 2011-12-01 2020-08-28T15:50:04Z info:eu-repo/semantics/bookPart info:eu-repo/semantics/publishedVersion ISBN: 978-1-4577-0438-3 EISBN: 978-1-4577-0437-6 https://repository.urosario.edu.co/handle/10336/28909 https://doi.org/10.1109/ITW.2011.6089437 eng info:eu-repo/semantics/restrictedAccess application/pdf IEEE 2011 IEEE Information Theory Workshop
institution	EdocUR - Universidad del Rosario
collection	DSpace
language	Inglés (English)
topic	Cryptography Vectors Equations Decoding Generators
spellingShingle	Cryptography Vectors Equations Decoding Generators Faugère, Jean-Charles Gauthier-Umanã, Valérie Otmani, Ayoub Perret, Ludovic Tillich, Jean-Pierre A distinguisher for high rate McEliece cryptosystems
description	The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GCD problem in polynomial-time provided that the codes have rates sufficiently large. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the dimension of the solution space of a linearized system deduced from a particular polynomial system describing a key-recovery. It turns out that experimentally this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the value of the dimension are provided for “generic” random, alternant, and Goppa code over any alphabet. Finally, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes.
format	Capítulo de libro (Book Chapter)
author	Faugère, Jean-Charles Gauthier-Umanã, Valérie Otmani, Ayoub Perret, Ludovic Tillich, Jean-Pierre
author_facet	Faugère, Jean-Charles Gauthier-Umanã, Valérie Otmani, Ayoub Perret, Ludovic Tillich, Jean-Pierre
author_sort	Faugère, Jean-Charles
title	A distinguisher for high rate McEliece cryptosystems
title_short	A distinguisher for high rate McEliece cryptosystems
title_full	A distinguisher for high rate McEliece cryptosystems
title_fullStr	A distinguisher for high rate McEliece cryptosystems
title_full_unstemmed	A distinguisher for high rate McEliece cryptosystems
title_sort	distinguisher for high rate mceliece cryptosystems
publisher	IEEE
publishDate	2011
url	https://repository.urosario.edu.co/handle/10336/28909 https://doi.org/10.1109/ITW.2011.6089437
_version_	1676708406479552512
score	11,382149

A distinguisher for high rate McEliece cryptosystems

Ejemplares similares