# 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  
Lookup table arguments are a powerful tool in zero-knowledge proof systems, enabling a prover to demonstrate that all elements of a vector \(v\in F^{m}\) contained in a predefined table \(T\in\mathbb{F}^{t}\). This is particularly useful in applications where the prover needs to show that certain values belong to a valid set without revealing the values themselves. State-of-the-art approaches for lookup table arguments include Plookup, Baloo, and \(cq\)[12; 13]. Plookup is highly efficient for cases where the table size \(t\) is much smaller than the vector size \(m(t\ll m)\), making it a popular choice for many applications. Baloo and \(cq\), on the other hand, achieve sublinear prover complexity in tt, but their performance degrades for large \(mm\). In VerITAS, Plookup is chosen due to its efficiency and suitability for the system's requirements, particularly when dealing with small tables relative to the size of the input vectors.  
The Schwartz-Zippel lemma is a fundamental result in polynomial algebra that plays a critical role in \(zk\)-SNARKs. It states that for a non-zero n-variate polynomial \(f\) of degree \(d\) and random \(\alpha_{1},\ldots,\alpha_{1}\leftarrow\mathfrak{SF}\):  
\[Pr\Big{[}f\Big{(}\alpha_{1},\ldots,\alpha_{\mathbb{T}}\Big{)}=0\Big{]}\leq \frac{d}{|F|} \tag{5}\]  
This lemma is used extensively in \(zk\)-SNARKs to prove the equality of polynomials. For example, if two polynomials \(f\) and \(g\) agree on a randomly chosen point, the Schwartz-Zippel lemma provides a high probability guarantee that \(f=g\) everywhere. This property is crucial for ensuring the soundness of polynomial-based proofs in \(zk\)-SNARKs [14].  
The Fiat-Shamir transform is a widely used technique for converting interactive proof systems into non-interactive ones [15]. In an interactive protocol, the verifier typically sends random challenges to the prover, which the prover must respond to in order to complete the proof. The Fiat-Shamir transform eliminates the need for interaction by replacing the verifier's challenges with cryptographic hashes of the transcript up to that point. Specifically, the prover computes the challenge as \(H\) (transcript), where \(H\) is a collision-resistant hash function. This approach retains the soundness properties of the original protocol, provided the protocol satisfies special soundness, meaning that a valid proof can only be constructed if the prover knows a valid witness. The Fiat-Shamir transform is a key component of many \(zk\)-SNARK constructions, including those used in VerITAS, as it enables the efficient and non-interactive verification of proofs.  
In VerITAS, these concepts are combined to create a robust and efficient system for verifying the authenticity and integrity of edited images. Lookup table arguments are used to ensure that certain values (e.g., pixel transformations) belong to a valid set, while the Schwartz-Zippel lemma provides the mathematical foundation for proving polynomial equalities in \(zk\)-SNARKs. The Fiat-Shamir transform is employed to make the proof system non-interactive, enabling efficient verification without requiring back-and-forth communication between the prover and verifier. Together, these techniques enable VerITAS to achieve its goals of scalability, privacy, and security in digital content verification. For Post-Quantum VerITAS we use the same approach but modify the concepts to be post-quantum ones.