CWI Cryptology Group

Abstract: TBA

Abstract: In this talk I will show some interesting research problems on the utilization of cryptography in the context of blockchain. My goal is to give a high level presentation of current research efforts to improve Zero Knowledge Proof constructions.

Abstract: Assuming the existence of a public-key infrastructure (PKI), digital signatures are a fundamental building block in the design of secure consensus protocols with optimal resilience---less than 1/2 corrupted parties. It is known that without such a trusted setup, 1/3 is the best that can be achieved. More recently, with the advent of blockchain protocols like Bitcoin, consensus has been considered in the “permissionless” setting where no authentication or even point-to-point communication is available, and yet consensus tolerating a 1/2 corruption is possible *from scratch*.
How come? In this talk we explain this apparent inconsistency via a "resource-restricted cryptography" framework. Further, we put forth a formalization of a "blockchain-friendly" primitive we call Signatures of Work (SoW) that is sufficient for designing consensus protocols in this setting, and present a new permissionless consensus protocol based on it, secure assuming an honest majority of computational power.
This talk is based on joint work with Aggelos Kiayias, Rafail Ostrovsky, Giorgos Panagiotakos and Vassilis Zikas.

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.