Zero Knowledge Identification and One-Way Homomorphisms

Imagine logging into a secure web server which, instead of asking you to type in your password, merely asks you questions about your password until it’s convinced that you really do know it and therefore are who you say you are. Moreover, imagine that your answers to the server’s questions provide no information whatsoever which could be used by a malicious hacker, even if all communications between you and the server are being intercepted. Finally, imagine that the server in question not only does not store any information about your password, it has never at any point asked you for information about your password.

Sounds too good to be true, right?

In fact, such password schemes do exist, and they’re quite easy to implement. They are known as zero knowledge authentication systems. In this post, I’ll explain the main idea behind such protocols using the notion of a “one-way homomorphism”. Before diving into the technicalities, though, here’s a useful thought experiment which conveys the main idea.

Continue reading

The Mathematics of Marriage

linking-wedding-ringsIt’s been a while since my last blog post — one reason being that I recently got married.  In honor of that occasion, and my return to math blogging, here is a post on Hall’s Marriage Theorem.

Consider the following game of solitaire: you deal a deck of cards into 13 piles of 4 cards each, and your goal is to select one card from each pile so that no value (Ace through King) is repeated.  It is a beautiful mathematical fact that this can always been done, no matter how the cards were originally dealt!

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets A_1, A_2,\ldots, A_n and you wish to find distinct elements x_1 \in A_1,\ldots, x_n \in A_n.  (In our solitaire example, take A_j to be the values of the cards in the j^{\rm th} pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset J \subset \{ 1,\ldots, n \}, the set A_J:= \bigcup_{j \in J} A_j contains at least \#J elements.  Hall’s theorem asserts that these conditions are also sufficient. Continue reading