Paper 2014/857

Pseudonymous Broadcast and Secure Computation from Cryptographic Puzzles

Jonathan Katz, Andrew Miller, and Elaine Shi

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
broadcast
Contact author(s)
amiller @ cs umd edu
History
2015-09-01: last of 7 revisions
2014-10-22: received
See all versions
Short URL
https://ia.cr/2014/857
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/857,
      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{https://eprint.iacr.org/2014/857}},
      url = {https://eprint.iacr.org/2014/857}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.