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?


The "omitted part of this upside down algorithm" is like dynamic programming, since it
computes node values before getting to the point at which those values will be used.
Unlike my original thought, the recursive approach certainly can be better; the canonical
example of that would be using their scheme for PIR. $\:$ However, for the application your
previous question was about, their approach will definitely be better than recursion.

$P$ is just a party's input, so it certainly can be reused. $\:$ However, the resulting
ciphertext can't necessarily be run through the homomorphing process again, since the
group changes with each layer. $\:$ (That is mentioned in the top paragraph of page 16.)

  • $\begingroup$ Sorry, I cannot catch the point. I know that the first example seems like the up-bottom process, and the second example shows the recursion, which requires RAM to store the function caller records on stack. These examples are two different programs, using different structures. In the paper, however, it seems that $P$ of the orginial version and the encrypted version share the same structure. So would you please expand it a bit more? Thank you very much. $\endgroup$
    – phan
    Aug 24 '15 at 7:26
  • $\begingroup$ I now realize that memoization is actually independent of the point I was trying to make. $\;$ $\endgroup$
    – user991
    Aug 24 '15 at 7:56
  • $\begingroup$ Sorry, I am still confusing... The Fibonacci series can be calculated from up to bottom or from bottom to up for the commutativity and associativity, but I think the calculation graph of $P$ does not always hold these properties. So why we can obtain $P(x)$ from a path from the terminal nodes to the initial node? Should I have known some other things? Is there any reference for the non-cryptographic version of the bottom-up evaluation of BP? $\endgroup$
    – phan
    Aug 24 '15 at 8:06
  • $\begingroup$ We "can obtain $P(x)$ from a path from the terminal nodes to the initial node" because the value of every non-terminal node is defined in terms of (stuff that's independent of $P$ and) the values of nodes that are closer to being terminal. $\:$ With their approach, those values will already have been computed by the time they are to be used, rather than having to be computed on-the-fly. $\;\;\;\;$ $\endgroup$
    – user991
    Aug 24 '15 at 8:13
  • $\begingroup$ By manually writing down each step of the bottom-up process, I think I finally understand it. In my opinion, for the terminal nodes, their labels are exactly all the possible outputs. And then, for the nodes whose height $j > 0$, their labels are the filtered possible outputs by the information of inputs at height $j$. So the label of the initial node is the only one left possible output filtered by all the inputs. Am I right? $\endgroup$
    – phan
    Aug 24 '15 at 8:49

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.