Paper 2018/939

The Proof is in the Pudding: Proofs of Work for Solving Discrete Logarithms

Marcella Hastings, Nadia Heninger, and Eric Wustrow

Abstract

We propose a proof of work protocol that computes the discrete logarithm of an element in a cyclic group. Individual provers generating proofs of work perform a distributed version of the Pollard rho algorithm. Such a protocol could capture the computational power expended to construct proof-of-work-based blockchains for a more useful purpose, as well as incentivize advances in hardware, software, or algorithms for an important cryptographic problem. We describe our proposed construction and elaborate on challenges and potential trade-offs that arise in designing a practical proof of work.

Note: Update camera-ready paper, add publication information.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Financial Cryptography and Data Security 2019
Keywords
Proofs of workdiscrete logarithm problemPollard rhocryptanalysisdistributed cryptography
Contact author(s)
mhast @ cis upenn edu
History
2019-01-10: last of 3 revisions
2018-10-05: received
See all versions
Short URL
https://ia.cr/2018/939
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/939,
      author = {Marcella Hastings and Nadia Heninger and Eric Wustrow},
      title = {The Proof is in the Pudding: Proofs of Work for Solving Discrete Logarithms},
      howpublished = {Cryptology ePrint Archive, Paper 2018/939},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/939}},
      url = {https://eprint.iacr.org/2018/939}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.