DS09 - Liberté et sécurité de l’Europe, de ses citoyens et de ses résidents

Code-based Cryptography – CBCRYPT

Submission summary

In recent years, there has been a substantial amount of research on quantum computers. Such computers would be a major threat for all the
public key cryptosystems used in practice, since all these systems rely on the hardness of integer factoring or discrete logarithms, and
these problems are easy on a quantum computer. This has prompted the NIST to release at the end of last year a call for
standardizing quantum resistant alternatives to those cryptosystems. This call concerns all three major cryptographic primitives, namely public key cryptosytems, key exchange protocols and digital signature schemes.

The deadline for this call is November 30, 2017.
NIST expects to perform multiple rounds of evaluation, over a period of three to five years. The goal of this process is to select a number of acceptable candidate cryptosystems for standardization. The first round of evaluation will last approximatively twelve to eighteen months.
Before the second round, the submitters of the algorithms will have the option of providing updated optimized implementations and
to patch small deficiencies discovered during the evaluation process.

The most promising
techniques today for addressing this issue are code-based cryptography, lattice-based cryptography, mutivariate cryptography, and hash-based cryptography.
Our project will propose candidates to the NIST call for all three primitives.
We will consider two different, but related, techniques to achieve this purpose: the Hamming metric and the rank metric.
For both these techniques, schemes can be designed whose security relies
partially, sometimes solely, on the hardness of decoding problem, that is finding a word close, for the Hamming or rank metric, to some code (i.e. a vector space) over a finite alphabet.

Our project does not deal solely with the NIST call. We will also develop some other code-based solutions: these will be either primitives that are not mature enough to be proposed in the first NIST call or whose functionalities are not covered by the NIST call, such as
identity-based encryption, broadcast encryption, attribute based encryption or functional encryption.

A third goal of this project is of a more fundamental
nature: namely to lay firm
foundations for code-based cryptography by developing thorough and rigorous security proofs together with a set of algorithmic tools
for assessing the security of code-based cryptography.

More generally, the main objectives of the project are the following:
- NIST competition: submission and follow up of our proposals, cryptanalysis of concurrent schemes;
- Development of other basic and advanced code-based primitives;
- General study of the security of code-based schemes for the Hamming and rank metrics.

Project coordinator

Inria de Paris (Laboratoire public)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

Institut de Mathématiques de Bordeaux
LABORATOIRE D'INFORMATIQUE, DE TRAITEMENT DE L'INFORMATION ET DES SYSTÈMES - EA 4108
XLIM
Inria de Paris

Help of the ANR 593,568 euros
Beginning and duration of the scientific project: September 2017 - 48 Months

Useful links