In the FeigeFiatShamir protocol the S1Sk secret credentials

In the Feige-Fiat-Shamir protocol, the S1,.....,Sk secret credentials of the authenticating user are chosen such the gcd (Si,n)= 1.i= 1..n. Explain why that is the case?

Solution

According to the New Encyclopedia Britannicca 2016 cryptography is defined as \" The practice of the enciphering and deciphering of messages in secret code in order to render them unintelligible to all but the intended receiver\".

Cryptography was focused on the transforming of private correspondence into unreadable sequences of gures to protect the content of messages transferred from one geographic location to another.

A zero-knowledge interactive proof is a protocol between two parties in which one party, called the prover, tries to prove a certain fact to the other party, called the verier. A zero-knowledge interactive proof takes usually the form of a three-way protocol:

1) Witness: The prover chooses a random number and sends to the verier a proof of knowledge of this secret number. The number denes a class of questions to which the prover is supposed being able to answer.
2) Challenge: The verier chooses randomly a question in that class and sends it to the prover.
3) Response: The prover answers the question to the verier, using his secret.

Uriel Feige, Amos Fiat and Adi Shamir introduce in their identication scheme based on a zero-knowledge protocol. This is the best-known zero knowledge proof of identity. The Feige-Fiat-Shamir identication scheme uses a public-private key pair. It has the advantage of requiring only a few modular operations; hence, it is quite fast and may be implemented on the weak microprocessors embedded in smart cards. FFS is a mere identication protocol; it may serve for login procedures. Unlike RSA, it is not possible to use it also for data encryption. However, its advantage over RSA is that it’s much computationally lighter; FFS computations involve just multiplications, while RSA uses raisings to power.

In the scheme, a trusted center publish a modulus n which is the product of two large primes of the form 4r+3. n is a Blum integer, and hence it has the property that -1 is a quadratic nonresidue (i.e X² =-1 mod n has no solution) and its Jacobi symbol is 1 mod n. The difculty of extracting square roots mod makes the private key infeasible to guess.

Once the modulus n has been published, the center can be closed as it has no further role in the protocol.

First A generates her public and private keys as follows:-

1) She chooses k random numbers S₁,....... S_k     in Z _n .      The S1 to Sk are the private keys.

2) She chooses k random values Ij as Ij=+-1/S_j² mod n. The I1 to Ik is the public key.

The Identification protocol develops itself as follows:

1) A chooses the random number R, and sends X=+- R²   mod  n to B.

2) B chooses k random booleans E1,........Ek and send it to the A.

3) A sends the Value Y=R.^E_j=1 S_j mod n to B.

4) B verifies that X=+- Y² .^E_j=I I_j mod n . if and only if this is true, the proof is accepted.

To increase the security , these steps may be repeated t times. The probability that A can fool B is then 1 in 2^kt.