7 papers
Proof of Work With External Utilities
Yogev Bar-On, Ilan Komargodski, Omri Weinstein
Proof-of-Work (PoW) consensus is traditionally analyzed under the assumption that all miners incur similar costs per unit of computational effort. In reality, costs vary due to fac…
Proofs of Useful Work from Arbitrary Matrix Multiplication
Ilan Komargodski, Omri Weinstein
We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task (as opposed to artificial random h…
Hardness-Preserving Reductions via Cuckoo Hashing
Itay Berman, Iftach Haitner, Ilan Komargodski +1
The focus of this work is \emph{hardness-preserving} transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consi…
Distributional Collision Resistance Beyond One-Way Functions
Nir Bitansky, Iftach Haitner, Ilan Komargodski +1
Distributional collision resistance is a relaxation of collision resistance that only requires that it is hard to sample a collision where is uniformly random and i…
Compressing Communication in Distributed Protocols
Yael Tauman Kalai, Ilan Komargodski
We show how to compress communication in selection protocols, where the goal is to agree on a sequence of random bits using only a broadcast channel. More specifically, we present…
Communication with Contextual Uncertainty
Badih Ghazi, Ilan Komargodski, Pravesh Kothari +1
We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributiona…
Secret-Sharing for NP
Ilan Komargodski, Moni Naor, Eylon Yogev
A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a "qualified" subset of parti…