Cryptology ePrint Archive: Report 2014/857

Pseudonymous Broadcast and Secure Computation from Cryptographic Puzzles

Jonathan Katz and 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.

Category / Keywords: foundations / broadcast

Date: received 19 Oct 2014, last revised 1 Sep 2015

Contact author: amiller at cs umd edu

Available format(s): PDF | BibTeX Citation

Version: 20150901:165230 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]