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 -