  We introduce a new approach to computation on encrypted data -- Encrypted
Operator Computing (EOC) -- as an alternative to Fully Homomorphic Encryption
(FHE). Given a plaintext vector $|{x}\rangle$, $x\in \{0,1\}^n$, and a function
$F(x)$ represented as an operator $\hat F$, $\hat F\;|{x}\rangle =
|{F(x)}\rangle$, the EOC scheme is based on obfuscating the conjugated operator
(circuit) $\hat{F}^E = \hat E\;\hat F\;\hat{E}^{-1}$ that implements
computation on encrypted data, $\hat E |{x}\rangle$. The construction of EOC
hinges on the existence of a two-stage NC$^1$ reversible-circuit-based IND-CCA2
cipher $\hat{E} = \hat{N} \hat{L}$, where $\hat{L}$ and $\hat{N}$ represent,
respectively, linear and non-linear NC$^1$ tree-structured circuits of 3-bit
reversible gates. We make and motivate security assumptions about such a NC$^1$
cipher. Furthermore, we establish the polynomial complexity of the obfuscated
circuit, the evaluator $O(\hat{F}^E)$, by proving that: (a) conjugation of each
gate of $F$ with $\hat{L}$ yields a polynomial number of gates; and (b) the
subsequent conjugation with $\hat{N}$ yields a polynomial number of ``chips,''
$n$-input/$n$-output reversible functions, with outputs expressed as
polynomial-sized ordered Binary Decision Diagrams (OBDDs). The security of
individual chips is connected to the notion of Best Possible Obfuscators which
relies on poly-size OBDDs and the fact that OBDDs are normal forms that expose
the functionality but hide the gate implementation of the chip. We conjecture
that the addition of random pairs of NOTs between layers of $\hat{N}$ during
the construction of $F^E$, a device analogous to the AddRoundKey rounds of AES,
ensures the security of the the evaluator. We also present a generalization to
asymmetric encryption.
