Paper 2011/131

Trapdoor oneway functions associated with exponentiation

Virendra Sule

Abstract

This paper shows that if exponentiation $b=X^{k}$ 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. This paper makes this property precise. Further the decryption problem is a special case of a general problem of solving equations in groups. Such equations lead to more such trapdoor one way functions when solvable in polynomial time. The paper considers single and two variable equations on above groups and determines their solvability.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Exponential functionelliptic curvesdivision polynomials
Contact author(s)
vrs @ ee iitb ac in
History
2011-03-18: received
Short URL
https://ia.cr/2011/131
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/131,
      author = {Virendra Sule},
      title = {Trapdoor oneway functions associated with exponentiation},
      howpublished = {Cryptology ePrint Archive, Paper 2011/131},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/131}},
      url = {https://eprint.iacr.org/2011/131}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.