# Distributed Cryptography Based on the Proofs of Work

@article{Andrychowicz2014DistributedCB, title={Distributed Cryptography Based on the Proofs of Work}, author={Marcin Andrychowicz and Stefan Dziembowski}, journal={IACR Cryptol. ePrint Arch.}, year={2014}, volume={2014}, pages={796} }

Motivated by the recent success of Bitcoin we study the question of constructing distributed crypto- graphic protocols in a fully peer-to-peer scenario (without any trusted setup) under the assumption that the adver- sary has limited computing power. We propose a formal model for this scenario and then we construct the following protocols working in it: (i) a broadcast protocol secure under the assumption that the honest parties have computing power that is some non-negligible fraction of… Expand

#### 25 Citations

PoW-Based Distributed Cryptography with No Trusted Setup

- Computer Science
- CRYPTO
- 2015

A formal model for this scenario is proposed and then a broadcast protocol is constructed that is secure under the assumption that the honest parties have computing power that is some non-negligible fraction of computing power of the adversary. Expand

Pseudonymous Broadcast and Secure Computation from Cryptographic Puzzles

- 2015

In standard models of secure 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… Expand

Improvement on Bitcoin’s Verifiable Public Randomness with Semi-Trusted Delegates

- Computer Science
- 2018 9th International Symposium on Telecommunications (IST)
- 2018

It is argued that a successful attack against this scheme to impose a bias on a single bit of the output randomness requires not only a significant financial cost but also a corruption of more than k out of n trusted delegates. Expand

Blockchain and Consensus from Proofs of Work without Random Oracles

- 2018

One of the most impactful applications of proofs of work (POW) currently is in the design of blockchain protocols such as Bitcoin. Yet, despite the wide recognition of POWs as the fundamental… Expand

Proofs of Work for Blockchain Protocols

- Computer Science
- IACR Cryptol. ePrint Arch.
- 2017

This work provides a formulation of the POW primitive that implies the security of the Bitcoin blockchain protocol in the standard model and paves the way for proving theSecurity of blockchain protocols in theStandard model assuming the authors' primitive can be realized from computational assumptions. Expand

Bootstrapping the Blockchain - Directly

- Computer Science
- IACR Cryptol. ePrint Arch.
- 2016

This paper presents a bootstrapped Bitcoin-like blockchain protocol relying on POWs that builds genesis blocks from scratch in the presence of adversarial pre-computation, and considers applications of the construction, including a PKI generation protocol and a consensus protocol without trusted setup assuming an honest majority. Expand

Scalable Distributed Random Number Generation Based on Homomorphic Encryption

- Computer Science
- 2019 IEEE International Conference on Blockchain (Blockchain)
- 2019

A protocol which can be implemented on a blockchain that ensures unpredictable, tamper-resistant, scalable and publicly-verifiable outcomes, and a comparison between recent approaches to the generation of random beacons is presented. Expand

A Secure Sharding Protocol For Open Blockchains

- Computer Science
- CCS
- 2016

ELASTICO is the first candidate for a secure sharding protocol with presence of byzantine adversaries, and scalability experiments on Amazon EC2 with up to $1, 600$ nodes confirm ELASTICO's theoretical scaling properties. Expand

Consensus from Signatures of Work

- Computer Science
- CT-RSA
- 2020

This work formalizes a building block that is sufficient for designing consensus protocols in this setting where no authentication or even point-to-point communication is available and relies on a very strong independence assumption about adversarial accesses to the underlying computational resource. Expand

Robust P2P Primitives Using SGX Enclaves

- Computer Science
- 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS)
- 2020

This work studies the setting of a synchronous network wherein peer nodes have CPUs equipped with a recent trusted computing mechanism called Intel SGX, and observes that the byzantine adversary reduces to the adversary in the general-omission model. Expand

#### References

SHOWING 1-10 OF 58 REFERENCES

Rational Protocol Design: Cryptography against Incentive-Driven Adversaries

- Computer Science
- 2013 IEEE 54th Annual Symposium on Foundations of Computer Science
- 2013

This work considers a two-party game between an protocol designer and an external attacker to modeling a protocol under attack from an external entity, and demonstrates how knowledge of the attacker's incentives can be used to circumvent known impossibility results in this setting. Expand

Player Simulation and General Adversary Structures in Perfect Multiparty Computation

- Computer Science
- Journal of Cryptology
- 2000

This work formally defines what it means to simulate a player by a multiparty protocol among a set of (new) players, and derives the resilience of the new protocol as a function of the resiliences of the original protocol and the protocol used for the simulation. Expand

Leakage Resilient Secure Two-Party Computation

- Computer Science
- IACR Cryptol. ePrint Arch.
- 2011

This paper provides the first general construction for secure two-party computation and shows how to adapt the proof from Yao’s protocol into the leakage resilient setting and provides compositions theorems for the case where the inputs of the parties are sampled from a min-entropy source distribution. Expand

Multiparty computation secure against continual memory leakage

- Mathematics, Computer Science
- STOC '12
- 2012

We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-ε fraction of all parties for an arbitrarily small constant ε >0, can… Expand

Exposing Computationally-Challenged Byzantine Impostors

- 2005

Internet protocols permit a single machine to masquerade as many, allowing an adversary to appear to control more nodes than it actually does. The possibility of suchSybil attackshas been taken to… Expand

Rational secure computation and ideal mechanism design

- Mathematics, Computer Science
- 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
- 2005

This work puts forward and implements a stronger notion, rational secure computation, that does not depend on player honesty, but solely on player rationality, and shows that the ballot-box can actually be used to securely compute any function. Expand

Byzantine Agreement Given Partial Broadcast

- Computer Science
- Journal of Cryptology
- 2005

It is shown that, by extending this model by the existence of partial broadcast channels among subsets of b players, global broadcast can be achieved if and only if the number h of honest players satisfies 2n/h < b + 1. Expand

Theoretical Bitcoin Attacks with less than Half of the Computational Power (draft)

- Computer Science
- IACR Cryptol. ePrint Arch.
- 2013

It is argued that the current theoretical limit of attacker's fraction of total computational power essential for the security of the system is in a sense not $\frac{1}{2}$ but a bit less than $\frac {1}{4}$, and outline proposals for protocol change that can raise this limit to be as close to 1-2 as the authors want. Expand

Leakage-Tolerant Interactive Protocols

- Computer Science
- TCC
- 2011

A variant of the UC theorem is proved that enables modular design and analysis of protocols even in face of general, non-modular leakage. Expand

Random oracles are practical: a paradigm for designing efficient protocols

- Computer Science
- CCS '93
- 1993

It is argued that the random oracles model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice, and yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. Expand