Indistinguishable Proofs of Work or Knowledge

Foteini Baldimtsi, Aggelos Kiayias, Thomas Zacharias, Bingsheng Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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, 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 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 one-way functions.

We then showcase PoWorK protocols by presenting a number of applications. We first show how non-interactive PoWorKs 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 PoWorKs is privacy-preserving 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 (“Bitcoin-like”) with cryptocurrencies that are based on knowledge relations (these include cryptocurrencies that are based on “proof of stake”, and others). The resulting PoWorK-based cryptocurrency inherits the robustness properties of the underlying two systems while PoWorK-indistinguishability ensures a uniform population of miners. Finally, we show that PoWorK protocols imply straight-line quasi-polynomial simulatable arguments of knowledge and based on our construction we obtain an efficient straight-line concurrent 3-move statistically quasi-polynomial simulatable argument of knowledge.
Original languageEnglish
Title of host publicationAdvances in Cryptology
Subtitle of host publicationASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II
EditorsJung Hee Cheon, Tsuyoshi Takagi
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages32
ISBN (Electronic)978-3-662-53890-6
ISBN (Print)Print ISBN 978-3-662-53889-0
Publication statusPublished - 9 Nov 2016
Event22nd International Conference on the Theory and Application of Cryptology and Information Security - Hanoi, Viet Nam
Duration: 4 Dec 20168 Dec 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Conference22nd International Conference on the Theory and Application of Cryptology and Information Security
Abbreviated titleASIACRYPT 2016
Country/TerritoryViet Nam
Internet address


Dive into the research topics of 'Indistinguishable Proofs of Work or Knowledge'. Together they form a unique fingerprint.

Cite this