Nikhil Pappu

It is well-known in classical cryptography that standard (black-box) proof techniques are insufficient to establish the security of statistical NIZK arguments for NP based on any standard (falsifiable) cryptographic assumption. In this work, we extend this impossibility result to a quantum scenario where quantum computations and communications are incorporated into the protocol. The classical result is demonstrated using the meta-reduction paradigm, which is a typical technique employed to generate cryptographic impossibility results. In our work, we extend this technique to the quantum setting to prove our results.

Succinct Non-interactive Arguments (SNARGs) are cryptographic protocols that enable a prover to demonstrate the validity of an $\NP$ statement to a verifier using a single message of size poly-logarithmic in the size of the $\NP$ statement and witness. Currently, SNARGs are only known to exist based on non-standard cryptographic assumptions, and were shown to be inherently challenging to obtain from standard assumptions by the work of \cite{STOC:GenWic11}. The work proved that standard (black-box) proof techniques are insufficient to prove the security of a SNARG based on any standard (falsifiable) cryptographic assumption. We extend the result of \cite{STOC:GenWic11} to the quantum setting, where parties can perform quantum computations and communicate using quantum information. The result of \cite{STOC:GenWic11} uses the meta-reduction paradigm, which is a general technique for obtaining cryptographic impossibility results. To obtain our result, we extend the above paradigm to the quantum setting, which we believe to be of independent interest.