Loading

Module 1: Identification Schemes and Zero-knowledge Protocol

Notes
Study Reminders
Support
Text Version

Identification Schemes and Zero-Knowledge Protocol - Lesson Summary

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Prime Numbers: An integer P>1 is called a Prime number if the only positive factors of P are 1 and P. A positive integer that is greater than 1 and not Prime is called its Composite number.
The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written uniquely as a Prime or as a product of two or more Primes, where the Prime factors are written in order of non-decreasing size.
The Naive Algorithm is based on the fact that if a number P is Composite, it has at least one of the divisors which is less than or equal to the square root of P.
If A and B are non-zero integers, the Greatest Common Divisor of A and B is the greatest integer which divides both A an B.
In Shamir's Secret Sharing Scheme, if a dealer wants to share a secret it does the following;

Picks a random Polynomial over the field
Sends the share Si to Party Pi
The Correctness of the Secret Sharing is trivial, which means out of the same shareholders any set of (t+1) shares suffice to unique interpolate back t-degree Polynomial F(x) using the Lagrange interpolation formula
Information-theoretically, any set of t shares reveal no information about the shared secrets

A Zero-Knowledge Proof is a kind of Interaction Protocol between two entities, a Prover and Verifier which allows the Prover to prove a statement to the Verifier without actually showing anything about the underlying witness.
Properties required for the Zero-Knowledge Proof Protocol are; 

Completeness: Honest Prover and honest Verifier 
Soundness: If Prover is corrupt and does not have a witness - Protocol V should output reject with high probability
Zero-Knowledge: If Prover is honest and Verifier is corrupted - nothing about a witness is revealed from the Protocol transcript

To Convert a Passively-Secure Protocol into a Maliciously-Secure Protocol, each Party should prove to every other Party that it is following the Protocol instructions correctly without showing its input and local randomness; Since every N-P statement can be proved in a ZK fashion thanks to the ZK Proof system for 3-Coloring Problem.