# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 6 Cryptographic Foundations and Preliminaries
### Commitment Schemes  
Commitment schemes are fundamental cryptographic primitives that enable a party to commit to a value while keeping it hidden until revealed. These schemes are essential for ensuring data integrity and privacy in protocols, such as zero-knowledge proofs and verifiable computation [7]. This section formally defines commitment schemes and their properties, followed by an introduction to polynomial commitment schemes, which are a specialized form of commitments used in Post-Quantum VerITAS.  
Algorithms:  
* setup (\(1^{\lambda}\))\(\rightarrow\) pp: Generates public parameters.
* commit (\(pp,x,r\))\(\rightarrow\)com: Commits to \(x\) with randomness \(r\).
* Opening: Committer reveals \(x\) and \(r\); verifier checks commit \((x,r)=com\).
* A commitment scheme must satisfy the following two key properties:
* Hiding: The commitment com reveals no information about the value \(x\).
* Binding: The committer cannot change the value \(xx\) after producing the commitment com.  
Polynomial commitment schemes extend the concept of commitment schemes to polynomials. They allow a party to commit to a polynomial \(f\in F[X]\) of degree \(\leq d\) and later prove the evaluations of the polynomial at specific points [8]. A polynomial commitment scheme consists of the following algorithms:  
* setup (\(1^{\lambda},d\)) \(\rightarrow\)\(pp\): Generates public parameters for degree \(d\).
* commit (\(pp\), \(f,r\)) \(\rightarrow\)\(com\): Commits to polynomial \(f\).
* open (\(pp,f,x,r\)) \(\rightarrow(\pi,y)\): Generates proof \(\pi\) that \(f(x)=y\).
* \(Vf\) (\(pp,com,x,y,\pi\)) \(\rightarrow\)\(0/1\): Verifies the proof.  
Polynomial commitment schemes are widely used in cryptographic protocols, including zero-knowledge proofs and verifiable computation, due to their ability to efficiently prove polynomial evaluations without revealing the polynomial itself.  
The KZG (Kate-Zaverucha-Goldberg) polynomial commitment scheme is a widely used construction based on bilinear pairings. It offers constant-sized commitments and proofs, making it highly efficient for applications requiring succinctness. The KZG scheme relies on the hardness of the discrete logarithm problem in pairing-friendly elliptic curves [9].  
The FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) polynomial commitment scheme is an alternative approach that uses collision-resistant hash functions instead of pairings. FRI is particularly well-suited for scenarios where pairing-friendly curves are unavailable or impractical. It leverages the properties of Reed-Solomon codes and interactive oracle proofs to achieve efficient commitments and proofs [10].  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Meaning** \\ \hline \(\pi\) & Zero-knowledge proof \\ \hline \(pk,vk\) & Public/verification key \\ \hline \(\mathcal{L}\) & Lattice structure/matrix \\ \hline \(R,G,B\) & Red, green, blue image channels \\ \hline \(\sigma\) & Signature \\ \hline \hline \end{tabular}
\end{table}
Table 2: _Cont._KZG offers constant-sized proofs and is highly efficient for low-degree polynomials. However, it requires pairing-friendly curves, which may limit its applicability in some settings. FRI, does not rely on pairings, making it more versatile. However, its proofs are larger, and verification is less efficient compared to KZG. Both schemes are integral to modern cryptographic protocols, including VerITAS, where polynomial commitments are used to prove the authenticity and integrity of edited images. The choice between KZG and FRI depends on the specific requirements of the application, such as proof size, verification efficiency, and the availability of cryptographic primitives. As we offer Post-Quantum VerITAS, we use FRI in our approach.