We show that predictable arguments of knowledge (PAoK) can be made extremely laconic, with the prover sending a single bit, and assumed to have only one round (two messages) without loss of generality. We then explore constructs of PAoK. For specific relations we obtain PAoK from Extractable Hash Proof systems (Wee, Crypto '10); we also show that PAoK are equivalent to Extractable Witness Encryption. Unfortunately, the latter poses serious doubts on the existence of PAoK for all \NP.
Finally, we apply PAoK in the context of leakage-tolerant PKE protocols. At PKC '13 Nielsen {\em et al.} have shown that any leakage-tolerant PKE protocol requires long keys already when it tolerates super-logarithmic leakage. We strengthen their result proving a more fine-grained lower bound for any constant numbers bits of leakage. Moreover, we consider an adaptive-secure definition for PAoK. In this stronger model the challenge generation algorithm is independent of the instance proved, the extraction is guaranteed for adversarial chosen instances.
Category / Keywords: foundations / Date: received 23 Jul 2015, last revised 12 Oct 2015 Contact author: afaonio at gmail com Available format(s): PDF | BibTeX Citation Version: 20151012:133533 (All versions of this report) Short URL: ia.cr/2015/740 Discussion forum: Show discussion | Start new discussion