Paper 2019/315

Iterated Search Problems and Blockchain Security under Falsifiable Assumptions

Juan A. Garay and Aggelos Kiayias and Giorgos Panagiotakos

Abstract

We put forth a new class of search problems, iterated search problems (ISP), and study their relation to the design of secure blockchain protocols. We prove that (i) any blockchain protocol implies a hard ISP problem, i.e., ISP hardness is necessary for secure blockchain protocols---but not sufficient by itself, and (ii) a suitably enhanced class of ISPs is sufficient to imply, via construction, a secure blockchain protocol in the common reference string (CRS) model. We then put forth a specific proposal for an enhanced ISP based on an underlying cryptographic hash function. The resulting blockchain protocol's security reduces to the ISP hardness of the hash-based scheme and to a randomness extraction property of the hash function. As a corollary, we obtain a blockchain protocol secure in the standard model under falsifiable assumptions; in contrast, all previous blockchain protocols were shown secure in the random oracle model.

Note: Some changes on Construction 1.