Paper 2011/187

Accelerating ID-based Encryption based on Trapdoor DL using Pre-computation

Hyung Tae Lee, Jung Hee Cheon, and Jin Hong


The existing identity-based encryption (IBE) schemes based on pairings require pairing computations in encryption or decryption algorithm and it is a burden to each entity which has restricted computing resources in mobile computing environments. An IBE scheme (MY-IBE) based on a trapdoor DL group for RSA setting is one of good alternatives for applying to mobile computing environments. However, it has a drawback for practical use, that the key generation algorithm spends a long time for generating a user's private key since the key generation center has to solve a discrete logarithm problem. In this paper, we suggest a method to reduce the key generation time of the MY-IBE scheme, applying modified Pollard rho algorithm using significant pre-computation (mPAP). We also provide a rigorous analysis of the mPAP for more precise estimation of the key generation time and consider the parallelization and applying the tag tracing technique to reduce the wall-clock running time of the key generation algorithm. Finally, we give a parameter setup method for an efficient key generation algorithm and estimate key generation time for practical parameters from our theoretical analysis and experimental results on small parameters. Our estimation shows that it takes about two minutes using pre-computation for about 50 days with 27 GB storage to generate one user's private key using the parallelized mPAP enhanced by the tag tracing technique with 100 processors.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Identity-based EncryptionTrapdoor DL GroupsDiscrete LogarithmPre-computation
Contact author(s)
htsm1138 @ snu ac kr
2012-01-12: last of 4 revisions
2011-04-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hyung Tae Lee and Jung Hee Cheon and Jin Hong},
      title = {Accelerating ID-based Encryption based on Trapdoor DL using Pre-computation},
      howpublished = {Cryptology ePrint Archive, Paper 2011/187},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.