TY - GEN

T1 - Indistinguishable proofs of work or knowledge

AU - Baldimtsi, Foteini

AU - Kiayias, Aggelos

AU - Zacharias, Thomas

AU - Zhang, Bingsheng

PY - 2016/12/4

Y1 - 2016/12/4

N2 - 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 formalise 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 formalise 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 implystraight-line quasi-polynomial simulatable arguments of knowledge and basedon our construction we obtain an efficient straight-line concurrent 3-move statistically quasi-polynomial simulatable argument of knowledge.

AB - 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 formalise 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 formalise 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 implystraight-line quasi-polynomial simulatable arguments of knowledge and basedon our construction we obtain an efficient straight-line concurrent 3-move statistically quasi-polynomial simulatable argument of knowledge.

KW - proof of work

KW - cryptographic puzzle

KW - concurrent zero-knowledge

KW - dense one-way functions

KW - cryptocurrencies

U2 - 10.1007/978-3-662-53890-6_30

DO - 10.1007/978-3-662-53890-6_30

M3 - Conference contribution/Paper

SN - 9783662538890

T3 - Lecture Notes in Computer Science

SP - 902

EP - 933

BT - Advances in Cryptology – ASIACRYPT 2016

A2 - Cheon, Jung Hee

A2 - Takagi, Tsuyoshi

PB - Springer

CY - Heidelberg

ER -