Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Feige-Fiat-Shamir Identification Scheme
2.1.
Setup
2.2.
Algorithm
2.3.
Security
3.
Frequently Asked Questions
3.1.
Briefly explain DSA.
3.2.
Mention the importance of Encryption.
3.3.
Name the two types of Cryptographic Algorithms.
3.4.
Mention the principles of Cryptography.
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Author Rupal Saluja
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

notion of cryptography

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.

notion of authentication

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 s1, s2, s3,.......,sn. After creating secret numbers, calculate vi ≡ si2 (mod n). The parties, Peggy and Vector, receive n while p and q are kept secret. The secret numbers, si, are sent to Peggy, which are utilized as login numbers for authentication. Peggy sends the number to Victor, vi, when it desires to prove itself to Victor. Sometimes, Victor cannot retrieve Peggy’s snumbers from its vi 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 = log2n times.

1. Alice chooses a random value R ∈ Zn.

2. She calculates X = ±R2 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

equation 

6. She sends the response Y to Bob.

7. Bob verifies X using the equation

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 vi numbers but is not able to decrypt Peggy’s si numbers. If Eve desires to convince Victor that it is Peggy, it will be easy for it to determine what Victor’s ai numbers will be. Then, it randomly picks an integer y to calculate the x using the following formula.

x ≡ y2v1-a1v2-a2…..vk-ak (mod n)

This x is then sent to Victor. When Victor sends ai, 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 awill be only 1 in 2k. By continuously repeating the procedure t times, the probability reduces to 1 in 2kt.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Briefly explain DSA.

The full form of DSA is Digital Signature Algorithm. DSA is one type of cryptographic algorithm used to create keys, sign data and validate signatures. It encrypts the digital signatures and hence, secure them.

Mention the importance of Encryption.

Encryption ensures the conversation’s privacy and confidentiality. We frequently use Encryption when there is a need to secure the data such as financial statements, test results, or important documents.

Name the two types of Cryptographic Algorithms.

The two types of Cryptographic Algorithms are Asymmetric Key Encryption and Symmetric Key Encryption.

Mention the principles of Cryptography.

The four principles of Cryptography include Data Confidentiality, Data Integrity, Authentication, and Non-repudiation.

Conclusion

Overall, we will learn 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.

We hope the above discussion helped you understand the concepts of the Feige-Fiat-Shamir Identification Scheme in Cryptography and can be used for reference whenever needed. To learn more about Cryptography, you can refer to blogs on Security in CryptographySigning and Encrypting in CryptographyAuthenticated Encryption in CryptographyCBC MAC in Cryptography, and Message Authentication Codes in Cryptography.

Visit our website to read more such blogs. Make sure you enroll in our courses, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help fellow ninjas grow.

Happy Coding!

Live masterclass