Paper 2014/857

Pseudonymous Broadcast and Secure Computation from Cryptographic Puzzles

Jonathan Katz, Andrew Miller, and Elaine Shi


In standard models of distributed computation, point-to-point channels between parties are assumed to be authenticated by some pre-existing means. In other cases, even stronger pre-existing setup—e.g., a public-key infrastructure (PKI)—is assumed. These assumptions are too strong for open, peer-to-peer networks, where parties do not necessarily have any prior relationships and can come and go as they please. Nevertheless, these assumptions are made due to the prevailing belief that nothing “interesting” can be achieved without them. Taking inspiration from Bitcoin, we show that precise bounds on computational power can be used in place of pre-existing setup to achieve weaker (but nontrivial) notions of security. Specifically, under the assumption that each party can solve cryptographic puzzles only at a bounded rate (and the existence of digital signatures), we show that without prior setup and with no bound on the number of corruptions, a group of parties can agree on a PKI with which they can then realize pseudonymous notions of authenticated communication, broadcast, and secure computation. Roughly, “pseudonymous” here means that parties are identified by pseudoynms rather than by their true identities.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
amiller @ cs umd edu
2015-09-01: last of 7 revisions
2014-10-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Katz and Andrew Miller and Elaine Shi},
      title = {Pseudonymous Broadcast and Secure Computation from Cryptographic Puzzles},
      howpublished = {Cryptology ePrint Archive, Paper 2014/857},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.