Courtesy of Encode Club Bootcamp.
Human dignity demands that personal information be hidden from the public e.g medical records, forensic data
But veils of secrecy designed to preserve privacy may also be abused to cover up lies and deceipt by institutions entrusted with data, unjustly harming citizens and eroding trust in central institutions. - Starkware
ZK gives similar vibes to Machine Learning. More and more people just mention ZK as a magic solution that fixes everything with no context of this current limitation. - 0xMisaka
Set of integers is denoted by Z. {...-4,-3,-2,-1,0,1,2,3,4..}
Set of Rational numbers denoted by Q. {..1, 3/2, 2, 22/7,...}
Set of Real Numbers denoted by R. {2, -4, 613, π, √2,..}
Field denoted by F, if they are a finite field or K for a field of real or complex numbers we also use Zp* to represent a finite field of integers mod prime p
We use finite field for cryptography because they have short exact representations and useful properties
n mod k simply means the remainder when n is divided by k
35 mod 3 = 1 15 mod 4 = 3
See modular arithmentic exercize
the remainders shoul be positive
Simply a group is a set of elements {a, b, c, ...} plus a binary operation
To be concidered a group the combination needs certain properties
- Closure
- Associativity
- Identity element
- Inverse element
Closure: For all a, b in set G, the result of operation a•b, is also in G
Associativity: for all a, b and c in set G, (a•b)•c
Identity element: there exists an element e in G such that every element a in G, the equation e•a = a•e=a holds.
Inverse element: for each a in G, there exists an element b in G, denoted a-1 (or -a if the operation is "+"), such that a•b = b•a = e, where e is the identity element
if a subset of the elements in a group also satisfies the group properties, then that is a subgroup of the original group
A finite group can be cyclic. That means it has a generator element. If you start at any point and apply a group operation with the generator as argument a certain number of times, you can go around the whole group and end in the same place.
fermat's little theorem
a-1 ≡ a p-2 (modp)
Let p = 7 and a = 2. We can compute the inverse of a as:
ap-2 = 25 = 32 ≡ 4 mod 7
Verify: 2 x 4 ≡ 1 mod 7
since
6 mod 7 = 6
13 mod 7 = 6
20 mod 7 = 6
6, 13, 20 form equivalence classes
more formally
i + kN | k EZ for some i between 0 and N - 1.
Thus if we are trying to solve the equation
x mod 7 = 6
x could be 6, 13, 20 ....
This gives us the basis for a one way function
A field is a set of say integers together with two operations called addition and multiplication.
One example of a field is the Real Numbers under addition and multiplication, another is a ser of integers mod a prime number with addition and multiplication.
The field operations are required to satisfy the following field axioms. In these axioms, a, b and c are arbitrary element s of the field F.
-
Associativity of addition and multiplication: a+(b+c) = (a+b)+c and a•(b•c)=(a•b)•c
-
Commutativity of addition and multiplication: a+b=b+a and a•b=b•a
-
Additive and multiplicative identity. Additve = 0, a + 0 = a, multiplicative = 1, a • 1 = a
-
Additive inverse: For every a in F, there exists an element in F, denoted -a, called the additive invers of a, such that a + (-a) = 0
-
Multicative inverse: For every a ≠ 0 in F, the exists an element in F, denoted by a-1, called the multiplicative inverse of a, such that a•a-1=1
-
Distributivity of multiplication over addition: a•(b+c) = (a•b)+(a•c)
-
Instance variables --> which are public
-
Witness variables ---> which are private
-
Interactive proofs --> Multiple rounds
-
Non-interactive proofs ---> no repeated communications between the prover and the verifier
-
Succint --->
-
Non Succint --->
-
Proof
-
Proof of Knowledge --->
-
Argument
- Homework 2