# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 4 Efficient zk-SNARKs for Large-Scale Image Provenance  
We now describe the techniques that enable Post-Quantum VerITAS to remain scalable and efficient, even when processing high-resolution images. This section outlines the cryptographic optimizations that make such performance feasible. Post-Quantum VerITAS, like the original VerITAS framework, relies on a prover, typically a newsroom editor, to generate cryptographic proofs that validate the authenticity of edited images. Given an edited image \(x\) and an editing function \(f\), the prover demonstrates two key facts. The original image \(w\) was signed with a valid signature \(\sigma\) under a public verification key \(vk\). Applying the editing function \(f\) to the original image \(w\) results in the edited image \(x\). This process is formalized through a \(zk\)-SNARK instance-witness relation \(R\), defined as follows:  
\[R:=\{((vk,f,x);(w,\sigma)):f(w)=x\wedge SigVerify(vk,w,\sigma)=1\} \tag{1}\]  
Here, the instance consists of the public verification key \(vk\), the editing function \(f\), and the edited image \(x\). The witness includes the original image \(w\) and its signature \(\sigma\). The prover's task is to demonstrate that the witness satisfies the relation \(R\) without revealing \(w\) or \(\sigma\), preserving the privacy of the original content. A significant challenge in implementing this \(zk\)-SNARK-based approach is the computational inefficiency of proving operations on large-scale data. The witness (\(w\), \(\sigma\)) includes a 30-megapixel image, which can be approximately 90 MB in size. Proving the hashing of such large data, whether using SHA256/SHA512 or more \(zk\)-SNARK-friendly hash functions, like Poseidon, is computationally expensive and impractical for real-world applications. This inefficiency stems from the inherent complexity of proving cryptographic operations within zero-knowledge proof systems, particularly for high-resolution images. Because of the rapid development of quantum computers, the system must be resistant against attacks by quantum computers. To address this challenge, Post-Quantum VerITAS introduces a custom proof system optimized for the efficient hashing of large images. This system leverages innovative techniques to reduce the computational overhead associated with proving operations on high-resolution data. By streamlining the hashing process within the \(zk\)-SNARK framework, VerITAS enables scalable proofs for 30-megapixel images, making it the first system capable of handling such large-scale data efficiently. Our modification makes it post-quantum. The key innovation lies in the system's ability to decompose the image into smaller, manageable components and process them in a way that minimizes the proving time while maintaining the integrity of the proof. \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Feature** & **C2 PA** & **VerITAS** & **Post-Quantum VerITAS** \\ \hline Edit Tolerance & Low (re-sign only) & High (zk-SNARKs) & High (zk-SNARKs + PQ) \\ \hline Quantum Resilience & \(\times\) & \(\times\) & \\ \hline Privacy-Preserving Proofs & \(\times\) & & \\ \hline Real-Time Proofs (30 MP) & \(\times\) & Partially & \\ \hline Trust in Editor Software & Required & Not required & Not required \\ \hline Compatible with Open Tools & Limited & Yes & Yes \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of provenance frameworks. This decomposition involves splitting the original high-resolution image into its red, green, and blue (RGB) color channels and further dividing each channel into fixed-size pixel tiles. These tiles are independently hashed and committed in parallel to reduce the witness size per SNARK circuit. To achieve post-quantum security, we must modify Poseidon in the following concrete manner, which allows for efficient vector-to-polynomial encoding and parallel proof construction. A detailed explanation of this process is provided in Section 9.2, where we describe the polynomial encoding and lattice hash commitment process for each color vector.