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
For an easy to grasp explanation, you can have a look at the talk Obfuscation I at the Cryptography Bootcamp by Amit Sahai. Here's a link to youtube. In this context he also explains matrix branching programs, which are also used in the construction of indistuingishability obfuscation. He starts explaining them at the minute 40.

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.