This article defines encrypted gate, which is denoted by @math . We present a gate-teleportation-based two-party computation scheme for @math , where one party gives arbitrary quantum state @math as input and obtains the encrypted @math -computing result @math , and the other party obtains the random bits @math . Based on @math , we propose a method to remove the @math -error generated in the homomorphic evaluation of @math -gate. Using this method, we design two non-interactive and perfectly secure QHE schemes named GT and VGT . Both of them are @math -homomorphic and quasi-compact (the decryption complexity depends on the @math -gate complexity). Assume @math -homomorphism, non-interaction and perfect security are necessary property, the quasi-compactness is proved to be bounded by @math , where @math is the total number of @math -gates in the evaluated circuit. VGT is proved to be optimal and has @math -quasi-compactness. According to our QHE schemes, the decryption would be inefficient if the evaluated circuit contains exponential number of @math -gates. Thus our schemes are suitable for homomorphic evaluation of any quantum circuit with low @math -gate complexity, such as any polynomial-size quantum circuit or any quantum circuit with polynomial number of @math -gates.
@cite_15 prove a no-go result: if interaction is not allowed, there does not exist QFHE scheme with perfect security. An enhanced no-go result has been proved independently by Newman and Shi @cite_18 and Lai and Chung @cite_27 : if interaction is not allowed, there does not exist ITS QFHE scheme. This article focuses on the non-interactive and perfectly secure QHE schemes. Our schemes are quasi-compact, so they are not QFHE schemes, and then our result does not contradict with those no-go results. Though our schemes are not QFHE schemes, they can implement any unitary quantum circuit homomorphically (maybe inefficiently).
@cite_27 @cite_15 @cite_18
2079128711 2098611377
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 localization argument, that deterministic fully homomorphic encryption necessarily incurs exponential overhead if perfect security is required. We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In particular, we show that in order to transmit n qubits privately, 2n bits of shared private key are necessary and sufficient. This result may be viewed as the quantum analogue of the classical one-time pad encryption scheme.