International Association
for Cryptologic Research

In standard models of secure computation, point-to-point channels between parties are as-

sumed 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 assumptions that digital signatures exist and each party can solve cryp-

tographic \"time-lock\" puzzles only at a bounded rate, 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 inputs/outputs are (effectively)

bound to pseudonyms rather than parties\' true identities.