FiatShamir Identification  NonInteractive ZeroKnowledge Proofs  Full Implementation
Posted on Fri 25 August 2023 in tech
FiatShamir Identification: NonInteractive ZeroKnowledge Proofs
See full implementation code on GitHub
The ability to prove knowledge of some secret information without revealing the secret itself is crucial. FiatShamir Identification demonstrates how this can be achieved in a way that doesn't require interaction between the prover and verifier. Further, Fiat and Shamir deliberately set out to create a proof which does not leak any knowledge to the verifier. The idea is that the Prover can prove thier identity by revealing precisely 1 bit of inforation, that the proof itself is sound.
What are ZeroKnowledge Proofs?
ZeroKnowledge proofs are a form of probabilistic proof in which a prover typically demonstrates inner knowledge of an intractable problem. The process proceeds in a series of rounds. Each round typically involves the prover comitting to a confounding random value. Then the Verifier sends a challenge to the Prover that the Prover can not anticipate, such as "tell me a fact about your random value". This gives the method an association to the classic "cut and choose" approach to fairness. When two parties wish to share a cake, they say "You cut", "I choose". The prover will be disadvantaged if they make an unfair choice at the start, for example lying about the cake cut or nature of the random value. When the Verifier makes the "choice" over repeated interactions a lie will be punished and in the disinterest of the Prover.
Origins of the FiatShamir Scheme
The FiatShamir Identification Scheme was introduced by Amos Fiat and Adi Shamir in 1985. Originally, it was designed as an interactive proof system for identification. However, the FiatShamir heuristic transformed this interactive system into a noninteractive one, making it more suitable for many cryptographic applications like digital signatures.
How Does It Work?
The FiatShamir Identification, as with other ZK proofs of knowledge, can be understood in three phases:

Commitment: The prover starts by choosing a random value and sending a commitment to the verifier. This commitment does not reveal the chosen value.

Challenge: The verifier then sends a random challenge to the prover. In the interactive version, this challenge would typically be generated fresh for each interaction.

Response: The prover then computes a response based on the secret they wish to prove they possess and the challenge from the verifier. The verifier checks this response against the previously received commitment to decide whether the prover genuinely knows the secret.
The FiatShamir heuristic makes the process noninteractive. Instead of the verifier sending a challenge, the prover uses a cryptographic hash function to generate the challenge from their commitment. This makes the system noninteractive, as the prover can generate the commitment, compute the challenge, and then produce the response, all at once.
Advantages and Implications

NonInteractivity: The most prominent advantage of the FiatShamir heuristic is its noninteractive nature. This noninteractivity means the protocol can be used in scenarios where realtime interaction isn't feasible.

Efficient: The FiatShamir approach is efficient because each of the phases depend on polynomial time operations.

Applications: The noninteractive version of the protocol has been foundational for other cryptographic primitives, notably the construction of digital signatures.
Potential Limitations
 Assumptions: The security of the transformed protocol heavily relies on the hash function's properties. If the hash function is compromised, so is the protocol.
Conclusion
The FiatShamir Identification Scheme and its noninteractive transformation through the FiatShamir heuristic have been instrumental in the development of cryptographic protocols. The FiatShamir approach is a spiritual cousin with RSA and shares security characteristics in a class with the most secure cryptographic protocols similar to One Time Pads.