Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / blockchain protocols, proof-of-work, falsifiable assumptions

Date: received 21 Mar 2019, last revised 29 Mar 2019

Contact author: pagio91i at gmail com,akiayias@inf ed ac uk,garay@cse tamu edu

Available format(s): PDF | BibTeX Citation

Note: Some changes on Construction 1.

Version: 20190329:173502 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]