Date de l'exposé : 15 septembre 2017
identity-based encryption with rank metric
Code-based cryptography has a long history, almost as long
as the history of public-key encryption (PKE). While we can construct
almost all primitives from codes such as PKE, signature, group signature
etc, it is a long standing open problem to construct an identity-based
encryption from codes. We solve this problem by relying on codes with
rank metric.
The concept of identity-based encryption (IBE), introduced by Shamir in
1984, allows the use of users’ identifier information such as email as public
key for encryption. There are two problems that makes the design of IBE
extremely hard: the requirement that the public key can be an arbitrary
string and the possibility to extract decryption keys from the public
keys. In fact, it took nearly twenty years for the problem of designing an
efficient method to implement an IBE to be solved. The known methods
of designing IBE are based on different tools: from elliptic curve pairings
by Sakai, Ohgishi and Kasahara and by Boneh and Franklin in 2000 and
2001 respectively; from the quadratic residue problem by Cocks in 2001;
and finally from the Learning-with-Error problem by Gentry, Peikert,
and Vaikuntanathan in 2008.
Among all candidates for post-quantum cryptography, there only exist
thus lattice-based IBE. In this paper, we propose a new method, based on
the hardness of learning problems with rank metric, to design the first
code-based IBE scheme. In order to overcome the two above problems
in designing an IBE scheme, we first construct a rank-based PKE, called
RankPKE, where the public key space is dense and thus can be obtained
from a hash of any identity. We then extract a decryption key from any
public key by constructing an trapdoor function which relies on RankSign
- a signature scheme from PQCrypto 2014.
In order to prove the security of our schemes, we introduced a new prob-
lem for rank metric: the Rank Support Learning problem (RSL). A high
technical contribution of the paper is devoted to study in details the
hardness of the RSL problem.