How intractable is the modified chosen discrete logarithm assumption?

Abstract

Abstract In modern cryptologic theory, the design of cryptographic protocols is often based on the assumed difficulty of number theoretic problems. Especially, in order to prove the security of a cryptographic protocol based upon the assumed difficulty of a problem, a very important role is played by the legitimacy (as concerns the security of the cryptographic protocol) of that cryptographic assumption. Recently, Kurosawa, Ogata, and Tsujii proposed a new cryptographic assumption, the Chosen Discrete Logarithm Assumption (CDLA), and showed that any language in NP has a four‐move, zero‐knowledge interactive proof (ZKIP) under the CDLA. In this paper, we define the modified CDLA and consider its legitimacy. Our principal result (that the modified CDLA is not a legitimate cryptographic assumption) follows from a theoretical analysis of expected polynomial‐time algorithms and the concrete construction of an algorithm based on the Artin conjecture.