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.