First construction of program obfuscation for general-purpose quantum circuits
Establishment of security methods in quantum circuits including Shor's factorization algorithm

Tokyo - June 20, 2023 - NTT Corporation (President and CEO: Akira Shimada, “NTT”) has devised a security method that enables cryptographically secure program obfuscation for more general-purpose quantum circuits (*1). This result shows that it is also possible to obfuscate quantum circuits implementing Shor's factorization algorithm, a well-known example of the superiority of quantum computers. This achievement is expected to contribute to the prevention of unauthorized analysis of programs in the world of quantum computing and lead to the protection of intellectual property by expanding the range of quantum circuits that can be obfuscated.
　The results will be presented at the 55th Annual ACM Symposium on Theory of Computing (ACM STOC 2023) (*2), the premier international conference in theoretical computer science.

1. Background

Obfuscation of a program refers to the rewriting of the code without impairing the function of the program, mainly to prevent the analysis of the program by reverse engineering (*3) and the infringement of intellectual property by doing so. Theoretical work on obfuscation of existing classical computation from the aspect of cryptography began to emerge in the 2000s, and the proposal of obfuscation for general computation dates back to the work of Garg et al. (*4) in 2013.
　On the other hand, during this period, research on quantum computation utilizing the physical properties of quantum has advanced. Research has advanced on how to achieve encryption, zero-knowledge proof (*5), and multiparty computation, which have been considered in the world of classical computation, in the world of quantum computation. The similarities and differences with classical computation have gradually become clear. However, the question of whether obfuscation is possible in the world of quantum computing has been an open question. The only known result on obfuscation of quantum circuits has been for a very limited class of quantum circuits, such as “null” quantum circuits, which always output zero.

2．Results

In this research, in a paper (*6) co-authored with James Bartusek of UC Berkley, NTT's Associate Distinguished Researcher Fuyuki Kitagawa, Distinguished Researcher Ryo Nishimaki, and Distinguished Researcher Takashi Yamakawa developed a cryptographically secure program obfuscation method for a class of quantum circuits called pseudo-deterministic quantum circuits for the first time. A pseudo-deterministic quantum circuit is a quantum circuit that returns a fixed classical output to a classical input (rather than a quantum state such as superposition) with a probability close to 1. This quantum circuit can compute classical truth tables and solve problems for which the answer is always determined as yes or no, a sub-class of BQP, (*7) which can be efficiently computed by quantum computers. This is a general-purpose computation including Shor's factorization algorithm, which is famous as an example of the superiority of quantum computers, and this obfuscation approach for such a general-purpose quantum circuit is the first result obtained in this study. This result was achieved through an approach that combines classical verification protocols with the idea of realizing digital signatures with a unique property that takes advantage of quantum properties. The unique property is that when you generate a signature for a document, the signature key is a one-shot signature key that cannot generate any signatures for other documents. This can be achieved by representing the signature key in a quantum state, taking advantage of the unique properties of quantum.

Figure 1. Obfuscable quantum circuits

3. Future work

Through this research, we have proved that obfuscation is possible for a wider range of quantum circuits compared to the known results. This result was selected for the 55th Annual ACM Symposium on Theory of Computing (ACM STOC 2023), the premier international conference in theoretical computer science.
　In the future, we will promote the study of obfuscation methods that can be applied to various classes, not just BQP class.

^(*1)Quantum circuit: A circuit model for performing desired quantum calculations by combining quantum gates that change the state of a qubit.

^(*2)ACM STOC 2023 http://acm-stoc.org/stoc2023/

^(*3)Reverse engineering: Extracting source code by disassembling and decompiling software executables and analyzing program behavior.

^(*4)Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput., 45(3):882-929, 2016.

^(*5)Zero-knowledge proof: A method of proving the truth of a proposition without leaking any information except that it is true.

^(*6)James Bartusek (UC Berkeley); Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa (NTT Social Informatics Laboratories), Obfuscation of Pseudo-Deterministic Quantum Circuits.

^(*7)BQP: Bounded-error Quantum Polynomial time. One of the computational classes. If a problem belongs to BQP, there are algorithms for quantum computers that can be computed in polynomial time with a high probability of returning the correct answer.

About NTT

NTT believes in resolving social issues through our business operations by applying technology for good. We help clients accelerate growth and innovate for current and new business models. Our services include digital business consulting, technology and managed services for cybersecurity, applications, workplace, cloud, data center and networks all supported by our deep industry expertise and innovation.
　As a top 5 global technology and business solutions provider, our diverse teams operate in 88 countries and regions and deliver services to over 190 of them. We serve 85% of Fortune Global 100 companies and thousands of other clients and communities around the world.
　For more information on NTT, visit www.global.ntt.