MAPPING
THE DISCRETE
LOGARITHM
an
Undergraduate Research Project,
funded by National Science
Foundation REU grants
DMS-0352940, DMS-1003924
Just a few decades ago, cryptography was considered a domain exclusive to national governments and militaries. However, the computer explosion has changed that. Every day, millions of people trust that their privacy will be protected as they make online purchases or communicate privately with a friend. Many of the cryptographic algorithms they use are built upon a common transformation, namely discrete exponentiation modulo an integer n. For instance, Diffie-Hellman key exchange, RSA and the Blum-Micali pseudorandom bit generator all use discrete exponentiation.
It is thought that the inverse of this transformation, the "discrete logarithm problem", or "DLP" is computationally intractable. This is part of the basis for assuming the cryptographic security of the algorithms referred to above. However, there is no known proof of this fact.
In particular, it would be interesting to know if there were patterns in this transformation that can be exploited. One way to determine this would be to construct the "functional graph" associated with the transformation. Any unexpected characteristics of this functional graph might lead to new progress in breaking the discrete logarithm problem.
Open questions to explore regarding this functional graph include:
Under what circumstances can we find a "fixed point" for the DLP? How often do they occur? (Partially solved, but not completely.)
Under what circumstances can we find a "two cycle" for the DLP? How often do they occur? (Much evidence, but little proof.)
What should a "random" functional graph look like? In particular, what do we expect the average values of statistics associated with the graph to be? (Known for some sorts of statistics (number of connected components, number of cyclic nodes, number of terminal nodes, average cycle length, maximum cycle length, average tail length, and maximum tail length) and some sorts of functional graphs (unary, binary). Lots left unknown.)
What do we expect the standard deviation of statistics associated with a "random" functional graph to be? (Very little known, but the methods are out there.)
How closely do the functional graphs for the DLP resemble "random" functional graphs? (Some data collected, but more would help.)
What if the modulus of the discrete logarithm is composite? (For example, prime powers or RSA numbers: n = pq where p and q are prime.)
What about discrete logarithms in finite fields?
What about discrete logarithms on elliptic curves (or other groups)?
What about other maps similar to the discrete logarithm, e.g. those involved in breaking the ElGamal signature scheme?
Mapping the Discrete Logarithm talk
notes:
Some references (more available on request):
General:
The Hard Problems in Cryptography wiki Discrete Logarithms page.
Steven Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press, scroll down for “Full Extended Text”.
Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, An Introduction to Mathematical Cryptography, Springer, 2014.
Comparing discrete exponentiation maps with random maps:
Daniel R. Cloutier. Mapping the discrete logarithm. Senior thesis, Rose-Hulman Institute of Technology, 2005.
Code from "Mapping the Discrete Logarithm"
Daniel R. Cloutier and Joshua Holden. Mapping the discrete logarithm. Involve, 3:197--213, 2010.
Nathan W. Lindle. A Statistical Look at Maps of the Discrete Logarithm. Senior thesis, Rose-Hulman Institute of Technology, 2008.
Max F. Brugger and Christina A. Frederick. The Discrete Logarithm Problem and Ternary Functional Graphs, MSTR 07-02. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 8, Issue 2, 2007.
Max F. Brugger. Exploring the Discrete Logarithm with Random Ternary Graphs. Senior thesis, Oregon State University, 2008.
Andrew Hoffman. Statistical Investigation of Structure in the Discrete Logarithm, MSTR 09-09. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 10, Issue 2, 2009.
Code from "Statistical Investigation of Structure in the Discrete Logarithm"
Marcus L. Mace. Discrete Logarithm over Composite Moduli, MSTR 09-07.
Mitchell Orzech. Statistical Analysis of Binary Functional Graphs of the Discrete Logarithm. Senior thesis, Rose-Hulman Institute of Technology, 2016.
Code from "Mapping the Discrete Logarithm".
Counting random maps and related objects:
Philippe Flajolet and Andrew Odlyzko. Random Mapping Statistics. In Advances in Cryptology, Proc. Eurocrypt'89, , J-J. Quisquater Ed., Lect. Notes in Comp. Sc. vol 434, 1990, pp. 329-354.
Philippe Flajolet and Andrew Odlyzko. Singularity analysis of generating functions. In SIAM J. Discrete Math., vol 3 (1990) pp. 216-240.
Philippe Flajolet and Andrew Odlyzko. The Average Height of Binary Trees and Other Simple Trees. In Journal of Computer and System Scienes, vol 25, 1982, pp. 171-213.
P. Flajolet, Z. Gao, A. Odlyzko, and B. Richmond. The distribution of heights of binary trees and other simple trees (44kb). In Combinatorics, Probability, and Computing, vol 2 (1993), pp. 145-156.
Herbert Wilf, Generatingfunctionology, 2nd ed., Academic Press, 1994.
Other related analyses of discrete exponentiation maps:
Joshua Holden. Fixed Points and Two-Cycles of the Discrete Logarithm. In: Algorithmic number theory: 5th international symposium; proceedings, no. 2369 in Springer Lecture Notes in Computer Science, Springer-Verlag, 2002.
Joshua Holden. Distribution of the Error in Estimated Numbers of Fixed Points of the Discrete Logarithm. Communications in Computer Algebra, 38:111–118, 2004.
Joshua Holden and Pieter Moree. New Conjectures and Results for Small Cycles of the Discrete Logarithm. In: High Primes and Misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, no. 41 in Fields Institute Communications, AMS, 2004.
Joshua Holden and Pieter Moree. Some heuristics and results for small cycles of the discrete logarithm. Mathematics of Computation, 75:419--449, 2006.
Lev Glebsky and Igor E. Shparlinski. Short Cycles in Repeated Exponentiation Modulo a Prime. Designs, Codes and Cryptography, Vol. 56, no. 1, 2009.
Jean Bourgain, Sergei V. Konyagin, and Igor E. Shparlinski. Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm, Int Math Res Notices, Vol. 2008, rnn090, 2008.
Jean Bourgain, Sergei V. Konyagin, and Igor E. Shparlinski. Distribution on elements of cosets of small subgroups and applications, Int Math Res Notices, Vol. 2012, no. 9 (2012), pp. 1968-2009.
The Blum-Micali CSPRNG:
Manuel Blum and Silvio Micali, How to Generate Cryptographically Strong Sequences of Pseudorandom Bits, SIAM Journal on Computing 13, no. 4 (1984): 850-864.
Elliptic curve discrete logarithms and random number generators based on them:
NIST. SP 800-90A, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, January 2012.
Daniel R.L. Brown and Kristian Gjøsteen. A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, CRYPTO 2007, LNCS 4622, pp. 466-481, 2007.
Aaron Blumenfeld. Discrete Logarithms on Elliptic Curves, MSTR 10-04. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 12, Issue 1, 2011.
Code from "Discrete Logarithms on Elliptic Curves".
Chapter 6 of Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, An Introduction to Mathematical Cryptography, Springer, 2014.
Elliptic curve isogenies and cryptography using them:
Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren, Cryptographic Hash Functions from Expander Graphs, Journal of Cryptology, volume 22, pages 93–113 (2009).
Chapter 9 and Chapter 25 of Steven Galbraith, Mathematics of Public Key Cryptography, Cambridge University Press.
Joseph H. Silverman, The Arithmetic of Elliptic Curves, Springer, 2009, especially Chapter III and Chapter V.
The self-power map
Roger Crocker, On a New Problem in Number Theory, The American Mathematical Monthly, Vol. 73, No. 4 (Apr., 1966), pp. 355-357.
Roger Crocker, On Residues of nn, The American Mathematical Monthly, Vol. 76, No. 9 (Nov., 1969), pp. 1028-1029.
Lawrence Somer, The Residues of nn Modulo p, Fibonacci Quarterly, Vol. 19, No. 2 (Apr., 1981), pp. 110-117.
Antal Balog, Kevin A. Broughan, Igor E. Shparlinski. On the Number of Solutions of Exponential Congruences. Acta Arithmetica, Vol. 148 (2011), pp. 93-103.
Matthew Friedrichsen, Brian Larson, and Emily McDowell. Structure and Statistics of the Self-Power Map, MSTR 10-05. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 11, Issue 2, 2010.
Code from "Structure and Statistics of the Self-Power Map".
Catalina Voichita Anghel, The Self Power Map and its Image Modulo a Prime, Ph.D. Thesis, University of Toronto, 2013.
Pär Kurlberg, Florian Luca, and Igor E. Shparlinski, On the
Fixed Points of the Map
x → xx
Modulo a Prime, Mathematical Research Letters, Vol. 22
(2015), pp. 141-168.
The square (and higher power) discrete exponential map
Jan Camenisch and Markus Stadler, Efficient group signature schemes for large groups, CRYPTO '97, LNCS 1294, pp. 410-424, 1997.
"Multi-maps" x mod pe → gx mod pe (or similar maps) for any x
Lev Glebsky, Cycles in Repeated Exponentiation Modulo pn. Preprint.
Joshua Holden, Margaret M. Robinson, Counting Fixed Points, Two-Cycles, and Collisions of the Discrete Exponential Function using p-adic Methods. Journal of the Australian Mathematical Society, Vol. 92 (2012), pp. 163-178.
Abigail Mann and Adelyn Yeoh, Deconstructing the Welch Equation using p-adic Methods, MSTR 14-04. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 16, Issue 1, 2015.
Caiyun Zhu and Anne Waldo, The Discrete Lambert Map, Rose-Hulman Undergraduate Mathematics Journal, Vol. 16, Issue 2, 2015.
Abigail Mann. Counting Solutions to Discrete Non-Algebraic Equations Modulo Prime Powers. Senior thesis, Rose-Hulman Institute of Technology, 2016.
Finite fields
Andrew M. Odlyzko, Discrete Logarithms in Finite Fields and Their Cryptographic Significance. In Advances in Cryptology: Proceedings of EUROCRYPT 84, Volume 209 of Lecture Notes in Computer Science, Springer-Verlag, 1985.
Brouwer, Pellikaan, Eric R. Verheul, Doing More with Fewer Bits. In Advances in Cryptology - Asiacrypt '99, Vol. 1716 of Lecture Notes in Computer Science, Springer-Verlag, 1999. pp. 321-332.
Arjen K. Lenstra, Eric R. Verheul, The XTR public key system, Crypto 2000.
Matrices and other groups
Eligijus Sakalauskas, Narimantas Listopadskis, Povilas Tvarijonas, KEY AGREEMENT PROTOCOL (KAP) BASED ON MATRIX POWER FUNCTION, in Krassimir Markov, Krassimira Ivanova, Ilia Mitov (ed.), Advanced Studies in Software and Knowledge Engineering.
Christopher J. Monico, Semirings and Semigroup Actions in Public-Key Cryptography.
In-Sok Lee, Woo-Hwan Kim, Daesung Kwon, Sangil Nahm, Nam-Seok Kwak, and Yoo-Jin Baek. On the Security of MOR Public Key Cryptosystem.
Johannes Buchmann and H. Williams, A key-exchange system based on imaginary quadratic fields, Journal of Cryptology 1, no. 2 (June 10, 1988): 107-118.
Max F. Brugger and Christina A. Frederick. The Discrete Logarithm Problem and Ternary Functional Graphs, MSTR 07-02. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 8, Issue 2, 2007.
Matthew Niemerg. Isomorphisms of Elliptic Curves over Extensions of Finite Fields, MSTR 07-01.
Philip Brunetti. Structural Properties of the Mapping gx → gx2. (Draft)
Katrina Glaeser. The Digraph of the Square Mapping on Elliptic Curves, MSTR 09-08.
Andrew Hoffman. Statistical Investigation of Structure in the Discrete Logarithm, MSTR 09-09. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 10, Issue 2, 2009.
Code from "Statistical Investigation of Structure in the Discrete Logarithm".
Joseph Kramer-Miller. Structural Properties of Power Digraphs Modulo n, MSTR 09-06.
Marcus L. Mace. Discrete Logarithm over Composite Moduli, MSTR 09-07.
Aaron Blumenfeld. Discrete Logarithms on Elliptic Curves, MSTR 10-04. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 12, Issue 1, 2011.
Code from "Discrete Logarithms on Elliptic Curves".
Matthew Friedrichsen, Brian Larson, and Emily McDowell. Structure and Statistics of the Self-Power Map, MSTR 10-05. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 11, Issue 2, 2010.
Code from "Structure and Statistics of the Self-Power Map".
JingJing Chen and Mark Lotts. Structure and Randomness of the Discrete Lambert Map, MSTR 11-02. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 13, Issue 1, 2012.
Code from Chen and Lotts.
Christopher Evans. The Elliptic Curve Discrete Logarithm and Functional Graphs, MSTR 11-01.
Code from Evans.
Alex Wood. The Square Discrete Exponentiation Map, MSTR 11-05.
Reports from the 2014 Mini-REU at Mount Holyoke College:
Abigail Mann and Adelyn Yeoh, Deconstructing the Welch Equation using p-adic Methods, MSTR 14-04. Also published in the Rose-Hulman Undergraduate Mathematics Journal, Vol. 16, Issue 1, 2015.
Caiyun Zhu and Anne Waldo, The Discrete Lambert Map, Rose-Hulman Undergraduate Mathematics Journal, Vol. 16, Issue 2, 2015.
Other resources:
Information about computers:
The Algolib package for Maple and lots of tutorials and other information
Information about presentations: