汎用的な量子回路に対するプログラム難読化を初めて実現 ～Shorの素因数分解アルゴリズムを含む量子回路におけるセキュリティ手法の確立～
日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：島田 明、以下「NTT」）は、量子回路（※1）に関する難読化の研究において、これまでより汎用的な量子回路に対して暗号学的に安全なプログラム難読化を可能にするセキュリティ手法を考案しました。この結果は、量子計算機の優位性を示す例としてよく知られているShorの素因数分解アルゴリズムの量子回路に対するプログラム難読化も可能であることを示すものです。本成果により、難読化できる量子回路の範囲が広がることで、量子計算の世界におけるプログラム等に対する不正な解析を防ぐことに寄与し、知的財産保護につながることが期待されます。
なお、本成果は理論計算機科学における最高峰の国際会議である55th Annual ACM Symposium on Theory of Computing (ACM STOC 2023)（※2）において発表されます。
1．背景
プログラムの難読化とは、プログラムの機能を損なうことなくそのコードを書き換えることであり、主にリバースエンジニアリング(※3)によるプログラムの解析やそれによる知的財産の侵害などを防ぐために行われます。既存の古典的な計算に対する難読化に関する暗号の側面からの理論的な研究成果は2000年代に入ってから出始めるようになり、汎用的な計算に対する難読化の提案は2013年のGargらの成果(※4)に遡ります。
一方、この間に量子の物理的特性を生かした量子計算に関する研究も進み、古典計算の世界で考えられてきた暗号、ゼロ知識証明（※5）、多者間秘密計算等を量子計算の世界でどのように実現できるかといった研究が進み、古典計算との類似点や相違点なども徐々に明らかになってきました。しかしながら、量子計算の世界で難読化が可能かという問題については、これまで未解決であり、これまで知られている量子回路の難読化に関する結果としては非常に限定的な量子回路のクラス、例えばNULL量子回路と呼ばれる常にゼロを出力する回路などに対するものだけでした。
2．研究の成果
本研究において、NTTの北川冬航准特別研究員、西巻陵特別研究員、山川高志特別研究員は、UC BerkleyのJames Bartusek氏と共著で投稿した論文（※6）において、疑似確定的量子回路という量子回路のクラスに対して暗号学的に安全なプログラム難読化手法を初めて実現しました。疑似確定的量子回路とは、（重ね合わせのような量子状態ではなく）古典の入力に対して決まった古典の出力を１に近い確率で返す量子回路です。この量子回路は、古典的な真理値表の計算やBQP（※7）と呼ばれる量子計算機で効率的に計算できるとされる問題の内、答えがyesかnoのどちらかに決まる問題を解くことができます。これは、量子計算機の優越性を示す例として有名なShorの素因数分解アルゴリズムを含む汎用的なものであり、このような汎用的な量子回路に対する難読化手法は本研究で初めて得られた成果です。本成果は、古典の検証プロトコルに、量子の特性を生かした特殊な性質をもつディジタル署名を実現するアイディアを組み合わせるというアプローチで得られました。特殊な性質とは、ある文書に対して署名を生成するとその署名鍵は他の文書に対して一切署名を生成できなくなる１度限りの署名鍵になっているというものです。これは署名鍵を量子状態で表すことで実現できるものであり、量子ならではの特性を利用したものになっています。
３．今後の展開
本研究を通じ、量子計算におけるプログラム等の難読化に対してこれまでより広い範囲の量子回路で難読化が可能であることを証明しました。本成果は理論計算機科学における最高峰の国際会議である55th Annual ACM Symposium on Theory of Computing (ACM STOC 2023)に採択されました。
今後は、BQPクラスだけでなく、様々なクラスに適用可能な難読化手法の検討を推進します。
＜用語解説＞
※1 量子回路：量子ビットの状態を変化させる量子ゲートを組み合わせ、所望の量子計算を行うための回路モデルのこと。
※2 ACM STOC 2023 http://acm-stoc.org/stoc2023/
※3 リバースエンジニアリング：ソフトウェアの実行ファイルに対し逆アセンブル・逆コンパイルをかけるなどしてソースコードを抽出し、プログラムの動作を解析すること。
※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 ゼロ知識証明：ある命題が真であることを、真であるという情報以外漏らすことなく証明する手法。
※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。計算量クラスのひとつ。ある問題がBQPに属するならば、高い確率で正答を返す多項式時間で計算可能な量子計算機のアルゴリズムが存在する。
なお、本成果は理論計算機科学における最高峰の国際会議である55th Annual ACM Symposium on Theory of Computing (ACM STOC 2023)（※2）において発表されます。
1．背景
プログラムの難読化とは、プログラムの機能を損なうことなくそのコードを書き換えることであり、主にリバースエンジニアリング(※3)によるプログラムの解析やそれによる知的財産の侵害などを防ぐために行われます。既存の古典的な計算に対する難読化に関する暗号の側面からの理論的な研究成果は2000年代に入ってから出始めるようになり、汎用的な計算に対する難読化の提案は2013年のGargらの成果(※4)に遡ります。
一方、この間に量子の物理的特性を生かした量子計算に関する研究も進み、古典計算の世界で考えられてきた暗号、ゼロ知識証明（※5）、多者間秘密計算等を量子計算の世界でどのように実現できるかといった研究が進み、古典計算との類似点や相違点なども徐々に明らかになってきました。しかしながら、量子計算の世界で難読化が可能かという問題については、これまで未解決であり、これまで知られている量子回路の難読化に関する結果としては非常に限定的な量子回路のクラス、例えばNULL量子回路と呼ばれる常にゼロを出力する回路などに対するものだけでした。
2．研究の成果
本研究において、NTTの北川冬航准特別研究員、西巻陵特別研究員、山川高志特別研究員は、UC BerkleyのJames Bartusek氏と共著で投稿した論文（※6）において、疑似確定的量子回路という量子回路のクラスに対して暗号学的に安全なプログラム難読化手法を初めて実現しました。疑似確定的量子回路とは、（重ね合わせのような量子状態ではなく）古典の入力に対して決まった古典の出力を１に近い確率で返す量子回路です。この量子回路は、古典的な真理値表の計算やBQP（※7）と呼ばれる量子計算機で効率的に計算できるとされる問題の内、答えがyesかnoのどちらかに決まる問題を解くことができます。これは、量子計算機の優越性を示す例として有名なShorの素因数分解アルゴリズムを含む汎用的なものであり、このような汎用的な量子回路に対する難読化手法は本研究で初めて得られた成果です。本成果は、古典の検証プロトコルに、量子の特性を生かした特殊な性質をもつディジタル署名を実現するアイディアを組み合わせるというアプローチで得られました。特殊な性質とは、ある文書に対して署名を生成するとその署名鍵は他の文書に対して一切署名を生成できなくなる１度限りの署名鍵になっているというものです。これは署名鍵を量子状態で表すことで実現できるものであり、量子ならではの特性を利用したものになっています。
３．今後の展開
本研究を通じ、量子計算におけるプログラム等の難読化に対してこれまでより広い範囲の量子回路で難読化が可能であることを証明しました。本成果は理論計算機科学における最高峰の国際会議である55th Annual ACM Symposium on Theory of Computing (ACM STOC 2023)に採択されました。
今後は、BQPクラスだけでなく、様々なクラスに適用可能な難読化手法の検討を推進します。
＜用語解説＞
※1 量子回路：量子ビットの状態を変化させる量子ゲートを組み合わせ、所望の量子計算を行うための回路モデルのこと。
※2 ACM STOC 2023 http://acm-stoc.org/stoc2023/
※3 リバースエンジニアリング：ソフトウェアの実行ファイルに対し逆アセンブル・逆コンパイルをかけるなどしてソースコードを抽出し、プログラムの動作を解析すること。
※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 ゼロ知識証明：ある命題が真であることを、真であるという情報以外漏らすことなく証明する手法。
※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。計算量クラスのひとつ。ある問題がBQPに属するならば、高い確率で正答を返す多項式時間で計算可能な量子計算機のアルゴリズムが存在する。
