# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 9 Efficient Signature Verification in Post-Quantum VerITAS
### Proof System for the Lattice Hash
#### 9.3.6 Range Proof in Permutation Arguments  
The goal is to prove that all elements of a vector \(v\in F^{m}\) are in the range \([0,b-1]\). This is achieved using a lookup table \(u_{b}=(0,1,\ldots,b-1)\) and proving that \(v\) is a subset of \(u_{b}\) through polynomial commitments.  
The prover constructs a sorted vector \(z=sort(v\|u_{b})\) and encodes it as a polynomial \(z(X)=\text{poly}(z)\). The proof involves demonstrating that \(z(X)\) is a permutation of \(v(X)\|u(X)\) and that the elements of \(z(X)\) satisfy the required range constraints.  
The steps are the following:  
Prover:  
Construct \(z=\text{sort}(v\|u_{b})\) and \(z(X)=\text{poly}(z)\)  
Commit to \(z(X):\text{com}_{z}\).  
Prove \(z(X)\) is a permutation of \(v(X)\|u(X)\) using PermCheck:  
\[\pi_{PC}\gets P_{PC}(pp,com_{u},com_{v},com_{z};u,v,z,0,r_{v},r_{z}) \tag{19}\]  
Construct \(f(X)=(z(\omega X)-z(X))\cdot(z(\omega X)-z(X)-1)\).  
Prove \(f(X)=0\) on \(\Omega_{m+b}\) using ZeroCheck:  
\[\pi_{ZC}\gets P_{ZC,m+b}\Big{(}pp,com_{f};f,r_{f}\Big{)} \tag{20}\]  
Output proof \(\pi=(\text{com}_{z},\pi_{\text{PC}},\pi_{\text{ZC}})\).  
Verifier:  
Parse \(\pi=(\text{com}_{z},\pi_{\text{PC}},\pi_{\text{ZC}})\).  
Compute \(com_{u}=commit(pp,poly(u_{b}),0)\).  
Verify:  
accept if \(V_{PC}(\text{pp},\text{com}_{u},\text{com}_{v},\text{com}_{z};\pi_{\text{PC}})\) and \(V_{ZC,m+b}\Big{(}\text{pp},\text{com}_{f};\pi_{\text{ZC}}\Big{)}\) both accept.  
It works as \(z(\omega X)\) represents a shifted version of the polynomial \(z(X)\). If \(z(X)\) evaluates to \(z_{i+1}\) at \(X=\omega^{i}\), then \(z(\omega X)\) evaluates to \(z_{i+1}\) at \(X=\omega^{i}\). This is because \(z(\omega\cdot\omega^{i})=z(\omega^{i+1})=z_{i+1}\).  
This theorem states that the proof system is secure.  
**Theorem 1**.: _Suppose that \((P_{ZC},V_{ZC})\) and \((P_{PC},V_{PC})\) are \(zk\)-SNARKs for \(R_{ZC}\) and \(R_{PC}\) respectively. Further, suppose that the polynomial commitment scheme used is secure. Then, the proof system in Algorithms 1 and 2 is a \(zk\)-SNARK for the relation._  
\[R_{RP}:=\{((pp,b,com_{v});(v,r_{v})):v\in F^{<m}[X], \tag{21}\] \[\forall\omega\in\Omega_{m}:v(\omega)\in[0,b-1]\text{ for }b\in N,\] \[\text{com}_{v}=commit(pp,v,r_{v})\}\]```
Input: \(v\), auxiliary vector \(u_{b}\), randomness \(r_{v},r_{z},r_{f}\), public parameters \(pp\)  Concatenate and sort: \(z:=\text{sort}(v\|u_{b})\) \(z(X):=\text{poly}(z)\)  Commit to sorted polynomial: \(\text{com}_{z}:=\text{commit}(pp,z(X),r_{z})\)  Permutation proof: \(\pi_{PC}:=P_{PC}(pp,\text{com}_{u},\text{com}_{v},\text{com}_{z};u,v,z,0,r_{v},r_{z})\) Range check polynomial: \(f(X):=(z(\omega X)-z(X))\cdot(z(\omega X)-z(X)-1)\) ZeroCheck proof: \(\pi_{ZC}:=P_{ZC,m+b}\Big{(}pp,\text{com}_{f};f,r_{f}\Big{)}\) Output: \(\pi:=(\text{com}_{z},\pi_{PC},\pi_{ZC})\)
```

**Algorithm 1**Range Proof Construction (Prover Side)

``` Input: \(\pi:=(\text{com}_{z},\pi_{PC},\pi_{ZC})\)  Compute \(\pi_{PC}\), \(\pi_{ZC  
This relation ensures that \(v\) is a valid preimage of \(h\) under the linear transformation \(A\), and that \(v\) adheres to the low-norm constraint.  
The prover must take the following steps:  
* Commit to \(v(X)=poly(v):com_{v}\).
* Prove \(\|v\|_{\infty}<b\) using the Range Proof system.
* Prove \(h=A\cdot v\) using a univariate SumCheck proof:
* Reduce \(h=A\cdot v\) to a single dot-product using a random linear combination of rows of \(A\).
* Use the Fiat-Shamir transform to make the protocol non-interactive. The verifier must take the following steps:
* Verify the Range Proof and SumCheck proof. Accept if both proofs are valid.