**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# Considerations for Rank-based Cryptosystems

Abstract

Cryptosystems based on rank metric codes have been considered as an alternative to McEliece cryptosystems due to the relative difficulty of solving the rank syndrome decoding problem. Generic attacks have recently seen several improvements, notably in the work of Gaborit et al., who give an improved algorithm using linearized polynomials which yields a polynomial time algorithm for certain parameters. On the structural side, many of the proposals for cryptosystems based on Gabidulin codes have proven to be weak, following an attack by Overbeck in 2001. Of the Gabidulin based systems managing to resist Overbeck's attack, several were recently broken by Horlemann-Trautmann et al. using an attack based on finding the elements of rank one in some extended code. In this paper, we extend the polynomial time algorithm of Gaborit using the same underlying idea as Horlemann-Trautmann et al., and then demonstrate how codes with implicit structural weakness may be exploited, even if the explicit structure is not determined. We use this attack to break a Gabidulin code based cryptosystem which has so far resisted structural attacks.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (31)

Related publications (33)

Related MOOCs (13)

Decoding methods

In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, such as a binary symmetric channel. is considered a binary code with the length ; shall be elements of ; and is the distance between those elements. One may be given the message , then ideal observer decoding generates the codeword .

Polynomial

In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1. Polynomials appear in many areas of mathematics and science.

Code

In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication channel or storage in a storage medium. An early example is an invention of language, which enabled a person, through speech, to communicate what they thought, saw, heard, or felt to others. But speech limits the range of communication to the distance a voice can carry and limits the audience to those present when the speech is uttered.

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 2)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algor ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...