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 conferencePaper

Published

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.
Original languageEnglish
Pages148
Number of pages156
DOIs
Publication statusPublished - 5 Aug 2014
EventAlgorithmic Number Theory Symposium (ANTS) 2014 - Hyundai Hotel, Gyeongju, Korea, Republic of
Duration: 7 Aug 201411 Aug 2014

Conference

ConferenceAlgorithmic Number Theory Symposium (ANTS) 2014
CountryKorea, Republic of
CityGyeongju
Period7/08/1411/08/14

Research outputs

This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 22672811