4 papers · 1 filter
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…
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…