Paper 2018/420

Lattice-based Revocable (Hierarchical) IBE with Decryption Key Exposure Resistance

Shuichi Katsumata, Takahiro Matsuda, and Atsushi Takayasu

Abstract

Revocable identity-based encryption (RIBE) is an extension of IBE that supports a key revocation mechanism; an indispensable feature for practical cryptographic schemes. Due to this extra feature, RIBE is often required to satisfy a strong security notion unique to the revocation setting called decryption key exposure resistance (DKER). Additionally, hierarchal IBE (HIBE) is another orthogonal extension of IBE that supports key delegation functionalities allowing for scalable deployments of cryptographic schemes. Thus far, R(H)IBE constructions with DKER are only known from bilinear maps, where all constructions rely heavily on the so-called key re-randomization property to achieve the DKER and/or hierarchal feature. Since lattice-based schemes seem to be inherently ill-fit with the key re-randomization property, we currently do not know of any lattice-based R(H)IBE schemes with DKER. In this paper, we propose the first lattice-based RHIBE scheme with DKER without relying on the key re-randomization property, departing from all the previously known methods. We start our work by providing a generic construction of RIBE schemes with DKER, which uses as building blocks any two-level standard HIBE scheme and (weak) RIBE scheme without DKER. Based on previous lattice-based RIBE constructions, our result implies the first lattice-based RIBE scheme with DKER. Then, building on top of our generic construction, we construct the first lattice-based RHIBE scheme with DKER, by further exploiting the algebraic structure of lattices. To this end, we prepare a new tool called the level conversion keys, which allows us to achieve the hierarchal feature without relying on the key re-randomization property.

Note: In the previous version, the security game for RHIBE in Section 4 had an issue. Specifically, the condition of the initial check for an adversary's secret key reveal query was not sufficient, which admitted a generic attack on any scheme in a similar way to what we outlined in Remark 1. We have fixed it in the current version, and correspondingly updated Remark 1. We have also made a slight change in the challenger's response to an adversary's secret key generation query to improve clarity, and corrected some typos. We stress that the security proof of the proposed RHIBE scheme in Section 6 has not been changed since our proof was conducted by implicitly assuming the security game of the current version.