On the Security of a Universal Cryptocomputer: the Chosen Instruction Attack

The ultimate goal of private function evaluation is the complete outsourcing of processing tasks to distrusted platforms (such as clouds), so that arbitrary functions can be evaluated without any leakage of secret information. Several successful concepts have been proposed in the past, the most striking one having been fully homomorphic encryption besides the well-known garbled circuits and multiparty computation. In this paper, we look at an idealized model of outsourced computation, which we call a cryptocomputer. This is a (theoretical) machine that works exactly like a real-life computer in the sense of understanding a standard assembly language, but retaining all its internal signals, registers, and memory encrypted at all times. The encryption is assumed under a key that is unknown to the attacker, and taken as secure (in any cryptographically meaningful way), so that no leakage of information from any ciphertext can be expected from programs with reasonable (polynomial) time complexity. Unfortunately, such a cryptocomputer is necessarily insecure, irrespectively of how the encryption looks like. In particular, we explicitly do not assume any specific form of security (chosen-ciphertext or other) or (a)symmetry of encryption; our attack works only on ciphertexts and makes no assumptions whatsoever on the encryption. We prove insecurity of the cryptocomputer by taking the encryption as a black box, and show how to decipher every signal in the computer by pure virtue of submitting proper instructions for execution. Our attack falls into the general category of side-channel attacks, however unlike other related attacks, does neither exploit physical nor any logical characteristics of the underlying platform (besides the execution flow being observable). Somewhat surprisingly, it turns out that although the problem that we consider is cryptographic, it seemingly has no cryptographic solution and apparently calls for an interdisciplinary approach from new directions.