Cryptology ePrint Archive: Report 2016/500

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

Jong Hwan Park and 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}$.

Category / Keywords: identity-based encryption, trapdoor subgroup, RSA modulus, public-key signature.

Date: received 22 May 2016, last revised 25 May 2016

Contact author: jhpark at smu ac kr

Available format(s): PDF | BibTeX Citation

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

Version: 20160526:022124 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]