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

Yumi Sakemi; Tetsuya Izu; Masahiko Takenaka; Masaya Yasuda

doi:10.1007/978-3-642-21040-2_8

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

Yumi Sakemi, Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Information Security Theory and Practice
Subtitle of host publication	Security and Privacy of Mobile Devices in Wireless Communication - 5th IFIP WG 11.2 International Workshop, WISTP 2011, Proceedings
Pages	116-127
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-21040-2_8
Publication status	Published - 2011
Externally published	Yes
Event	5th Workshop in Information Security Theory and Practice, WISTP 2011 - Heraklion, Crete, Greece Duration: Jun 1 2011 → Jun 3 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6633 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	5th Workshop in Information Security Theory and Practice, WISTP 2011
Country/Territory	Greece
City	Heraklion, Crete
Period	6/1/11 → 6/3/11

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Sakemi, Y., Izu, T., Takenaka, M., & Yasuda, M. (2011). Solving DLP with auxiliary input over an elliptic curve used in TinyTate library. In Information Security Theory and Practice: Security and Privacy of Mobile Devices in Wireless Communication - 5th IFIP WG 11.2 International Workshop, WISTP 2011, Proceedings (pp. 116-127). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6633 LNCS). https://doi.org/10.1007/978-3-642-21040-2_8

Solving DLP with auxiliary input over an elliptic curve used in TinyTate library. / Sakemi, Yumi; Izu, Tetsuya; Takenaka, Masahiko et al.
Information Security Theory and Practice: Security and Privacy of Mobile Devices in Wireless Communication - 5th IFIP WG 11.2 International Workshop, WISTP 2011, Proceedings. 2011. p. 116-127 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6633 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sakemi, Y, Izu, T, Takenaka, M & Yasuda, M 2011, Solving DLP with auxiliary input over an elliptic curve used in TinyTate library. in Information Security Theory and Practice: Security and Privacy of Mobile Devices in Wireless Communication - 5th IFIP WG 11.2 International Workshop, WISTP 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6633 LNCS, pp. 116-127, 5th Workshop in Information Security Theory and Practice, WISTP 2011, Heraklion, Crete, Greece, 6/1/11. https://doi.org/10.1007/978-3-642-21040-2_8

Sakemi Y, Izu T, Takenaka M, Yasuda M. Solving DLP with auxiliary input over an elliptic curve used in TinyTate library. In Information Security Theory and Practice: Security and Privacy of Mobile Devices in Wireless Communication - 5th IFIP WG 11.2 International Workshop, WISTP 2011, Proceedings. 2011. p. 116-127. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-21040-2_8

Sakemi, Yumi ; Izu, Tetsuya ; Takenaka, Masahiko et al. / Solving DLP with auxiliary input over an elliptic curve used in TinyTate library. Information Security Theory and Practice: Security and Privacy of Mobile Devices in Wireless Communication - 5th IFIP WG 11.2 International Workshop, WISTP 2011, Proceedings. 2011. pp. 116-127 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9344f20578d3427abc0f6104e11f8d53,

title = "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, α 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.",

author = "Yumi Sakemi and Tetsuya Izu and Masahiko Takenaka and Masaya Yasuda",

year = "2011",

doi = "10.1007/978-3-642-21040-2_8",

language = "English",

isbn = "9783642210396",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "116--127",

booktitle = "Information Security Theory and Practice",

note = "5th Workshop in Information Security Theory and Practice, WISTP 2011 ; Conference date: 01-06-2011 Through 03-06-2011",

}

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 -

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this