# Combating Fake News with Cryptography in Quantum Era with Post-Quantum Verifiable Image Proofs
## 9 Efficient Signature Verification in Post-Quantum VerITAS
### Post-Quantum Poseidon  
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.  
To make the Poseidon hash function post-quantum-secure, we must address the vulnerabilities that quantum computers could exploit, such as [PERSON]'s algorithm and [PERSON]'s algorithm. Poseidon is not inherently quantum-resistant, because its design is based on classical security assumptions, and its efficiency for zero-knowledge proof systems does not account for quantum computational power. To achieve post-quantum security, we must modify Poseidon in the following concrete manner:  
To achieve quantum resistance, we increase the output size, use larger finite fields, and enhance the permutation layer. Quantum algorithms, particularly [PERSON]'s algorithm, can perform a brute-force search in \(O\big{(}\surd N\big{)}\) time, where \(N\) is the size of the search space. For an n-bit hash function, this reduces the effective security from \(2^{N}\) to \(2^{n/2}\). To mitigate this,therefore, we double the output size of Poseidon and extend other parameters accordingly. For example, if Poseidon currently uses a 256-bit output, we must increase it to 512 bits to achieve 256-bit post-quantum security. This ensures that even with [PERSON]'s algorithm, the security level remains sufficiently high.  
To ensure that the modified Poseidon hash is resistant to known quantum threats, we introduce the following concrete parameter choices:  
* Output Size: Increased from 256 bits to 512 bits to maintain 256-bit post-quantum security, mitigating [PERSON]'s algorithm which offers a quadratic speedup in brute-force hash searches.
* Finite Field: We use a prime field \(\mathbb{F}_{p}\) with \(p>2^{512}\) to ensure sufficient entropy against quantum adversaries capable of exploiting algebraic structures, thus neutralizing attacks like [PERSON]'s algorithm on small fields.
* Number of Rounds: Increased from the original Poseidon default (e.g., 8 full + 56 partial) to 16 full + 96 partial rounds. This enhances resistance against differential, linear, and quantum algebraic attacks.
* S-Box Nonlinearity: We replace quadratic S-boxes with quartic (\(x^{4}\)) S-boxes to increase algebraic complexity and diffusion in the quantum setting.  
These modifications result in a \(\sim 30-40\%\) increase in computational cost per hash due to larger state size and increased round function complexity. However, these costs are mitigated through parallelization of tiles and optimizations using zk-SNARK-friendly arithmetic gates, as discussed in Section 10.  
Larger finite fields are used to resist algebraic attacks, and the permutation layer is enhanced with additional rounds and stronger S-boxes to counter quantum cryptanalysis. Quantum algorithms, like [PERSON]'s algorithm, can efficiently solve problems, such as discrete logarithms and factoring in certain algebraic structures. To address this, we must use larger finite fields, such as fields with 512-bit or larger primes. This makes it significantly harder for quantum algorithms to exploit the algebraic structure of the hash function.  
Finally, we must strengthen the permutation layer, as the security of Poseidon depends on its permutation layer, which consists of rounds of nonlinear operations (e.g., S-boxes) and linear transformations. Quantum computers could potentially exploit weaknesses in this layer. To strengthen it, we must increase the number of rounds and use stronger S-boxes or nonlinear components that are specifically designed to resist quantum cryptanalysis. For example, we can use higher-degree nonlinear functions (e.g., cubic or quartic functions) instead of quadratic functions for the S-boxes, ensuring they have strong differential and linear properties. Additionally, we should optimize the linear layer (e.g., MDS matrices) to maximize diffusion and resist quantum attacks.