International Association
for Cryptologic Research

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 answers of the prover can be predicted, given the private randomness of the verifier.

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. However, we show that for the class of random self-reducible problems in NP we can avoid the problem relying on the assumption of public-coin differing-inputs obfuscation (Ishai et al., TCC \'15).

Finally, we apply PAoK in the context of leakage-tolerant PKE protocols.

At PKC \'13 Nielsen 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.