  Secure function evaluation (SFE) is the process of computing a function (or
running an algorithm) on some data, while keeping the input, output and
intermediate results hidden from the environment in which the function is
evaluated. This can be done using fully homomorphic encryption, Yao's garbled
circuits or secure multiparty computation. Applications are manifold, most
prominently the outsourcing of computations to cloud service providers, where
data is to be manipulated and processed in full confidentiality. Today, one of
the most intensively studied solutions to SFE is fully homomorphic encryption
(FHE). Ever since the first such systems have been discovered in 2009, and
despite much progress, FHE still remains inefficient and difficult to implement
practically. Similar concerns apply to garbled circuits and (generic)
multiparty computation protocols. In this work, we introduce the concept of a
blind Turing-machine, which uses simple homomorphic encryption (an extension of
ElGamal encryption) to process ciphertexts in the way as standard
Turing-machines do, thus achieving computability of any function in total
privacy. Remarkably, this shows that fully homomorphic encryption is indeed an
overly strong primitive to do SFE, as group homomorphic encryption with
equality check is already sufficient. Moreover, the technique is easy to
implement and perhaps opens the door to efficient private computations on
nowadays computing machinery, requiring only simple changes to well-established
computer architectures.
