logbook

6.857 Computer and Systems Security

Diffie Hellman Key Exchange

Let g be a generator. (a, b)’s are secret, (g^a, g^b) are exchanged, and g^ab is the key.

Discrete Log Assumption

Given g and g^x, it is computationally hard to find x.

CDH - Computational Diffie Hellman Assumption

Given g^a and g^b, compute g^ab.

DDH - Decisional Diffie Hellman Assumption Assumption

Given g^a, g^b, and g^c, decide whether g^ab = g^c.

Pedersen Commitment

Alice gives (g, h=g^a) to Bob. Bob commits to c = g^xh^r where x is his secret and r is random. Alice can’t figure out what x is and Bob can’t change his secret.

Zero Knowledge Proof Example

Knowing a 3-coloring of a graph, Alice commits to a coloring of random three colors. When asked two adjacent nodes Alice reveals the colors, showing Bob that they are distinctly colored. Then Alice recommits to another randomized coloring and repeats the process until Bob is convinced. This way Alice does not reveal any information about her coloring.

* Every NP statement has zero knowledge proof.

El-Gamal Encryption

Let (SK, PK) = (x, g^x) be private/public key pair. Pick random k and send (a, b) = (g^k, m*PK^k) as encrypted message. To decrypt, compute b/a^x = m.

Digital Signature Scheme from Encyption Scheme

• Sign(SK, m) = Dec(SK, m)
• Verify(PK, m, sign) = (Enc(PK, m) == sign)

Abel-Ruffini Theorem

Abstract Algebra Preliminary

• Group: A set (G) and a binary operator (+). Has four properties: clousure (a+b is in G), associativity ((a+b)+c = a+(b+c)), identity element, inverse element.
• Cyclic Group: There’s a g in G such that g^n generates all the elements.
• Normal Subgroup: N such that for all n in N and for all g in G g+n+g-1 is in N.
• Coset: Na = {n+a for n in N} where N is a subgroup and a is an element of G.
• Quotient Group: G/N = {Ng for g in G}. This is also a group since (Na)(Nb) = N(a+b).
• Solvable Group: G is solvable if there exists a chain: {0}=G₀<=…<=G_k=G where G_i-1 is normal in G_i and G_i/G_i-1 is cyclic.
• Field: to be continued..