Fiat-Shamir Zero Knowledge Proof

Bhaskar S

01/01/2023

Introduction

There is a lot of buzz and interest in the area of Zero Knowledge Proofs.

But, what really is a Zero Knowledge Proof ???

To answer that, let us ask a question - Has anyone ever played the board game I Spy ???

The game has a board with a deck of cards - one draws a card with a picture on it and the goal is to locate that same picture on the board within a set time of one minute. To prevent revealing the exact location of the matching picture on the board, one could cover the board with a paper that has a hole big enough to reveal the matching picture and prove to an opponent.

This is essense is an example of a Zero Knowledge Proof.

Formally, Zero Knowledge Proof is an identification scheme, where a prover demonstrates to a verifier about some piece of information they posses (such as a password) without revealing any further details about that information to the verifier.

In the year 1988, Amos Fiat and Adi Shamir had published a paper that laid the ground work for Zero Knowledge Proofs.

The World of Passwords

In the world we live today, we identify (prove who we are) using a user-id and a password (knowledge). This is in fact an example of Proof of Knowledge.

Let us consider an example to explain this concept further.

Bob operates and runs a popular online store, called bobs-store.com, and Alice is one of his loyal customers. Anytime Alice wants to purchase from bobs-store.com, she needs to first login and prove her identity using her online credentials (user-id and password).

The following is high-level flow of the password based Proof of Knowledge:

Alice signs-up for a bobs-store.com account by entering a user-id and a password. This is the registration process
Alice's password is hashed and stored in Bob's infrastructure, to be used in future for verification purposes
When Alice wants to make a purchase from bobs-store.com, she will login to the online store by providing the user-id and the password she used during registration
The verification system on Bob's infrastructure will take Alice's password, hash it and compare it with the hashed password stored in Bob's infrastructure. If they match, Alice is considered verified and let in

One of the challenges with this password based approach is that information about the password has leaked into the verifiers system albeit hashed.

If for some unknown reason Bob's infrastructure is compromised by Eve, she will have access to the sensitive data (albeit hashed). Eve can then try to crack Alice's password by brute-force techniques.

Now, for the question - Is there a better approach to the Proof of Knowledge scheme ???

This is where the idea of Zero Knowledge Proofs come into play.

Fiat-Shamir Interactive Algorithm

The following is high-level flow of the interactive Zero Knowledge Proof scheme proposed by Fiat and Shamir:

Alice and Bob agree on a prime number $p$ and pick a random generator $G \in \mathbb{F}_p$
Alice has a secret number $s$ associated with her identity and can prove to Bob about her identity
Alice computes $x = G^s \: (mod \: p)$ and sends $x$ to Bob. This is the registration process
When Alice wants to transact with bobs-store.com, she will pick a random number $t \in \mathbb{F}_p$, compute $y = G^t \: (mod \: p)$, and sends $y$ to Bob
Bob's verifier system will pick a random number $c \in \mathbb{F}_p$ and send $c$ as a challenge to Alice
Alice now computes $z = t - c.s\: (mod \: p)$ and sends $z$ to Bob
Bob's verifier system can now compute $G^z.x^c = G^{t - c.s}.(G^s)^c = G^t = y$
Bob's verifier system can now prove the identity of Alice if Bob's computed $y$ matches the $y$ that Alice sent earlier

So, the question - Why is this a better approach ???

The answer lies in the fact - Given $x$ there is no easy way to find $s$. This is related to the Discrete Logarithm Problem from Modular Arithmetic.

Proof-of-Concept (Python)

The following is a simple Python code do demonstrate the Fiat-Shamir Interactive Zero Knowledge Proof scheme:

main.py

#
# @Author: Bhaskar S
# @Blog:   https://www.polarsparc.com
# @Date:   01 Jan 2023
#

import hashlib
import random


def main():
    random.seed(101)

    # Alice and Bob agree on p and G
    p = 701
    G = random.randint(1, p)

    # Alice hashes her password and computes her secret number s
    password = 'S3cr3t!'.encode('utf-8')
    digest = hashlib.md5(password).hexdigest()
    s = int(digest, 16) % p

    # Alice computes x and sends to Bob
    x = pow(G, s, p)

    print(f'Alice -> Bob: x = {x}')

    # Alice chooses a random t, computes y, and sends to Bob
    t = random.randint(1, p)
    y = pow(G, t, p)

    print(f'Alice -> Bob: y = {y}')

    # Bob chooses a random c and sends to Alice
    c = random.randint(1, p)

    print(f'Bob -> Alice: c = {c}')

    # Alice computes z and sends to Bob
    z = (t - c * s)

    print(f'Alice -> Bob: z = {z}')

    # Bob computes y using c, x, and z
    if z < 0:
        # Find the Multiplicative Inverse 
        tm = pow(G, -z, p)
        m = pow(tm, -1, p)
    else:
        m = pow(G, z, p)
    n = pow(x, c, p)
    bob_y = (m * n) % p

    print(f"Bob's computed y = {bob_y}")

    if y == bob_y:
        print('Success: Alice verified !!!')
    else:
        print('Failure: Alice imposter !!!')


if __name__ == '__main__':
    main()

Executing the above Python program produce the following output:

Output

Alice -> Bob: x = 376
Alice -> Bob: y = 167
Bob -> Alice: c = 553
Alice -> Bob: z = -354826
Bob's computed y = 167
Success: Alice verified !!!

References

Fiat-Shamir Heuristic