Adam Marcus, Princeton University, Ramanujan colorings
An important construction for (the information theoretic version of) semantic security is a "Biregular Irreducible Function" (BRI). These can be constructed from a complete biregular graph on $2^k d \times 2^k d$ by by coloring it with $2^k$ colors in such a way that each vertex has degree $d$ in each color. Good BRI's are…