Nikhil Pappu

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.

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.