A Note on Barrington's Theorem

Authors: D. Boneh

In several applications of Barrington's theorem to cryptography it is more convenient to use a group of 2x2 matrices instead of the symmetric group S5. The final branching program is a product of 2x2 matrices rather than a product of permutations. In this short note we list a few example 2x2 matrices that make Barrington's theorem work as efficiently as in S5. We also show how to implement an XOR gate efficiently in matrix branching programs.

web note

Full paper: html