Paper 2016/500

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

Jong Hwan Park, Kwangsu Lee, and Dong Hoon Lee


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).

Available format(s)
Publication info
Preprint. MINOR revision.
identity-based encryptiontrapdoor subgroupRSA moduluspublic-key signature.
Contact author(s)
jhpark @ smu ac kr
2016-05-26: revised
2016-05-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jong Hwan Park and Kwangsu Lee and Dong Hoon Lee},
      title = {Efficient Identity-Based Encryption and Public-Key Signature from Trapdoor Subgroups},
      howpublished = {Cryptology ePrint Archive, Paper 2016/500},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.