International Association
for Cryptologic Research

Revocable identity-based encryption (RIBE) is an extension of IBE that supports a key revocation mechanism, which is 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. So 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, no construction of lattice-based R(H)IBE schemes with DKER are known.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 without DKER, 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 enables us to achieve the hierarchal feature without relying on the key re-randomization property.

Since May (Crypto’02) revealed the vulnerability of the small CRT-exponent RSA using Coppersmith’s lattice-based method, several papers have studied the problem and two major improvements have been made. (1) Bleichenbacher and May (PKC’06) proposed an attack for small $$d_q$$ d q when the prime factor p is significantly smaller than the other prime factor q ; the attack works for $$p<N^{0.468}$$ p < N 0.468 . (2) Jochemsz and May (Crypto’07) proposed an attack for small $$d_p$$ d p and $$d_q$$ d q when the prime factors p and q are balanced; the attack works for $$d_p, d_q<N^{0.073}$$ d p , d q < N 0.073 . Even a decade has passed since their proposals, the above two attacks are still considered as the state of the art, and no improvements have been made thus far. A novel technique seems to be required for further improvements since it seems that the attacks have been studied with all the applicable techniques for Coppersmith’s methods proposed by Durfee–Nguyen (Asiacrypt’00), Jochemsz–May (Asiacrypt’06), and Herrmann–May (Asiacrypt’09, PKC’10). Since it seems that the attacks have been studied with all the applicable techniques for Coppersmith’s methods proposed by Durfee–Nguyen (Asiacrypt’00), Jochemsz–May (Asiacrypt’06), and Herrmann–May (Asiacrypt’09, PKC’10), improving the previous results seem technically hard. In this paper, we propose two improved attacks on the small CRT-exponent RSA: a small $$d_q$$ d q attack for $$p<N^{0.5}$$ p < N 0.5 (an improvement of Bleichenbacher–May’s) and a small $$d_p$$ d p and $$d_q$$ d q attack for $$d_p, d_q < N^{0.122}$$ d p , d q < N 0.122 (an improvement of Jochemsz–May’s). The latter result is also an improvement of our result in the proceeding version (Eurocrypt ’17); $$d_p, d_q < N^{0.091}$$ d p , d q < N 0.091 . We use Coppersmith’s lattice-based method to solve modular equations and obtain the improvements from a novel lattice construction by exploiting useful algebraic structures of the CRT-RSA key generation equation. We explicitly show proofs of our attacks and verify the validities by computer experiments. In addition to the two main attacks, we also propose small $$d_q$$ d q attacks on several variants of RSA.