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

  • 1
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Aug 25 '15 at 20:16
  • 1
    $\begingroup$ I think "matrix branching program" is the specific question I ask here...anyway thanks for your comments @IlmariKaronen $\endgroup$ – cryptodog Aug 26 '15 at 17:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.