TY - GEN
T1 - Identity-based encryption from codes with rank metric
AU - Gaborit, Philippe
AU - Hauteville, Adrien
AU - Phan, Duong Hieu
AU - Tillich, Jean Pierre
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2017.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - 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 problem 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.
AB - 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 problem 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.
KW - Code-based cryptography
KW - IBE
KW - PKE
KW - Rank metric
U2 - 10.1007/978-3-319-63697-9_7
DO - 10.1007/978-3-319-63697-9_7
M3 - Conference contribution
AN - SCOPUS:85028466590
SN - 9783319636962
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 194
EP - 224
BT - Advances in Cryptology – CRYPTO 2017 - 37th Annual International Cryptology Conference, Proceedings
A2 - Katz, Jonathan
A2 - Shacham, Hovav
PB - Springer Verlag
T2 - 37th Annual International Cryptology Conference, CRYPTO 2017
Y2 - 20 August 2017 through 24 August 2017
ER -