Paper 2016/500

Efficient Identity-Based Encryption and Public-Key Signature from Trapdoor Subgroups

Jong Hwan Park, Kwangsu Lee, and Dong Hoon Lee

Abstract

We present a new Identity-Based Encryption (IBE) scheme from a trapdoor subgroup of $\mathbb{Z}^*_{n}$ for an RSA modulus $n$. In a trapdoor subgroup of $\mathbb{Z}^*_{n}$, a subgroup order is hidden and can be used as a trapdoor. Our IBE scheme is efficient in both performance and space. Compared to practical pairing-based IBE schemes, ours is more efficient particularly in terms of computational performance. Following Naor's observation, we also suggest a new Public-Key Signature (PKS) scheme from a trapdoor subgroup of $\mathbb{Z}^*_{n}$. A favorable feature of our PKS scheme is that signing algorithm is exponentiation-free and requires only one modular inversion. This enables our PKS scheme to provide the fastest signing, compared to practical signature schemes such as RSA and ECDSA. We prove the security of our schemes in the random oracle model under new computational hardness problems that arguably hold in the trapdoor subgroup of $\mathbb{Z}^*_{n}$.

Note: Since our manuscript has been revealed at ePrint Archive, we have received several analysis from Marc Joye, Jung Yeon Hwang, and Olivier Sanders. All of them show that our schemes are all broken and only the inverse structure in a trapdoor subgroup of $\mathbb{Z}^*_{n}$ is not enough. We put the analysis by Marc Joye in the last part of this manuscript. Thus, it still remains an open problem to construct an IBE scheme over an RSA modulus (or to show impossibility result).