# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 9 Efficient Signature Verification in Post-Quantum VerITAS
### Input Representation and Hash Verification Using Lattice and Poseidon Hashes  
The input photo, denoted as \(w\), is decomposed into three low-norm vectors corresponding to the red, green, and blue (RGB) color channels. These vectors are represented as \(v_{r}\), \(v_{g}\), \(v_{b}\), respectively. Each vector has a length of \(m\), where \(m\) corresponds to the number of pixels in the image, and the pixel values in each vector are constrained to the range \([0,255]\), ensuring compatibility with standard image formats. To compute the lattice hash, each of the RGB vectors is multiplied by a randomly generated matrix \(A\), where \(A\in F_{q}q^{\{n\times m\}}\). The multiplication is performed by modulo \(q\), resulting in the transformation \(h=A\cdot v\)_mod_, where \(h\) represents the intermediate hash output for each color channel. This step ensures that the high-dimensional pixel data is compressed into a lower-dimensional representation, while preserving the structural properties of the image. The output of the lattice hash is further processed using the Poseidon hash function, a cryptographic hash designed for efficiency in zero-knowledge proof systems. The final hash is computed as follows:  
\[H(v)=Poseidon(A\cdot v\ modq) \tag{7}\]  
providing an additional layer of security and ensuring that the hash output is both compact and suitable for verification in zero-knowledge proof systems. The hashing procedure is illustrated in Figure 3.  
The input image is decomposed into red, green, and blue channels, each of which is hashed using a lattice-based method. The resulting digest is then compressed using a post-quantum Poseidon hash, yielding a SNARK-compatible 512-bit output. The verification of the hash involves proving a specific relation, denoted as \(R_{VH}\), which is defined as follows:  
\[R_{\mathrm{VH}}:=\{((A,h,b);v):h=\mathrm{Poseidon}(A\cdot v),\left\|v\right\|_{ \infty}<b\} \tag{8}\]  
This relation ensures that the prover knows a valid vector \(\mathbf{v}\) that satisfies the hash computation and adheres to the low-norm constraint \(\left\|v\right\|_{\infty}<b\), which is critical for collision resistance. The proof system for hash verification consists of the following three key components: (1) the prover demonstrates that \(h=A\cdot v\), ensuring the correctness of the linear transformation applied during the lattice hash computation; (2) the prover shows that \(\left\|v\right\|_{\infty}<b\), confirming that the input vector \(v\) adheres to the required norm bound, which is essential for maintaining the collision-resistant properties of the hash function; and (3) using a Groth16 circuit, the prover verifies that the Poseidon hash function was applied correctly to the output of the lattice hash, ensuring the integrity of the final hash computation. In Mode 2, the signer begins by encoding the input image \(w\) as a polynomial:  
\[W(X)=poly(w) \tag{9}\]  
A key insight in this approach is the avoidance of proving com directly in the SNARK circuit by leveraging HyperPlonk's extended permutation argument, which significantly reduces computational overhead. Polynomial commitments are employed for their efficiency, as they eliminate the need to hash \(w\) within the SNARK circuit, and for their binding property, which ensures that com is a valid and secure commitment to the polynomial \(W(X)\). The signer then computes a polynomial commitment using a post-quantum PCS, we use FRI.  
\[com\ \leftarrow\ PCS.commit(pp,\ W,\ r) \tag{10}\]  
Figure 3: Post-quantum image hashing pipeline. where pp represents the public parameters of the commitment scheme, \(W\) is the polynomial representation of the image, and \(r\) is a random blinding factor. The signer proceeds to sign the commitment com to produce a signature \(\sigma\) and sends the tuple \((\textit{rk},\textit{ com},\ \sigma,r)\) to the editor, where \(\textit{rk}\) is the verification key. The editor's task involves producing an edited image. \[x=f(w) \tag{11}\]  
where \(f\) represents the editing function applied to the original image.