# What is matrix branching program?

Recently I am reading something about order-revealing encryption (by Boneh at al. in EuroCrypt 2015) and encountered "matrix branching programming". It seems like it took me forever to understand this. Anyone can help me with this problem. better have a concrete example in explanations

• It might help if you could make your question a bit more specific. Good questions here on Stack Exchange should be reasonably scoped, so that they can be answered in a few pages of text (or less). While I really don't know anything about the subject, I'd guess there's a good chance that "explain matrix branching programs to me" may be too broad a question for this site. – Ilmari Karonen Aug 25 '15 at 20:16
• I think "matrix branching program" is the specific question I ask here...anyway thanks for your comments @IlmariKaronen – cryptodog Aug 26 '15 at 17:30

In short: You're given $2k$ of invertible matrixes $A_{x,y}$ with $y\in\{0,1\}$, $x=0,1,\dots,k-1$. For an (previously fixed) input of $n$ bits $b_i$ ($i={0,1,\dots,n-1}$), ($k$ should be a multiple of $n$), you multiply them like this: $$\prod_{x=0}^{k-1} A_{x,b_{x \text{ mod }n}}$$
And if you evaluate it honestly (following this rule), you either get the identity matrix or a different, fixed matrix $B$, and this is equivalent to an output of a single bit of the function, which is realized by this matrix branching program.
A nice feature is that you can realize all programs in $NC^1$ this way in poly sized matrix branching programs. But I really suggest watching the video, even if just for the matrix branching part.