Predictable arguments of knowledge

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We initiate a formal investigation on the power of 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 constructions of PAoK relying on different cryptographic tools, and discuss applications to cryptography.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
EditorsSerge Fehr
Number of pages30
PublisherSpringer VS
Publication year2017
ISBN (print)9783662543641
ISBN (Electronic)978-3-662-54365-8
Publication statusPublished - 2017
Event20th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2017 - Amsterdam, Netherlands
Duration: 28 Mar 201731 Mar 2017


Conference20th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2017
By Amsterdam
SponsorInternational Association for Cryptologic Research (IACR)
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 119023685