We present a novel approach for secure evaluation of encrypted Boolean functions on encrypted bits. Building upon
Barrington’s work to transform circuits to group programs and the Feige-Kilian-Naor cryptographic protocol, our novel
Fixed Structure Group Program construction for secure evaluation eliminates the need for an expensive Universal Circuit
to hide the function. Elements on the Black side weave together and multiply two coordinated streams of random
sequences of elements from an unsolvable group; the Boolean decision is recovered while preserving the confidentiality
of the decision function and the input bits. The operation is fast and can be further sped up using parallel computation.
Our approach can handle expressions with NC1 complexity, which is the class of Acyclic Boolean Circuits with
polynomial width and logarithmic depth in the size of the input. This efficiently parallelizable class includes nonmonotone
Boolean expressions of equality, inequality/range, Hamming distance, Boolean matrix multiplication, and kof-
m threshold matching operations. The combined benefits of scaling and expressivity of our approach enables secure
decision-making on the Black side. Envisioned applications include confidential publish/subscribe systems (with
empirically validated performance), secure content-oriented internetworks, confidential forwarding and firewalling rules,
and cross-domain guards.