ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

A Generalized Attack on Discrete Logarithm Problems with Auxiliary Inputs

Speaker: Sung-Wook Kim
Date, Time: Fri, 27 Aug 2010 15:00

Let $g$ be an element of prime order $p$ in an abelian group $G$ and let $\alpha \in \mathbf{F}_p$. The strong Discrete Logarithm problem with $d$ auxiliary inputs ($d$-SDL) is the problem to compute $\alpha$ when $g, g^{\alpha}, \dots, g^{\alpha^d}$ are given. In Eurocrypt 2006, Cheon gave an algorithm to solve $d$-SDL when $p-1$ or $p+1$ has an appropriate divisor. In 2008, Satoh generalized this algorithm into more general $d$ using an embedding to $GL(n,\mathbf{F}_p)$. In this talk we consider the generalization of Cheon's algorithm. We present Satoh's algorithm and several open problems for this topic.

Back to the top of this page