Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Generalized Algorithm for DLP with Auxiliary Inputs

Speaker  Jung Hee Cheon

Affiliation  Seoul National University

Host  Kristin Lauter

Duration  01:17:46

Date recorded  29 June 2010

The DLP with auxiliary inputs is to find α when gαi (i=0,1,2,…,d) as well as g, gα are given. Recently, numerous cryptosystems are designed on a weaker variant of this problem. One example is the strong Diffie-Hellman problem. It has been shown that the complexity of this problem is lower than the original DLP by upto √ d group operations when p-1 or p+1 has an appropriate divisor. In this talk, we present a generalization of this algorithm, which can be applied even when p-1 and p+1$ are almost prime. We also discuss how many parameters are susceptible to this attack.

©2010 Microsoft Corporation. All rights reserved.
> Generalized Algorithm for DLP with Auxiliary Inputs