### Predictable Arguments of Knowledge

Antonio Faonio, 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.

Available format(s)
Publication info
A major revision of an IACR publication in PKC 2017
Keywords
Foundations
Contact author(s)
afaonio @ gmail com
History
2017-01-13: last of 6 revisions
See all versions
Short URL
https://ia.cr/2015/740

CC BY

BibTeX

@misc{cryptoeprint:2015/740,
author = {Antonio Faonio and Jesper Buus Nielsen and Daniele Venturi},
title = {Predictable Arguments of Knowledge},
howpublished = {Cryptology ePrint Archive, Paper 2015/740},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/740}},
url = {https://eprint.iacr.org/2015/740}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.