# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 6 Cryptographic Foundations and Preliminaries
### zk-SNARKs  
Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) are cryptographic protocols that enable one party (the prover) to prove to another party (the verifier) that a statement is true without revealing any additional information. zk-SNARKs are widely used in privacy-preserving applications due to their efficiency and strong security guarantees [11]. A zk-SNARK consists of the following three main algorithms: setup, prove, and verify.  
* _setup_\(\left(1^{\lambda}\right)\to pp\colon\) Generates public parameters.
* _prove_\(\left(pp,x,w\right)\to\pi\colon\) Generates proof \(\pi\) for instance \(x\) and witness \(w\).
* \(Vf\left(pp,x,\pi\right)\to 0/1\colon\) Verifies the proof.  
A zk-SNARK must satisfy several key properties. First, it must be complete; if the prover knows a valid witness \(w\) for the instance \(x\), the verifier will always accept the proof \(\pi\). Second, it must be knowledge-sound; if the prover can generate a valid proof \(\pi\pi\) for an instance \(x\), they must know a valid witness \(w\) for \(x\), ensuring that the prover cannot cheat by creating proofs for false statements. Third, it must be zero-knowledge; the proof \(\pi\) reveals no information about the witness \(w\) beyond the fact that the statement is true, ensuring privacy. Fourth, it must be non-interactive; proofs are standalone and require no interaction between the prover and the verifier, making zk-SNARKs highly efficient for real-world applications. Finally, it must be succinct; the size of the proof \(\pi\) and the time required to verify it are small, typically sublinear in the size of the witness \(w\), making zk-SNARKs scalable for complex computations.  
In VerITAS and in the post-quantum offer, zk-SNARKs play a critical role in ensuring the authenticity and integrity of edited images while preserving privacy. The system uses the following two types of zk-SNARKs: a custom zk-SNARK and a general-purpose zk-SNARK. The custom zk-SNARK is designed specifically for proving the correctness of lattice-based hash computations. It is optimized for the linear operations used in lattice hashes, making it highly efficient for large-scale image processing. The general-purpose zk-SNARK, on the other hand, is used for proving the correctness of Poseidon hashes and photo transformations. It is based on widely adopted cryptographic primitives and is suitable for a broad range of computations. Additionally, Post-Quantum VerITAS employs Hyper Plonk, a system for writing and verifying PLONK-based circuits. Hyper Plonk is a state-of-the-art zk-SNARK framework that combines efficiency with flexibility, enabling Post-Quantum VerITAS to handle complex image editing operations, while maintaining succinct proofs and fast verification and having resilience to quantum attacks.  
In Post-Quantum VerITAS, zk-SNARKs are used to prove that an image has been edited in a permissible way without revealing the original content, verify the authenticity of the original image and its signature, and ensure that the editing process preserves the integrity of the image. By combining custom and general-purpose zk-SNARKs, Post-Quantum VerITAS achieves a balance between efficiency and versatility, making it suitable for real-world applications in journalism, media, and digital content verification. By means of post-quantum \(zk\)-SNARKS, we make it usable in post-quantum settings.