Discrete Logarithm Problem with Auxiliary Inputs

Abstract

The modern cryptography has been developed based on mathematical hard problems. For example, it is considered hard to solve the discrete logarithm problem~(DLP). The DLP is required to solve $\alpha$ for given $g, g^\alpha$, where $G = \langle g \rangle$. It is well-known that the lower bound complexity to solve the DLP in the generic group model is $\Omega(p^{1/2})$~(EUROCRYPT 97, Shoup), where $p$ is the prime order of the group $G$. However, if the problem is given with auxiliary informations, then it can be solved faster than $O(p^{1/2})$. In the former of the thesis, we deal with the problem called discrete logarithm problem with the auxiliary inputs~(DLPwAI). The DLPwAI is a problem required to solve $\alpha$ for given $g, g^\alpha, \dots, g^{\alpha^d}$. The state-of-art algorithm to solve this problem is Cheon's algorithm which solves the problem in the case of $d

p\pm 1$.

In the thesis, we propose a new method to solve the DLPwAI which reduces to find a polynomial with small value sets. As a result, we solved the DLPwAI when $g^{\alpha^k}$ were given, where $k$ is an element of multiplicative subgroup of ${\mathbb Z}_{p-1}^{\times}$.

In the later of the thesis, we try to solve the DLP with the pairing inversion problem. If one has an efficient algorithm to solve the pairing inversion, then it can be used to solve the DLP. We focus on how to reduce the complexity of the pairing inversion problem by reducing the size of the final exponentiation in the pairing computation. As a result, we obtained the lower bound of the size of the final exponentiation.