The l-th power Diffie-Hellman problem and the l-th root Diffie-Hellman problem

Abstract

There are many variants of the computational Diffie-Hellman problem that are necessary to provide security of many cryptographic schemes. Two of them are the square Diffie-Hellman problem and the square root Diffie-Hellman problem. Recently, the first and third authors proved that these two problems are polynomial-time equivalent under a certain condition (Roh and Hahn in Des Codes Cryptogr 62(2): 179-187, 2011). In this paper, we generalize this result. We introduce the l-th power Diffie-Hellman problem and the l-th root Diffie-Hellman problem and show that these two problems are polynomial-time equivalent for l = O(log p) under a condition similar to that of Roh and Hahn (2011), where p is the order of the underlying group.