how to explain zero knowledge proof to your 7 year old cousin?

2018-03-21 08:09:21

how to explain zero knowledge proof to your 7 year old cousin?

Nathan Aw

The simplest example of zero knowledge proof I know of ia for graph isomorphism. It's somewhat less interesting following Babai's quasi polynomial result, but for educational purpose we will ignore that. The zero knowledge proof still stands. I'm not sure it is simple enough for a 7 year old but here goes:

We have two graphs where the nodes have different names, we want to prove they are essentially the same graph. Meaning there is a one to one mapping between the nodes of the graphs which preserves the edges. Or alternatively we can rename the nodes of one graph to recieve the second. We want to prove the existence of such a mapping without revealing it.

This can be done by taking ine of the graphs and renaming the nodes to random names(providing edges in random order). We send this new graph to verifier who asks to reveal a mapping between it and one of the two originals of his choice. Th

  • The simplest example of zero knowledge proof I know of ia for graph isomorphism. It's somewhat less interesting following Babai's quasi polynomial result, but for educational purpose we will ignore that. The zero knowledge proof still stands. I'm not sure it is simple enough for a 7 year old but here goes:

    We have two graphs where the nodes have different names, we want to prove they are essentially the same graph. Meaning there is a one to one mapping between the nodes of the graphs which preserves the edges. Or alternatively we can rename the nodes of one graph to recieve the second. We want to prove the existence of such a mapping without revealing it.

    This can be done by taking ine of the graphs and renaming the nodes to random names(providing edges in random order). We send this new graph to verifier who asks to reveal a mapping between it and one of the two originals of his choice. The prover provides such a mapping. Repeat until desired confidence is reached.

    It probably i

    2018-03-21 09:55:05