Trapdoor one way functions associated with exponentiation

Download Now Date Added: Mar 2011
Format: PDF

This paper shows that if exponentiation b = Xk in groups of finite field units or B = [k]X in elliptic curves is considered as encryption of X with exponent k treated as symmetric key, then the decryption or the computation of X from b (respectively B) can be achieved in polynomial time with a high probability under random choice of k. Since given X and b or B the problem of computing the discrete log k is not known to have a polynomial time solution, the exponentiation has a trapdoor property associated with it.