University of Tartu - ©2011 Dominique Peer Ghislain Dr Unruh - Last update: 02.11.2015 13:05
Date: Wednesday, 04/11/2015, 2:15pm
Location: J. Liivi 2, room 317 (next to the coffee room)
Title: Proof of Work or Knowledge
Abstract:
We introduce a new class of protocols called Proofs of Work or Knowledge (PoWorK’s). In a PoWorK, a prover can convince a verifier that she has either performed work or that she possesses knowledge of a witness to a public statement without the verifier being able to distinguish which of the two has taken place. We formalize PoWorK in terms of three basic properties, completeness, f-soundness and indistinguishability (where f is a function that determines the tightness of the proof of work aspect) and present a construction that transforms 3-move HVZK protocols into 3-move public-coin PoWorK’s. To formalize the work aspect in a PoWorK protocol we define cryptographic puzzles that adhere to certain uniformity conditions, which may also be of independent interest. We instantiate our puzzles in the random oracle (RO) model as well as via constructing “dense” versions of suitably hard one-way functions.
We then showcase PoWorK protocols by presenting two applications. We first show how non-interactive PoWorK’s can be used to reduce spam email by forcing users sending an e-mail to either prove to the mail server they are approved contacts of the recipient or to perform computational work. As opposed to previous approaches that applied proofs of work to this problem, our proposal of using PoWorK’s is privacy-preserving as it hides the list of the receiver’s approved contacts from the mail server. Our second application for PoWorK relates to zero-knowlege protocols. We show that PoWorK protocols imply straight-line quasi-polynomial simulatable arguments of knowledge; by applying this result to our construction we obtain an efficient straight-line concurrent 3-move statistically quasi-polynomial simulatable argument of knowledge, improving the round complexity of the previously known four-move protocols.
Bio: Dr. Bingsheng Zhang is Lecturer (a.k.a. assistant professor) in Security of Cyber-Physical Systems in the School of Computing and Communications at Lancaster University since September 2015 and member of Security Lancaster research centre. Before that, he was a postdoctoral researcher at Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Greece. He received his B. Eng. in computer science from Zhejiang University of Technology in 2007, his M. Sc. in information security from University College London in 2008, and his Ph.D. degrees in computer science from University of Tartu in 2011. He then worked as a postdoctoral researcher at Department of Computer Science and Engineering, State University of New York at Buffalo, USA.