Suggested by Ricky Demer in this post, I am reading the paper "Evaluating Branching Programs on Encrypted Data"(TCC 2007), which uses one-round strong OT protocol to implement homomorphic evaluation of branching program (BP) on encrypted data with succinct ciphertext.
As it says on page 6, the natural way to evaluate a BP is
The output $P(x)$ of a branching program on an input assignment $x$ ... defined by following the path induced by $x$ from [the initial node] $v_0$ to a terminal node $v_l$ ... The output is the value $\psi_V(v_l)$ labeling the terminal node reached by the path.
Apparently, this is a up-to-bottom process, from the initial node to one of the terminal nodes.
However, the encrypted version of BP evaluation on ciphertext $c$ (corresponding to the cleartext $x$) seems to use a totally different (and which is strange to me) method (on page 11):
To evaluate $P$ on $c$, the server makes a bottom-up" pass on $P$, starting with the terminal nodes $T$ and ending with the initial node $v_0$ ... at the end of iteration $l$, the initial node $v_0$ is labeled by an OT answer which can be viewed as an (iterated) encryption of the output value $P(x)$ ...
So what's the omitted part of this upside down algorithm (that I should have known), and why?
PS: Another (maybe small) question, am I right to say $P$ of this scheme can be reused, on the contrary to Yao's one-time Garbled Circuit setting?