# Zero Knowledge Identification and One-Way Homomorphisms

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.

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