We propose Phecda, a new framework to produce quantum-resistant transparent zkSNARKs in the Random Oracle Model. Phecda features a novel multi-linear polynomial commitment scheme and a novel VOLE-in-the-Head zero-knowledge argument, offering a versatile solution for verifying many real-world computations. In particular, we invent a novel AES verification circuit, which, combined with Phecda, allows to verify 1024 blocks of AES in the counter-mode in 10ms using a single-thread program running on a Linux PC.

Abstract This paper revisits Virgo, a well-known transparent zero-knowledge proof system that has been used in many subsequent studies. Through our analysis, we uncover previously overlooked limitations and several exploitable security vulnerabilities within Virgo’s zkVPD protocol design and implementation. We subsequently address these issues and improve Virgo’s zkVPD protocol. Our improvements feature simplified but more efficient VPD and zkVPD algorithms, offering enhanced support for computations over binary fields and their extension fields.

We present a new efficient two-party secure computation protocol which allows the honest party to catch dishonest behavior (if any) with a publicly-verifiable, non-repudiable proof without sacrificing the honest party's secret. Comparing to the best existing protocol of its kind, ours requires a substantially simpler judge algorithm and is able to process circuit evaluator's input-wires two orders of magnitude faster. Further, we propose an automated, decentralized judge implemented as a blockchain smart-contract. As a killer application of combining our two-party PVC protocol with our decentralized judge, we proposed the concept of financially-secure computation, which can be useful in many practical scenarios where it suffices to consider rational adversaries. We experimentally evaluated our prototype implementation, demonstrated the 2PC protocol is highly efficient and the judge is very affordable to protect users against rational attackers.