## Fiat-Shamir heuristic Protocol

## Background

### Introduction

A cryptographic protocol is a distributed algorithm describing with precision the interactions between two or more entities while achieving certain security objectives. These objectives often revolve around ensuring the confidentiality, completeness and soundness of the information or data exchanged

Authentication schemes come in two primary forms: interactive and noninteractive. Interactive schemes involve direct communication between parties for verification, while noninteractive schemes, authenticate information without requiring real-time interaction.

An interactive proof scheme involves a protocol where a prover convinces a verifier of a statement's truth.
<div style ="text-align: center; padding-bottom: 10px; margin-top: -10px">Figure 1: Interactive proof schemes (Momin, 2023)</div>

In a non-interactive proof scheme a prover aims to convince a verifier of a statement's validity without revealing any additional information beyond the statement's truth
<div style ="text-align: center; padding-bottom: 10px; margin-top: -10px">Figure 2: Non-interactive proof schemes (Momin, K. 2023)</div>

Zero-knowledge proof schemes, are an intriguing subset of non-interactive cryptographic protocols, they offer a unique approach to authentication. In these schemes the goal is for the prover to convince a verifier of a statement's validity without revealing any additional information beyond the statement's truth. This interaction ensures the verifier's confidence while preserving the privacy of the prover's underlying knowledge.

Despite this lack of interaction, the verifier can still validate the prover's claim with a high degree of certainty, zero-knowledge proofs a powerful tool for secure authentication in distributed systems.
A unique feature of a noninteractive Σ-proof is its ability for any entity to act as the verifier. This means that multiple entities can independently verify the proof, similar to how anyone interested in its validity can verify a digital signature.

### Fiat-Shamir Protocol
The Fiat–Shamir heuristic simplifies Σ-protocols into noninteractive forms, enabling practical zero-knowledge identification.

- In the Fiat-Shamir protocol, a trusted third party chooses two large prime
numbers `p` and `q` to calculate the value of `n = p × q`.
- The value of `n` is disclosed to the public while the values of `p` and `q` are kept secret. Alice the prover, selects a secret number `s` between 1 and n-1 i.e., `(1 ≤ s <n)`. She calculates `v = s mod n`. She keeps `s` as her private key and registers `v` as her public key with the third party.
- Verification of Alice's statement by Bob can be done in four steps shown below:
1. Alice, the prover, chooses a random number `r` between 0 and n-1 i.e., `(1 ≤ r <n)`. She then calculates the value of `x = r² mod n`; `x` is called as witness.
2. Alice sends `x` to Bob as the witness.
3. Bob the verifier, sends a challenge `c` to Alice, `c` is either 0 or 1.
4. Alice calculates the response <code>rs^c</code>, where `r` is a random number selected by Alice in the first step. `s` is her private key and `c` is the challenge(0 or 1).
5. Alice sends the response to Bob to show that she knows value of her privatekey, s. She claims to be Alice.
6. Bob calculates <code>xv^c</code>. If these two values are equal then Alice either knows the value of s (she is honest) or she has calculated the value of`y` in some other way (dishonest) because we can easily prove that y² is the same as xvc in the modulo n arithmetic as given below:
<code><div style ="text-align: center">y² = (rs)^c = r²s²^c = r²(s²)^c = xv^c</div></code>

<div style ="text-align: center; padding-bottom: 10px; margin-top: -10px">Overview of the Fiat-Shamir Protocol</div>

### Fiat-Shamir Protocol Suitability in Various Protocols
Fiat Shamir maintains its integrity and reliability when applied within a [Random Oracle model](https://en.wikipedia.org/wiki/Random_oracle#:~:text=In%20cryptography%2C%20a%20random%20oracle,time%20that%20query%20is%20submitted.) and together with Zero-Knowledge proofs for certain suitable definitions.However, its effectiveness diminishes significantly when used with any instantiation. It sometimes require a cryptographic hash function. For certain protocols such as Lyubashevsky, Schnorr, Chaum-Pedersen simple FS hash functions can be enough. But for many classic protocols such as GMR85, Blum86 and GMW86 cryptographic FS hash functions are important.

## Implementation
### [Fiat-Shamir Protocol CLI](https://github.com/Tomi-3-0/Fiat-shamir-Protocol-CLI.git)

This CLI tool implements the Fiat-Shamir protocol, a non-interactive proof of knowledge scheme. It allows users to generate and verify proofs for a given message.

Github link: https://github.com/Tomi-3-0/Fiat-shamir-Protocol-CLI.git

### References
1. Schoenmakers, B. (2024, February 2). Lecture Notes Cryptographic Protocols. https://www.win.tue.nl/~berry/CryptographicProtocols/LectureNotes.pdf.
2. U. Feige, A. Fiat, and A. Shamir. Zero-knowledge proofs of identity. Journal of Cryptology, 1(2):77–94, 1988.
3. Maurya, Amit & Choudhary, Murari & P, Ajeyaraj & Singh, Sanjay. (2012). Modeling and Verification of Fiat-Shamir Zero Knowledge Authentication Protocol. 10.1007/978-3-642-27308-7_6.
4. Forouzan, B.A.: Cryptography & Network Security. First edn. McGraw-Hill Press,
United Kingdom (2008)
5. Momin, K. (2023, April 4). A Non-Mathematical introduction to zero knowledge proof. Medium. Retrieved March 27, 2024, from https://kayprasla.medium.com/a-non-mathematical-introduction-to-zero-knowledge-proof-c1a4a269e308

6. Wikipedia contributors. (2024, February 29). Random oracle. Wikipedia. https://en.wikipedia.org/wiki/Random_oracle

---
© 2024 Omoniyi Caleb <[e-mail]>