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:
- Start with two isomorphic graphs G1 and G2 (public) where G2 was formed from function
fapplied to G1.
fhere is the secret.
- Generate an isomorphism of G1 and send it to person X.
- 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
Person X is none the wiser what function
Many schemes have been proposed for identification based on the (supposed) computation intractability of various NP-complete problem types.
(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.
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.