Projects per year
Abstract
We introduce a new class of protocols called Proofs of Work or Knowledge (PoWorKs). 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 properties, completeness, fsoundness and indistinguishability (where f is a function that determines the tightness of the proof of work aspect) and present a construction that transforms 3move HVZK protocols into 3move publiccoin PoWorKs. 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 oneway functions.
We then showcase PoWorK protocols by presenting a number of applications. We first show how noninteractive PoWorKs can be used to reduce spam email by forcing users sending an email 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 PoWorKs is privacypreserving as it hides the list of the receiver’s approved contacts from the mail server. Our second application, shows how PoWorK can be used to compose cryptocurrencies that are based on proofs of work (“Bitcoinlike”) with cryptocurrencies that are based on knowledge relations (these include cryptocurrencies that are based on “proof of stake”, and others). The resulting PoWorKbased cryptocurrency inherits the robustness properties of the underlying two systems while PoWorKindistinguishability ensures a uniform population of miners. Finally, we show that PoWorK protocols imply straightline quasipolynomial simulatable arguments of knowledge and based on our construction we obtain an efficient straightline concurrent 3move statistically quasipolynomial simulatable argument of knowledge.
We then showcase PoWorK protocols by presenting a number of applications. We first show how noninteractive PoWorKs can be used to reduce spam email by forcing users sending an email 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 PoWorKs is privacypreserving as it hides the list of the receiver’s approved contacts from the mail server. Our second application, shows how PoWorK can be used to compose cryptocurrencies that are based on proofs of work (“Bitcoinlike”) with cryptocurrencies that are based on knowledge relations (these include cryptocurrencies that are based on “proof of stake”, and others). The resulting PoWorKbased cryptocurrency inherits the robustness properties of the underlying two systems while PoWorKindistinguishability ensures a uniform population of miners. Finally, we show that PoWorK protocols imply straightline quasipolynomial simulatable arguments of knowledge and based on our construction we obtain an efficient straightline concurrent 3move statistically quasipolynomial simulatable argument of knowledge.
Original language  English 

Title of host publication  Advances in Cryptology 
Subtitle of host publication  ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 48, 2016, Proceedings, Part II 
Editors  Jung Hee Cheon, Tsuyoshi Takagi 
Place of Publication  Berlin, Heidelberg 
Publisher  Springer Berlin Heidelberg 
Pages  902933 
Number of pages  32 
ISBN (Electronic)  9783662538906 
ISBN (Print)  Print ISBN 9783662538890 
DOIs  
Publication status  Published  9 Nov 2016 
Event  22nd International Conference on the Theory and Application of Cryptology and Information Security  Hanoi, Viet Nam Duration: 4 Dec 2016 → 8 Dec 2016 https://www.iacr.org/conferences/asiacrypt2016/www.asiacrypt2016.org/index.html 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer Berlin Heidelberg 
Volume  10032 
ISSN (Print)  03029743 
Conference
Conference  22nd International Conference on the Theory and Application of Cryptology and Information Security 

Abbreviated title  ASIACRYPT 2016 
Country  Viet Nam 
City  Hanoi 
Period  4/12/16 → 8/12/16 
Internet address 
Fingerprint Dive into the research topics of 'Indistinguishable Proofs of Work or Knowledge'. Together they form a unique fingerprint.
Projects
 1 Finished

Panoramix:Privacy and Accountability in Networks via Optimized Randomized Mixnets
1/09/15 → 31/01/19
Project: Research