Homomorphic encryption is a form of encryption which allows computation to be carried out on the encrypted data without the need for decryption. The success of quantum approaches to related tasks in a delegated computation setting has raised the question of whether quantum mechanics may be used to achieve information theoretically secure fully homomorphic encryption. Here we show, via an information localisation argument, that deterministic fully homomorphic encryption necessarily incurs exponential overhead if perfect security is required. The insight that information must be represented and manipulated in accordance with physical laws has led to the blossoming field of quantum information science. The applications of this approach to information processing are diverse, and it has led to discoveries ranging from new algorithms [1, 2] and communications protocols [3, 4] which exploit quantum states for increased efficiency to techniques for enhancing the precision of metrology [5] . Historically, cryptography was one of the first fields for which quantum information processing was shown to offer an advantage over classical processing, when in 1984 Bennett and Brassard introduced a quantum protocol for information theoretically secure key distribution [6] . While for many quantum cryptography has remained synonymous with quantum key distribution, the field has grown substantially, with quantum protocols being discovered which enhance the security with which many cryptographic tasks can be accomplished, including digital signatures [7] , anonymous communication [8] , private database queries [9] , and random number generation [10] . The importance of information theoretically secure cryptography is highlighted by the fact that quantum algorithms offer new attacks against cryptosystems which rely on assumptions of computational intractability for their security [11] [12] [13] . Unfortunately, not all cryptographic tasks that we may wish to accomplish admit an information theoretically secure quantum protocol, and indeed a number of no-go theorems have been discovered which show that quantum mechanics alone is insufficient to accomplish certain tasks, such as bit commitment [14] and oblivious transfer [15] , with perfect security. One of the most celebrated results in classical cryptography in recent years has been the discovery of computationally secure protocols for fully homomorphic computation [16] [17] [18] [19] . A homomorphic encryption scheme is one which allows data to be encrypted in such a way that certain operations can be performed on the data without decryption. This allows a user to provide encrypted data to a remote server for processing without having to reveal the plaintext. A number of examples of such homomorphic encryption schemes have been known for many years [20] , but it was the ground-breaking work of Gentry [16] which for the first time demonstrated a fully homomorphic encryption scheme, one which allowed for arbitrary computations to be performed on the encrypted data, rather than being restricted to some class of non-universal operations. The ability to perform universal computation on encrypted data has greatly increased the utility of homomorphic encryption, and as a result it has become one of the most active areas of modern cryptography. One draw back of known fully homomorphic schemes is that they derive their security from computational assumptions. The existence of perfectly secure quantum protocols for blind computation [21] [22] [23] [24] , and recent experimental demonstrations thereof [25, 26] , highlight the possibilities opened by quantum cryptographic techniques in this area. As cryptographic tasks, blind computation and homomorphic encryption are similar in many ways. Both tasks envision a two party scenario, where the first party, Alice, wishes the second party, Bob, to carry out a computation for her, without revealing the input of her computation. In blind computation, however, Alice specifies not only the input data but also the computation to be performed, and the task is to utilise Bob's resources to perform this computation without revealing either the input or the program. As a result, the current protocols for accomplishing this task are interactive, requiring multiple rounds of communication between Alice and Bob, a significant difference from the setting of homomorphic encryption. The idea of quantum homomorphic encryption appears in [27] , which shows that a perfect, universal, quantum homomorphic scheme cannot be constructed using one-time pads and which presents an interactive protocol for achieving similar functionality. Other cryptographic schemes have been proposed that achieve some of the functionality of homomorphic encryption using quantum data [28, 29] . However, these rely on assisted computation, and so require multiple rounds of interaction between Alice and Bob, thus amounting to interactive protocols rather than simply encryption schemes. A quantum homomorphic encryption scheme does exist for a restricted model of quantum computation known as boson scattering, which offers limited information theoretic security [30] . The existence of such schemes raises the question as to whether quantum techniques can be exploited to construct an information theoretically secure fully homomorphic encryption scheme. Here we answer that question in the negative by proving that quantum mechanics does not allow for efficient information theoretically secure fully homomorphic encryption that perfectly conceals the plaintext. To achieve this we first formalise the notion of quantum homomorphic
Yu et al. REF prove a no-go result: if interaction is not allowed, there does not exist QFHE scheme with perfect security.
Limitations on information theoretically secure quantum homomorphic encryption
Phys. Rev. A 90, 050303 (2014)
Physics Computer Science