Dan Boneh
Dec. 7, 2013
Abstract. In several applications of Barrington's theorem to cryptography it is more convenient to use a group of $2\times 2$ matrices instead of the symmetric group $S_5$. The final branching program is a product of $2 \times 2$ matrices rather than a product of permutations. Below we list a few example $2 \times 2$ matrices that make Barrington's theorem work as efficiently as in $S_5$. We also show how to implement an XOR gate efficiently in matrix branching programs.
1. Barrington's Theorem using $2 \times 2$ Matrices
Recall that Barrington's theorem shows how to express a depth $d$ formula as a branching programs of length at most $4^d$. The resulting branching program is a product of permutations in the symmetric group $S_5$. Barrington showed that the group $S_5$ can be replaced by any non-solvable group $G$, but the resulting branching programs may not be as short: their length is at most $B(G)^d$ where possibly $B(G)>4$. Here $B(G)$ is a constant that depends on the specific group $G$ being used. We are interested in using as the group G a group of $2 \times 2$ matrices and obtain programs of length at most $4^d$ as when using the group $S_5$.
The constant $B(G)$ is 4 whenever the group $G$ contains two (non-identity) elements $A$ and $B$ that are conjugate to each other and to their commutator. The symmetric group $S_5$ contains such a pair, but some non-solvable groups do not, for example $SL_2(\mathbb{Z})$.
We show that the group $SL_2(\mathbb{F})$ over a sufficiently large finite field $\mathbb{F}$ contains the required elements $A$ and $B$. Recall that $SL_2(\mathbb{F})$ is the group of $2 \times 2$ matrices over $\mathbb{F}$ with determinant 1. We list a few matrix pairs $(A,B)$ in $SL_2(\mathbb{F})$ that are conjugate to each other and to their commutator. This ensures that Barrington's construction using these matrices gives programs of length $4^d$, as in the group $S_5$.
Example 1: suppose the field $\mathbb{F}$ contains an element $i$ such as $i^2 = -1$ and $\text{char}(\mathbb{F})>2$. Define $$ A_0 = \left(\begin{array}{cc} -1 & 1 \\ 0 & -1 \end{array}\right) \quad\text{and}\quad B_0 = \left(\begin{array}{cc} 0 & i/2 \\ 2i & -2 \end{array}\right) $$ Their commutator is $$A_0 \cdot B_0 \cdot A_0^{-1} \cdot B_0^{-1} = \left(\begin{array}{cc} -3 & -1 \\ 4 & 1 \end{array}\right)$$ All three matrices have determinant 1 and trace $-2$ which means that their only eigenvalue is -1. Neither matrix is -I and therefore all three are conjugates, as required.
Example 2: suppose the field $\mathbb{F}$ contains a primitive cube root of unity $\mu$. Define $$ A_1 = \left(\begin{array}{cc} \mu & 0 \\ 0 & \mu^2 \end{array}\right) \quad\text{and}\quad B_1 = \left(\begin{array}{cc} -1 & -1 \\ 1 & 0 \end{array}\right) $$ Their commutator is $$ A_1 \cdot B_1 \cdot A_1^{-1} \cdot B_1^{-1} = \left(\begin{array}{cc} \mu^2 & \mu^2-1 \\ 0 & \mu \end{array}\right) $$ All three matrices have determinant 1 and trace $-1$ which means that their eigenvalues are $\mu$ and $\mu^2$. Therefore all three are conjugates.
Example 3: the pair $(A_1,B_1)$ is a special case of a more general set. Suppose the field $\mathbb{F}$ contains a pair of elements $(x,y)$ satisfying $$y^2 = x^6 + 2x^5 - x^4 -x^2 + 2x + 1$$ where $x \neq -1,0,1$. Define $$ A_2 = \left(\begin{array}{cc} x & 0 \\ 0 & 1/x \end{array}\right) \quad\text{and}\quad B_2 = \frac{1}{x^2+x} \cdot \left(\begin{array}{cc} (x^3+x^2+x+1+y)/2 & 1 \\ -x^3 & (x^3+x^2+x+1-y)/2 \end{array}\right) $$ Then again $A_2$ and $B_2$ are conjugate to each other and to their commutator and neither matrix is the identity. All sufficiently large finite fields contain a pair $(x,y)$ satisfying the requirements. The pair $(A_1,B_1)$ above is obtained by setting $(x,y) = (\mu,1)$. Note that the division by 2 in the definition of $B_2$ prevents this from generally being used in fields of characteristic 2. Nevertheless, the special case $(A_1,B_1)$ can be used in such fields.
Summary. For cryptographic applications all these examples show how to use Barrington's theorem with $2 \times 2$ matrices in different finite fields. Note that $SL_2(\mathbb{F}_2)$ and $SL_2(\mathbb{F}_3)$ cannot be used because both are solvable.
2. Computing XOR(x,y)
Suppose we wish to apply Barrington's construction to a formula containing AND, OR, NOT, and XOR gates. Naively, computing the XOR of bits x and y using Barrington requires a formula of depth 2 which translates to a product of 16 matrices. We show how to compute the XOR gates in the given formula using a product of only two matrices.
If the matrices $A$ and $B$ needed for Barrington's theorem happen to be involutions (i.e., $\ A^2 = B^2 = I$) then XOR(x,y) can be computed by the following 2-step matrix branching program: $$ (A, I)_x \ \cdot\ (A, I)_y $$ Indeed, if $x=y=0$ or $x=y=1$ then the product evaluates to the identity matrix $I$; otherwise the product evaluates to $A$ as required.
Unfortunately the groups $S_5$ and $SL_2(\mathbb{F})$ do not contain a pair of involutions $(A,B)$ that are conjugate to each other and to their commutator. However, the group $S_6$ does. For example $A = (1 2)(3 4)$ and $B = (1 4)(5 6)$ are clearly involutions and so is their commutator $A B A^{-1} B^{-1} = (2 3)(1 4)$. All three have the same cycle structure and are therefore conjugates as required.
The group $SL_2(\mathbb{F})$ does not have such elements $A$ and $B$, but the group $SL_5(\mathbb{F})$ of $5 \times 5$ matrices trivially does because the symmetric group $S_6$ has an injective 5-dimensional irreducible representation (known as the standard representation). Even better, Mark Zhandry showed that the required matrices exist in the group $SL_3(\mathbb{F})$, for example: $$ A_3 = \left(\begin{array}{ccc} -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{array}\right) \quad\text{and}\quad B_3 = \left(\begin{array}{ccc} 0 & 0 & 1 \\ 0 & -1 & 0 \\ 1 & 0 & 0 \end{array}\right) \ . $$ Both matrices are involutions and are conjugate to each other and to their commutator. Therefore, they can be used in Barrington's construction where all XORs are simply implemented as a 2-step branching program.
3. Computing arithmetic formulas using $3 \times 3$ matrices
To conclude we briefly review an old (1988) result of Ben-Or and Cleve that shows how to compute an arithmetic formula of depth $d$ using a product of at most $4^d$ matrices in $SL_3(\mathbb{F})$. Suppose we can recursively construct matrices $$ F = \left(\begin{array}{ccc} 1 & 0 & 0 \\ f & 1 & 0 \\ 0 & 0 & 1 \end{array}\right) \quad\text{and}\quad G = \left(\begin{array}{ccc} 1 & 0 & 0 \\ g & 1 & 0 \\ 0 & 0 & 1 \end{array}\right) \ $$ where $f = f(x_1,\ldots,x_n)$ and $g = g(x_1,\ldots,x_n)$ are arithmetic formulas on inputs $x_1,\ldots,x_n \in \mathbb{F}$. Ben-Or and Cleve observe that the following matrix products compute matrices for the formulas $f+g$ and $f \cdot g$: $$ \begin{align*} \left(\begin{array}{ccc} 1 & 0 & 0 \\ f+g & 1 & 0 \\ 0 & 0 & 1 \end{array}\right) = & F \cdot G \\[4mm] \left(\begin{array}{ccc} 1 & 0 & 0 \\ f \cdot g & 1 & 0 \\ 0 & 0 & 1 \end{array}\right) = & \left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ -f & 1 & 0 \end{array}\right) \cdot \left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & g & 1 \end{array}\right) \cdot \left(\begin{array}{ccc} 1 & 0 & 0 \\ f & 1 & 0 \\ 0 & 0 & 1 \end{array}\right) \cdot \left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & -g \end{array}\right) \end{align*} $$ where all four matrices needed in the formula for $f \cdot g$ are easily obtained from $F$ and $G$ by multiplying them by fixed signed permutation matrices on the left and right. For example, the fourth matrix is obtained from $G$ as: $$ \left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & -g \end{array}\right) = \left(\begin{array}{ccc} 0 & 0 & 1 \\ -1 & 0 & 0 \\ 0 & 1 & 0 \end{array}\right) \cdot G \cdot \left(\begin{array}{ccc} 0 & 0 & -1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{array}\right) $$ Since the matrix product for $f \cdot g$ uses 4 matrices, we can apply this recursively to the original depth-$d$ formula and obtain a matrix product of total length at most $4^d$ as promised. Each matrix in the product depends on a single input $x_i \in \mathbb{F}$.
Observe that taking $\mathbb{F} = \mathbb{F}_2$ gives Barrington's theorem using the group $SL_3(\mathbb{F}_2)$. We note that Cleve showed how to shrink the length of the program to $2^{d (1+\epsilon)}$ at the cost of using the group $SL_w(\mathbb{F})$ where $w$ is exponential in $1/\epsilon$.