TY - GEN

T1 - Solving DLP with auxiliary input over an elliptic curve used in TinyTate library

AU - Sakemi, Yumi

AU - Izu, Tetsuya

AU - Takenaka, Masahiko

AU - Yasuda, Masaya

PY - 2011

Y1 - 2011

N2 - The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α from G, αG, α dG in an additive cyclic group generated by G of prime order r and a positive integer d dividing r-1. The infeasibility of DLPwAI assures the security of some cryptographic schemes. In 2006, Cheon proposed a novel algorithm for solving DLPwAI. This paper shows our experimental results of Cheon's algorithm by implementing it with some speeding-up techniques. In fact, we succeeded to solve DLPwAI in a group with 128-bit order in 45 hours with a single PC on an elliptic curve defined over a prime finite field with 256-bit elements which is used in the TinyTate library.

AB - The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α from G, αG, α dG in an additive cyclic group generated by G of prime order r and a positive integer d dividing r-1. The infeasibility of DLPwAI assures the security of some cryptographic schemes. In 2006, Cheon proposed a novel algorithm for solving DLPwAI. This paper shows our experimental results of Cheon's algorithm by implementing it with some speeding-up techniques. In fact, we succeeded to solve DLPwAI in a group with 128-bit order in 45 hours with a single PC on an elliptic curve defined over a prime finite field with 256-bit elements which is used in the TinyTate library.

UR - http://www.scopus.com/inward/record.url?scp=79958834656&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79958834656&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-21040-2_8

DO - 10.1007/978-3-642-21040-2_8

M3 - Conference contribution

AN - SCOPUS:79958834656

SN - 9783642210396

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 116

EP - 127

BT - Information Security Theory and Practice

T2 - 5th Workshop in Information Security Theory and Practice, WISTP 2011

Y2 - 1 June 2011 through 3 June 2011

ER -