Cryptology ePrint Archive: Report 2015/740

Predictable Arguments of Knowledge

Antonio Faonio and Jesper Buus Nielsen and Daniele Venturi

Abstract: We initiate a formal investigation on the power of {\em predictability} for argument of knowledge systems for \NP. Specifically, we consider private-coin argument systems where the answer of the prover can be predicted, given the private randomness of the verifier; we call such protocols Predictable Arguments of Knowledge (PAoK).

Our study encompasses a full characterization of PAoK, showing that such arguments can be made extremely laconic, with the prover sending a single bit, and assumed to have only one round (i.e.,\ two messages) of communication without loss of generality.

We additionally explore PAoK satisfying additional properties (including zero-knowledge and the possibility of re-using the same challenge across multiple executions with the prover), present several constructs of PAoK relying on different cryptographic tools, and discuss applications to cryptography.

Category / Keywords: Foundations

Original Publication (with major differences): IACR-PKC-2017

Date: received 23 Jul 2015, last revised 13 Jan 2017

Contact author: afaonio at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170113:113751 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]