Branching program (BP) is a DAG-based non-uniform computational model for L/poly class. It has been widely used in formal verification, logic synthesis, and data analysis. As a special BP, a decision tree is a popular machine learning classifier for its effectiveness and simplicity. In this work, we propose a UC-secure efficient 3-party computation platform for outsourced branching program and/or decision tree evaluation. We construct a constant-round protocol and a linear-round protocol. In particular, the overall (online + offline) communication cost of our linear-round protocol is$O(d(\ell + \log m+\log n))$and its round complexity is$2d-1$, where$m$is the DAG size,$n$is the number of features,$\ell$is the feature length, and$d$is the longest path length. To enable efficient oblivious hopping among the DAG nodes, we propose a lightweight 1-out-of-$N$shared OT protocol with logarithmic communication in both online and offline phase. This partial result may be of independent interest to some other cryptographic protocols. Our benchmark shows, compared with the state-of-the-arts, the proposed constant-round protocol is up to 10X faster in the WAN setting, while the proposed linear-round protocol is up to 15X faster in the LAN setting.

Private function evaluation (PFE) is a special type of MPC protocols that, in addition to the input privacy, can preserve the function privacy. In this work, we propose a PFE scheme for RAM. In particular, we first design an efficient 4-server distributed ORAM scheme with amortized communication$O(\log n)$per access (both reading and writing). We then simulate a RISC RAM machine over the MPC platform, hiding (i) the memory access pattern, (ii) the machine state (including registers, program counter, condition flag, etc.), and (iii) the executed instructions. Our scheme can naturally support a simplified TinyRAM instruction set; if a public RAM program$P$with given inputs$x$needs to execute$z$instruction cycles, our PFE scheme is able to securely evaluate$P(x)$on private$P$and$x$within$5z+1$online rounds. We prototype and benchmark our system for set intersection, binary search, and quicksort algorithms. For instance, obliviously performing the binary search algorithm on a 210 array takes$5.81s$with function privacy.