The Feige-Fiat-Shamir Identification Scheme - it’s crowded here

Introduction

Cryptography is a technique to transform plain text to cipher text and vice versa. We use a key for the conversion, which can be used for encoding and decoding. Plain Text is a piece of writing that can be understood and read by any human. However, Cipher Text is an encrypted piece of text that can only be read by humans but cannot be understood.

This blog will use several aspects of one of the most important Identification Schemes: The Feige-Fiat-Shamir Identification Scheme. This includes its explanation, its algorithm, and an example.

Feige-Fiat-Shamir Identification Scheme

The Feige-Fiat-Shamir Identification Scheme suggests using zero-knowledge interactive proofs to authenticate entities. Its tricks and concepts are used to generate highly encrypted digital signatures. It permits one party, Peggy, to prove to another party, Victor, that it has secret information. This proof must be done without letting Victor know its secret information. The only difference is that the Feige-Fiat-Shamir Identification Scheme uses parallel verification and modular arithmetic processes that restrict the number of communications between both parties.

There are numerous variants of the Feige-Fiat-Shamir Identification Scheme. The two most prominent variants are used more frequently. One way is to classify the input based on the number of secrets. It is the most basic, and each prover knows only one secret. The second way is to differentiate the input based on identify-based and public key-based. In both ways, a trusted center made public n= p∙q such that p and q are secret primes. These secret primes are known only to the trusted center.

Setup

Start with choosing two large prime integers p and q and calculate their product n = pq. Then, create secret numbers s₁, s₂, s₃,.......,s_n. After creating secret numbers, calculate vi ≡ s_i² (mod n). The parties, Peggy and Vector, receive n while p and q are kept secret. The secret numbers, s_i, are sent to Peggy, which are utilized as login numbers for authentication. Peggy sends the number to Victor, v_i, when it desires to prove itself to Victor. Sometimes, Victor cannot retrieve Peggy’s s_i numbers from its v_i numbers. This is because of the difficulty in calculating a modular square root when the modulus’ factorization is not known.

Algorithm

The algorithm for the feige-fiat-shamir identification scheme is very easy. We will use an example of Bob-Alice to understand the algorithm better. Repeat the following four steps t = log₂n times.

1. Alice chooses a random value R ∈ Z_n.

2. She calculates X = ±R² mod n with the randomly chosen sign.

3. Then, she sends the commitment X to Bob.

4. Bob sends a random boolean vector E = (E1, . . . , Ek ) ∈ {0, 1}^k to Alice.

5. Alice calculates Y using the equation

6. She sends the response Y to Bob.

7. Bob verifies X using the equation

8. If so, then Bob “accepts”; otherwise, Bob “rejects.” 

Security

In the complete procedure, Peggy does not lend any important information to Victor. It hardly proves anything to Victor what and how many secret numbers it has. This must be done without letting Victor know what those numbers are. Anyone trying to decrypt the communication between Victor and Peggy would learn only this same information. The eavesdropper will not be able to learn anything important about Peggy’s secret numbers.

Suppose Eve has decrypted Victor’s v_i numbers but is not able to decrypt Peggy’s s_i numbers. If Eve desires to convince Victor that it is Peggy, it will be easy for it to determine what Victor’s a_i numbers will be. Then, it randomly picks an integer y to calculate the x using the following formula.

x ≡ y²v₁^-a1v₂^-a2…..v_k^-ak (mod n)

This x is then sent to Victor. When Victor sends a_i, Eve gives it the value of y. Victor becomes satisfied and decides that Eve has the secret numbers.

However, the probability of Eve making a correct guess of Victor’s a_i will be only 1 in 2^k. By continuously repeating the procedure t times, the probability reduces to 1 in 2^kt.