### 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)
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

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.