# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 9 Efficient Signature Verification in Post-Quantum VerITAS  
The signature verification process is a critical component of ensuring the authenticity of digital images. It involves the following two main steps: computing a hash of the original image and verifying the signature on that hash. Specifically, given an original image \(w\), the process computes a hash \(h\ \leftarrow\ H(w)\), where \(H\) is a collision-resistant hash function. The signature \(\sigma\sigma\) is then verified to ensure it is a valid signature on \(h\) under the camera's public key \(vk\). While this process is straightforward for small data, it becomes computationally challenging for large data, such as 30-megapixel (30 MP) photos, where most of the time is spent computing the hash \(h\).  
The challenge is further compound when using \(zk\)-SNARKs to prove the correctness of the hash computation. Proving that \(h=H(w)\) within a SNARK circuit is computationally expensive, especially for large images. Standard hash functions, like SHA256 or SHA512 for post-quantum settings, are inefficient in SNARKs, because they rely on non-algebraic operations, such as logical operations, which are not well-suited for the arithmetic circuits used in SNARKs. As a result, proving SHA256/SHA512 for a 30 MP image is infeasible in practice. Even Poseidon, a hash function specifically designed to be SNARK-friendly, struggles with the sheer size of 30 MP images, making it impractical for direct use in such scenarios.  
To address these challenges, Post-Quantum VerITAS introduces the following two innovative solutions: a lattice-based hash combined with edited Poseidon and a polynomial commitment scheme. The lattice-based hash system is post-quantum and bout Poseidon hash; we offer how to make it post-quantum in the next section. The first solution leverages the strengths of both lattice-based hashes and Poseidon hashes. The lattice-based hash is highly efficient for processing large data, reducing a 90 MB image to a compact 4 KB digest. This digest is then further hashed using Poseidon, which compresses it to 32 bytes [19; 20]. The lattice-based hash is particularly well-suited for SNARKs, because it relies on linear operations, which are efficient to prove in arithmetic circuits. By combining these two hash functions, Post-Quantum VerITAS achieves a balance between efficiency and SNARK-friendliness, making it feasible to handle 30 MP images.  
The second solution involves using a polynomial commitment scheme. In this approach, the signer computes a polynomial commitment to the image, which serves as a compact representation of the data. The advantage of this method is that it eliminates the need to prove \(h=H(w)\) within the SNARK circuit. Instead, the prover can directly work with the polynomial commitment, significantly reducing the computational overhead. This approach is particularly beneficial for computationally powerful signers, such as cloud-based systems, where the additional resources required for polynomial commitments are readily available.  
Together, these solutions enable Post-Quantum VerITAS to efficiently verify the authenticity of large images, while maintaining the privacy and security guarantees of zero-knowledge proofs. By combining lattice-based hashes, Poseidon hashes, and polynomial commitments, Post-Quantum VerITAS overcomes the limitations of standard hash functions and provides a scalable framework for verifying the provenance of digital content. These innovations represent a significant advancement in the field of image provenance, making it possible to handle high-resolution images in real-world applications.