A quantum approach to fully homomorphic encryption.

Si-Hui Tan, Joshua A. Kettlewell, Yingkai Ouyang, Lin Chen, Joseph F. Fitzsimons

Abstract

Quantum homomorphic encryption (QHE) aims to allow secure processing of quantum data on untrusted servers. This paper introduces a private-key QHE scheme that leverages the group-theoretic properties of bosonic particles. By utilizing a "separation of concerns" strategy—where encryption acts on internal states and computation on spatial modes—the protocol achieves high information-theoretic security for a broad class of quantum operations. Unlike previous attempts, this approach avoids exponential data blow-up while significantly improving security bounds.

Introduction

In classical cryptography, Homomorphic Encryption (HE) enables a third party to perform computations on encrypted data without accessing the underlying plaintext. While classical HE relies on computational security—assumptions about the mathematical hardness of specific problems—quantum mechanics offers the potential for Information-Theoretic Security (ITS), which is mathematically unbreakable regardless of an adversary's computational power.

However, a fundamental "barrier" exists in quantum cryptography: it has been proven that perfect security for arbitrary computations is impossible unless the encrypted data size grows exponentially with the computation's complexity. This research seeks a middle ground, proposing a scheme that supports a wide range of computations with high, provable security and polynomial overhead.

Methodology: Group-Theoretic Encryption

The core of the proposed protocol is a group-theoretic approach designed to ensure that encryption operations "commute" with computation operations. If encryption and computation commute, the evaluator can process the data without needing to decrypt it first.

Technical Setup

The protocol utilizes a physical system of $m$ identical bosonic particles (e.g., photons). Each particle possesses two distinct degrees of freedom:

  1. Internal State: A $d$-level system (qudit) used for encryption.
  2. Spatial Mode: The physical path or location used for computation.
Schematic of the proposed quantum homomorphic encryption protocol showing the flow from encryption to evaluation and decryption.

As shown in the figure above, the process follows three main stages:

  • Encryption ($\mathcal{E}$): The user (Alice) encodes her message into the internal states of the $m$ particles using a secret key of random rotation angles.
  • Computation ($G$): The evaluator (Bob) performs the desired quantum computation by manipulating the spatial modes using linear optical elements like beam-splitters and phase-shifters.
  • Decryption ($\mathcal{E}^\dagger$): Because the spatial manipulations do not affect the internal states, Alice can retrieve the result by applying the inverse of her secret transformation.

Key Insights and Results

The success of this scheme hinges on the use of reducible representations of groups. While simple quantum systems are difficult to encrypt securely, reducible representations provide a "centralizer"—a set of operations that commute with the group—allowing for the necessary mathematical "room" to hide information.

Security and Efficiency

The most significant result is the proof of a "security gap." The authors demonstrate that as the number of particles ($m$) increases, the amount of information hidden grows faster than the information potentially leaked to an adversary.

  • Accessible Information: The information an attacker can extract is upper-bounded by $\log_2 m!$ bits.
  • Security Gap ($\Gamma$): For a system with $m$ particles and $d$ internal levels, the security gap is approximately $m \log_2(d/m) + m(\log 2)^{-1}$, a marked improvement over the logarithmic bounds in previous literature.
  • Scalability: The overhead for increasing security scales polynomially with message length, successfully bypassing the exponential barrier of earlier theoretical models.

Discussion and Future Work

While the scheme supports a dimension $m$ unitary group—covering a vast range of quantum optical computations—it is not yet "fully" universal. Future research will focus on determining the exact boundaries of computable functions within this framework and exploring the transition from a private-key to a public-key infrastructure. Achieving true universality may require minimal interaction between the user and evaluator, or a further refinement of the "broad class" of supported operations.

Summary updated

Abstract

Encryption schemes often derive their power from the properties of the underlying algebra on the symbols used. Inspired by group theoretic tools, we use the centralizer of a subgroup of operations to present a private-key quantum homomorphic encryption scheme that enables a broad class of quantum computation on encrypted data. A particular instance of our encoding hides up to a constant fraction of the information encrypted. This fraction can be made arbitrarily close to unity with overhead scaling only polynomially in the message length. This highlights the potential of our protocol to hide a non-trivial amount of information, and is suggestive of a large class of encodings that might yield better security.
BibTeX
@misc{tan2014quantum,
  author = {Si-Hui Tan and Joshua A. Kettlewell and Yingkai Ouyang and Lin Chen and Joseph F. Fitzsimons},
  title = {{A quantum approach to fully homomorphic encryption.}},
  year = {2014},
  eprint = {1411.5254},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1411.5254},
}
Figure