Zero knowledge protocols

24th February 2010

These are lecture notes from my Computer Science course, not a general reference for "Zero knowledge protocols"

Zero-knowledge protocols are ways of proving ‘I have this secret’ without giving it away. Example is the cave with a magic door to get through the passage and come out the other side, or something.

You can use this to prove you know a graph isomorphism:

1. Start with two isomorphic graphs G1 and G2 (public) where G2 was formed from function f applied to G1. f here is the secret.
2. Generate an isomorphism of G1 and send it to person X.
3. To prove you know it, be asked by person X to prove it is isomorphic to G1 or G2. In the case of G1, just provide the function you used to generate it. In the case of G2, reverse it back to G1 and then apply f.

Person X is none the wiser what function f is.

Identification

Many schemes have been proposed for identification based on the (supposed) computation intractability of various NP-complete problem types.

Perceptron Problems

(Yes, that is spelt right)

• Given a matrix of ±1s. Can you find a secret vector such that you end up with a matrix that is all positive.
• Make it harder by asking for a particular histogram.

Generating Instances

This is where it goes wrong, apparently.

• Generate random matrix.
• Generate random secret.
• If anything in the result is negative, negate the row causing problems.

Stuff about finding these problems. I actually have no idea how this relates to zero knowledge proofs. I don’t think it does…

It mentions that annealing sometimes doesn’t find a solution because it can get stuck in local optimisations or whatever.

Then talks about how search techniques have computational dynamics too (e.g. timing attacks can be applied sort of to search problems. I don’t quite know how as it didn’t make sense). Apparently the process of doing the search has more information than the final state (result) of the search; to do with where the bits get stuck.

Comments

blog comments powered by Disqus