Skip to Main content Skip to Navigation
Conference papers

Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library

Abstract : The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α from G, αG, αd G 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, August 9, 2017 - 10:24:25 AM
Last modification on : Wednesday, August 9, 2017 - 10:25:13 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



yumi Sakemi, Tetsuya Izu, Masahiko Takenaka, Masaya yasuda. Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library. 5th Workshop on Information Security Theory and Practices (WISTP), Jun 2011, Heraklion, Crete, Greece. pp.116-127, ⟨10.1007/978-3-642-21040-2_8⟩. ⟨hal-01573301⟩



Record views


Files downloads