Paper 2019/533

Stopping time signatures for some algorithms in cryptography

Percy Deift, Stephen D. Miller, and Thomas Trogdon

Abstract

We consider the normalized distribution of the overall running times of some cryptographic algorithms, and what information they reveal about the algorithms. Recent work of Deift, Menon, Olver, Pfrang, and Trogdon has shown that certain numerical algorithms applied to large random matrices exhibit a characteristic distribution of running times, which depends only on the algorithm but are independent of the choice of probability distributions for the matrices. Different algorithms often exhibit different running time distributions, and so the histograms for these running time distributions provide a "time-signature" for the algorithms, making it possible, in many cases, to distinguish one algorithm from another. In this paper we extend this analysis to cryptographic algorithms, and present examples of such algorithms with time-signatures that are indistinguishable, and others with time-signatures that are clearly distinct.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
foundationsnumber theorydiscrete logarithm problemelliptic curve cryptosystem
Contact author(s)
miller @ math rutgers edu
History
2019-05-22: received
Short URL
https://ia.cr/2019/533
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/533,
      author = {Percy Deift and Stephen D.  Miller and Thomas Trogdon},
      title = {Stopping time signatures for some algorithms in cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2019/533},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/533}},
      url = {https://eprint.iacr.org/2019/533}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.