Fiat-Shamir Identification - Non-Interactive Zero-Knowledge Proofs - Full Implementation

Posted on Fri 25 August 2023 in tech

Fiat-Shamir Identification: Non-Interactive Zero-Knowledge Proofs

See full implementation code on GitHub

The ability to prove knowledge of some secret information without revealing the secret itself is crucial. Fiat-Shamir 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 Zero-Knowledge Proofs?

Zero-Knowledge 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 Fiat-Shamir Scheme

The Fiat-Shamir 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 Fiat-Shamir heuristic transformed this interactive system into a non-interactive one, making it more suitable for many cryptographic applications like digital signatures.

How Does It Work?

The Fiat-Shamir Identification, as with other ZK proofs of knowledge, can be understood in three phases:

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

  2. 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.

  3. 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 Fiat-Shamir heuristic makes the process non-interactive. 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 non-interactive, as the prover can generate the commitment, compute the challenge, and then produce the response, all at once.

Advantages and Implications

  • Non-Interactivity: The most prominent advantage of the Fiat-Shamir heuristic is its non-interactive nature. This non-interactivity means the protocol can be used in scenarios where real-time interaction isn't feasible.

  • Efficient: The Fiat-Shamir approach is efficient because each of the phases depend on polynomial time operations.

  • Applications: The non-interactive 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 Fiat-Shamir Identification Scheme and its non-interactive transformation through the Fiat-Shamir heuristic have been instrumental in the development of cryptographic protocols. The Fiat-Shamir 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.