/lesson/

It is illuminati thread where OP is broadcasting knowledge we otherwise have to pay for

God speed OP you are fighting the good fight

Forgot to mention. You the verifier don't have enough computational power to check whether the graphs are isomorphic or not (remember I said it's a hard problem?).

But the prover has unlimited computational power, she can solve anything she wants instantly.

Two of the problems are easy to fix.

>Or I could've said [E, B] instead of [B, E]
We can just agree that we'll always put the smaller letter first when we're talking about graphs.
>or rearrange the order of the edges.
We can consider each edge as a two-letter word and order them like the dictionary.

Both of these, it's very easy to do yourself and check that a given graph is the same as after applying these transformations.

>I could have called A C and C A.
But this is a hard one. In general, there are n! permutations of n nodes (reply if you don't understand what this means).

So maybe one graph has nodes 1, 2, 3, 4, 5, but the other one's, respectively, a re 4, 5, 3, 1, 2. If you wanted to check for equality you kind of have to check all n! permutations (technically this is not true due to a recent result of Laszlo Babai in 2015 - but just believe me that this still isn't easy to do).

We've isolated the problem to be, given two list of nodes, does there exist some permutation of the first list such that if you relabeled the edges and ordered it like I mentioned above, the edges match up?

Back to the interactive protocol. The idea is, you want to give one of the graphs at random to the prover, and the prover tries to tell you which one you gave (using their infinite power).

As I mentioned, the prover can just see which one you gave her by comparing the representations. So what you do is you randomly pick a permutation, maybe by flipping coins. This is easy since you only have to come up with one permutation, not all n!. Then you apply this permutation to one of the graphs, also picked at random, and send this graph to the prover.

If the two graphs weren't isomorphic, then the graph you send is only isomorphic to one of the original graphs, because all you did was rearrange the nodes, you didn't actually change the structure of the graph.

Anyone want to explain why the prover fails in the case that the two graphs were isomorphic?

Would that be comparing the relations between each individual node and then using their miss-matched-ness as proof that they're non-isomorphic? Using smaller quanta for the smaller computer and then sumarizing the set of info?

I don't know what I'm doing, i graduated highschool and then worked at a supermarket for two years

I'm not entirely sure what you mean. To formalize what "hard" and "easy" mean it would take forever. But what I mean is the verifier's computer just isn't strong enough to check whether the graphs are isomorphic or not.

Here are two graphs I just made in Python. Both vertices list are 1 through 100, both have 50 edges.

Graph 1
E = [[61, 64], [95, 22], [50, 29], [14, 32], [28, 56], [41, 77], [41, 42], [80, 82], [26, 4], [57, 99], [12, 17], [87, 69], [93, 13], [20, 4], [76, 14], [4, 94], [53, 98], [77, 74], [71, 28], [9, 90], [58, 60], [49, 59], [24, 54], [19, 12], [44, 34], [2, 32], [1, 54], [77, 12], [37, 37], [17, 86], [16, 92], [65, 52], [40, 30], [37, 71], [51, 43], [14, 9], [13, 67], [59, 31], [14, 75], [33, 83], [16, 77], [3, 33], [94, 72], [70, 22], [96, 87], [86, 78], [46, 36], [53, 33], [98, 4], [71, 22]]

Graph 2
E = [[40, 25], [80, 38], [30, 69], [93, 59], [1, 50], [90, 85], [14, 20], [68, 27], [7, 55], [61, 74], [37, 80], [33, 64], [86, 49], [83, 32], [37, 13], [4, 75], [87, 72], [4, 24], [50, 42], [46, 92], [50, 80], [67, 20], [20, 63], [63, 71], [10, 87], [44, 71], [30, 89], [29, 73], [82, 47], [88, 5], [53, 6], [82, 56], [51, 51], [54, 32], [53, 67], [69, 75], [33, 8], [55, 100], [53, 16], [53, 19], [89, 43], [4, 96], [9, 58], [21, 2], [66, 19], [51, 65], [80, 87], [46, 17], [24, 58], [69, 1]]

It's not really that easy to check if there's some way to relabel the vertices that would make all these edges to match up.k

What I mean to say is, if the prover tried to prove for each permutation why it doesn't work, the verifier just doesn't have enough power to even verify the prover's results, since there would be so much data sent (on the order of n!, which is really really large - for 100 nodes, there are 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 permutations).

>Anyone want to explain why the prover fails in the case that the two graphs were isomorphic?

Basically, the distribution of permutations is identical for both graphs if they're isomorphic. Say the first graph is G, the second is H, the one you sent is K.

It's equally likely to generate a permutation phi such that phi(G) = K than some other permutation psi such that psi(H) = K if they're isomorphic.

You're always just shuffling between a few of the n! permutations. If you know group theory this should be clear since permutations form a group. Otherwise, hopefully it's clear as well, but let me know if it isn't.

Also note that this protocol too is information theoretically zero-knowledge.

Next I'll just be briefly reviewing some advanced topics. Reply if you have any questions about anything!

>she
god damn you...

hey hey hold on
if the socks are different she can trick you into believing they're the same by saying the wrong thing a couple of times even though she knows it better.
Your procedure has two outcomes: she is always right or 50% of the time wrong.
but the second option has two explanations: the socks are different but she doesnt want to show you or the sockd are the same.

Bretty gud pleb filter