Jung Hee Cheon

Trapdoor DL groups and their Applications

Jung Hee Cheon

In this talk, we will discuss new developments concerning trapdoor DL
groups and their instantiation in Z_N^*. At Eurocrypt'91, Maurer-Yacobi
proposed a trapdoor DL group in Z_N^* where N=pq is a product of two
primes and p-1 and q-1 are B-smooth. Without knowing the factorization
of N, the DLP on Z_N^* takes O(B log N/log B) using the Pollard (p-1)
 method. However, given the factorization as a trapdoor, it takes only
O(sqrt B log N/log B) time using the Pohlig-Hellman and Pollard rho methods.

In this work, we show that DL groups with trapdoors can be made more
practical via a recently developed memory-efficient DL algorithm with 
precomputation. We show the trade-off between the precomputation, the 
online computation and the memory usage. Further we discuss several
applications of Trapdoor DL groups including ID-based encryption without 
pairings. Finally, on a more applied note we suggest some specific 
parameter settings and their implications.

(Related Papers)
1) Paterson, Sriramkrishnan - "On the relations between non-interactive 
key distribution, identity-based encryption and trapdoor discrete log 
groups" http://dx.doi.org/10.1007/s10623-009-9278-y

2) Maurer, Yacobi - "Non-interactive Public-Key Cryptography"