Chuhan Lu

Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary family (PRU). Their proof developed a new path recording technique. In this work, we show that a linear number of sequential repetitions of the parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQSY+24], also forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications.

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.