The discrete logarithm problem for exponents of bounded height. / Scott, Sam; Blackburn, Simon.

2014. 148 Paper presented at Algorithmic Number Theory Symposium (ANTS) 2014, Gyeongju, Korea, Republic of.

Research output: Contribution to conferencePaperpeer-review

Published

Standard

The discrete logarithm problem for exponents of bounded height. / Scott, Sam; Blackburn, Simon.

2014. 148 Paper presented at Algorithmic Number Theory Symposium (ANTS) 2014, Gyeongju, Korea, Republic of.

Research output: Contribution to conferencePaperpeer-review

Harvard

Scott, S & Blackburn, S 2014, 'The discrete logarithm problem for exponents of bounded height', Paper presented at Algorithmic Number Theory Symposium (ANTS) 2014, Gyeongju, Korea, Republic of, 7/08/14 - 11/08/14 pp. 148. https://doi.org/10.1112/S1461157014000230

APA

Scott, S., & Blackburn, S. (2014). The discrete logarithm problem for exponents of bounded height. 148. Paper presented at Algorithmic Number Theory Symposium (ANTS) 2014, Gyeongju, Korea, Republic of. https://doi.org/10.1112/S1461157014000230

Vancouver

Scott S, Blackburn S. The discrete logarithm problem for exponents of bounded height. 2014. Paper presented at Algorithmic Number Theory Symposium (ANTS) 2014, Gyeongju, Korea, Republic of. https://doi.org/10.1112/S1461157014000230

Author

Scott, Sam ; Blackburn, Simon. / The discrete logarithm problem for exponents of bounded height. Paper presented at Algorithmic Number Theory Symposium (ANTS) 2014, Gyeongju, Korea, Republic of.156 p.

BibTeX

@conference{6b069dc811734bb6b658f59df20a33c2,
title = "The discrete logarithm problem for exponents of bounded height",
abstract = "Let G be a cyclic group written multiplicatively (and represented in some concrete way). Let n be a positive integer (much smaller than the order of G). Let g,h∈G. The bounded height discrete logarithm problem is the task of finding positive integers a and b (if they exist) such that a⩽n, b⩽n and ga=hb. (Provided that b is coprime to the order of g, we have h=ga/b where a/b is a rational number of height at most n. This motivates the terminology.) The paper provides a reduction to the two-dimensional discrete logarithm problem, so the bounded height discrete logarithm problem can be solved using a low-memory heuristic algorithm for the two-dimensional discrete logarithm problem due to Gaudry and Schost. The paper also provides a low-memory heuristic algorithm to solve the bounded height discrete logarithm problem in a generic group directly, without using a reduction to the two-dimensional discrete logarithm problem. This new algorithm is inspired by (but differs from) the Gaudry–Schost algorithm. Both algorithms use O(n) group operations, but the new algorithm is faster and simpler than the Gaudry–Schost algorithm when used to solve the bounded height discrete logarithm problem. Like the Gaudry–Schost algorithm, the new algorithm can easily be carried out in a distributed fashion.The bounded height discrete logarithm problem is relevant to a class of attacks on the privacy of a key establishment protocol recently published by EMVCo for comment. This protocol is intended to protect the communications between a chip-based payment card and a terminal using elliptic curve cryptography. The paper comments on the implications of these attacks for the design of any final version of the EMV protocol.",
keywords = "Discrete logarithms, Number Theory",
author = "Sam Scott and Simon Blackburn",
year = "2014",
month = aug,
day = "5",
doi = "10.1112/S1461157014000230",
language = "English",
pages = "148",
note = "Algorithmic Number Theory Symposium (ANTS) 2014 ; Conference date: 07-08-2014 Through 11-08-2014",

}

RIS

TY - CONF

T1 - The discrete logarithm problem for exponents of bounded height

AU - Scott, Sam

AU - Blackburn, Simon

PY - 2014/8/5

Y1 - 2014/8/5

N2 - Let G be a cyclic group written multiplicatively (and represented in some concrete way). Let n be a positive integer (much smaller than the order of G). Let g,h∈G. The bounded height discrete logarithm problem is the task of finding positive integers a and b (if they exist) such that a⩽n, b⩽n and ga=hb. (Provided that b is coprime to the order of g, we have h=ga/b where a/b is a rational number of height at most n. This motivates the terminology.) The paper provides a reduction to the two-dimensional discrete logarithm problem, so the bounded height discrete logarithm problem can be solved using a low-memory heuristic algorithm for the two-dimensional discrete logarithm problem due to Gaudry and Schost. The paper also provides a low-memory heuristic algorithm to solve the bounded height discrete logarithm problem in a generic group directly, without using a reduction to the two-dimensional discrete logarithm problem. This new algorithm is inspired by (but differs from) the Gaudry–Schost algorithm. Both algorithms use O(n) group operations, but the new algorithm is faster and simpler than the Gaudry–Schost algorithm when used to solve the bounded height discrete logarithm problem. Like the Gaudry–Schost algorithm, the new algorithm can easily be carried out in a distributed fashion.The bounded height discrete logarithm problem is relevant to a class of attacks on the privacy of a key establishment protocol recently published by EMVCo for comment. This protocol is intended to protect the communications between a chip-based payment card and a terminal using elliptic curve cryptography. The paper comments on the implications of these attacks for the design of any final version of the EMV protocol.

AB - Let G be a cyclic group written multiplicatively (and represented in some concrete way). Let n be a positive integer (much smaller than the order of G). Let g,h∈G. The bounded height discrete logarithm problem is the task of finding positive integers a and b (if they exist) such that a⩽n, b⩽n and ga=hb. (Provided that b is coprime to the order of g, we have h=ga/b where a/b is a rational number of height at most n. This motivates the terminology.) The paper provides a reduction to the two-dimensional discrete logarithm problem, so the bounded height discrete logarithm problem can be solved using a low-memory heuristic algorithm for the two-dimensional discrete logarithm problem due to Gaudry and Schost. The paper also provides a low-memory heuristic algorithm to solve the bounded height discrete logarithm problem in a generic group directly, without using a reduction to the two-dimensional discrete logarithm problem. This new algorithm is inspired by (but differs from) the Gaudry–Schost algorithm. Both algorithms use O(n) group operations, but the new algorithm is faster and simpler than the Gaudry–Schost algorithm when used to solve the bounded height discrete logarithm problem. Like the Gaudry–Schost algorithm, the new algorithm can easily be carried out in a distributed fashion.The bounded height discrete logarithm problem is relevant to a class of attacks on the privacy of a key establishment protocol recently published by EMVCo for comment. This protocol is intended to protect the communications between a chip-based payment card and a terminal using elliptic curve cryptography. The paper comments on the implications of these attacks for the design of any final version of the EMV protocol.

KW - Discrete logarithms

KW - Number Theory

U2 - 10.1112/S1461157014000230

DO - 10.1112/S1461157014000230

M3 - Paper

SP - 148

T2 - Algorithmic Number Theory Symposium (ANTS) 2014

Y2 - 7 August 2014 through 11 August 2014

ER -