# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 6 Cryptographic Foundations and Preliminaries
### Lookup Tables, Polynomial Testing, and Non-Interactive Proofs
#### 6.3.1 Plonk: Arithmetic Circuit Evaluation and Permutation Arguments  
A core component of zero-knowledge proof systems is the ability to prove the correct evaluation of an arithmetic circuit. An arithmetic circuit consists of gates that perform operations (e.g., addition, multiplication) on input values, producing intermediate and output values. To prove that a circuit has been evaluated correctly, the prover must demonstrate that all gate constraints and copy constraints are satisfied. This is achieved through a computation trace, which is a table representing the circuit's execution, where each row corresponds to a gate. The trace includes the inputs, outputs, and intermediate values of the circuit [16].  
The gate constraints ensure that each gate operates correctly. For example, for a gate with inputs \(In_{0}\) and \(In_{1}\), output Out, and operation \(Op\), the constraint \(Op(In_{0},In_{1})=Out\) must hold. Additionally, copy constraints ensure that wires connected across gates share the same values. For instance, if the output of one gate is the input to another, the corresponding cells in the trace must have the same value. These constraints are critical for maintaining the consistency of the circuit's execution.  
In the context of VerITAS, the arithmetic circuit represents the transformation of an image from its original form to its edited form. The circuit's wire types include the following:  
Public Instance \(x\): the published edited photo, which is known to the verifier.  
Secret Witness \(w\): the original signed image (e.g., from a camera), which is kept private.  
Internal Wires \(y\): intermediate values generated during the transformation process.  
To enforce copy constraints, VerITAS employs a permutation argument. The goal of the permutation argument is to prove that certain cells in the computation trace are permutations of one another, ensuring that connected wires share the same values. The process involves interpolating the trace values into a polynomial \(T(x)\) and defining a permutation \(\tau\) such that \(\tau(s_{1})=s_{2},\tau(s_{2})=s_{3},\dots,\tau(s_{l})=s_{1}\) for copy constraints. The prover then demonstrates that \(T(s)=T(\tau(s))\) for all \(s\in\Omega\), where \(\Omega\) is a set of evaluation points. The output of the permutation argument is a commitment to the polynomials \(T\) and \(\tau\), which proves that the copy constraints are satisfied. The process is illustrated on Figure 2.  
In VerITAS, the permutation argument is modified to optimize proofs for computationally powerful signers, such as those in cloud-based systems. This modification reduces the overhead associated with proving photo editing transformations, making the system more efficient for high-resolution images. By leveraging the permutation argument, VerITAS ensures that the integrity of the editing process is maintained, while preserving the privacy of the original image. The combination of arithmetic circuit evaluation and permutation arguments enables VerITAS to provide a robust and efficient framework for verifying the authenticity and integrity of edited images. These techniques ensure that the transformation process is both correct and consistent, while the use of zero-knowledge proofs guarantees that sensitive information about the original image remains hidden. This makes VerITAS a powerful tool for applications in journalism, media, and digital content verification. For Post-Quantum VerITAS, we use HyperPlonk.  
Figure 2: Plonk.