- Tomas Sander, Adam Young, Moti Yung, "Non-Interactive CryptoComputing for NC
^{1}," 40th Annual Symposium on Foundations of Computer Science---FOCS '99, IEEE, pages 554-567, 1999.Abstract. The area of "computing with encrypted data" has been studied by numerous authors in the past twenty years since it is fundamental to understanding properties of encryption and it has many practical applications. The related fundamental area of "secure function evaluation" has been studied since the mid 80s. In its basic two-party case, two parties (Alice and Bob) evaluate a known circuit over private inputs (or a private input and a private circuit). Much attention has been paid to the important issue of minimizing rounds of computation in this model. Namely, the number of communication rounds in which Alice and Bob need to engage in to evaluate a circuit on encrypted data securely. Advancements in these areas have been recognized as open problems and have remained open for a number of years. In this paper we give a one round, and thus round optimal, protocol for secure evaluation of circuits which is in polynomial-time for NC

^{1}circuits. The protocol involves an input party sending encrypted input to a second party, a cryptocomputer, which evaluates the circuit (or a known circuit over its additional private input) non-interactively, securely and obliviously, and provides the output to the input party without learning it.This improves on previous (general) results that are specialized to the case of NC^{1}circuits and require a constant number of communication rounds. We further suggest applications to network and mobile computing. The scenario also coincides with computing with encrypted data when the input is transformed into an output while remaining encrypted throughout the computation. New techniques are required for our highly constrained non-interactive setting. Naturally, some of these techniques are related to special properties of encryption schemes (we in fact, need probabilistic encryption schemes which are random self-reducible). Homomorphic encryption schemes are closely related to and useful in secure circuit evaluation. They have been associated with computations with encrypted data (as well as with many other cryptographic applications). Surprisingly, the known homomorphic schemes have been limited to a small number of algebraic structures, e.g. all the schemes we are aware of are homomorphic over groups. We also give a new provably secure public key scheme that allows the computation of the logical AND operation using encrypted data. This scheme is homomorphic over a semigroup (instead of a group) and thus also expands the range of algebraic structures which can be encrypted "homomorphically."