Cryptology ePrint Archive: Report 2009/058

On Generalization of Cheon's Algorithm

Takakazu Satoh

Abstract: We consider a generalization of Cheon's algorithm on the strong Diffie-Hellman problem. More specifically, we consider the circumstance that p^k-1 has a small divisor for k>=3, where p is the order of group on which we consider the strong Diffie-Hellman problem. It seems that our algorithm is only effective for k=1, 2, that is, the original Cheon's algorithm.

Category / Keywords: public-key cryptography / strong Diffie-Hellman problem

Publication Info: None.

Date: received 4 Feb 2009, last revised 11 Oct 2010

Contact author: satohcgn at mathpc-satoh math titech ac jp

Available formats: PDF | BibTeX Citation

Note: The exponent in (5) and the proof of Lemma 2 are corrected. The author would like to thank Dr. Sungwook Kim for pointing out them.

Version: 20101011:080005 (All versions of this report)

Discussion forum: Show discussion | Start new discussion