世界初、高い耐量子安全性と通信効率性を両立するコミットメントを一方向性関数のみにより実現
～量子計算機を持つ攻撃者に対して安全かつ効率的な暗号プロトコルを構成するための基盤的な技術を開発～

日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：島田　明、以下「NTT」）は、量子計算機に対する高い安全性（頑強性（※1））と通信効率性（定数ラウンド性（※2））を両立するコミットメント（※3）を暗号理論における最も基本的な構成要素である「一方向性関数（※4）」のみを用いて世界で初めて構成しました。本成果を通じ、将来には量子計算機に対する高い安全性と効率性を両立する秘密計算への応用が期待されます。
　なお、本成果は理論計算機科学における最高峰の国際会議であるIEEE Symposium on Foundations of Computer Science (FOCS) 2023（※5）において発表されます。

1．背景

量子計算機は量子力学の原理を応用した計算機で、現在世界中で開発競争が進められています。1994年に示されたShorの素因数分解アルゴリズムにより、現在広く使われているRSA暗号は量子計算機が実現すれば解読されてしまうことが判明しています。このため、近年量子計算機でも解読不可能な耐量子計算機暗号の研究が活発に行われています。
　耐量子計算機暗号のなかでも公開鍵暗号や電子署名については、アメリカ国立標準技術局（NIST）により標準化が進められるなど、実用レベルの研究が進んでいる一方、その他の暗号プロトコルの量子計算機に対する安全性(耐量子安全性)については理論的に未解明な部分が多くあります。中でも、量子計算機に対して頑強性と呼ばれる強い安全性を満たすコミットメントを構成するためには、達成したい安全性強度に応じて通信回数を増やすか、一方向性関数よりも強い構成要素を用いるかのどちらかの方法しか知られていませんでした。

2．研究の成果

NTTの山川高志特別研究員は、NTT Research Cryptography & Information Security LabのXiao Liang博士とStony Brook大学のOmkant Pandey准教授と共著で投稿した論文（※6）において、量子計算機に対する頑強性と通信回数が達成したい安全性強度に依存しないという通信効率性（定数ラウンド性）を同時に達成するコミットメントを最低限の仮定である一方向性関数のみを用いて世界で初めて構成しました。

図1. コミットメント方式の例。送信者が最初に決めた値を受信者との通信・計算を通じて受信者に共有する。

図2. 耐量子頑強性を満たさないコミットメントの脆弱性の例。「Data_A」にコミットしても、量子計算機を用いた攻撃者により「Data_A」 と関連した値「Data_A'」に改ざんされてしまう。

古典計算機に対する安全性のみを考慮する場合には、同様の性質を持つコミットメントは2011年から知られていましたが、量子計算機に対する安全性を達成することはそれから10年以上未解決でした。これは、量子計算機は古典計算機と全く異なる原理に基づいて動作するため、従来の古典計算機を用いる攻撃者に対する安全性証明は量子計算機を用いる攻撃者に対しては適用できないためです。そのため、従来の方式は量子計算機を用いる攻撃者に対しては脆弱性が存在する可能性がありました。一方で、山川らは従来とは異なる手法でコミットメントを設計し直すことにより、量子計算機に対する頑強性を証明することに成功しました。
　頑強性を持つコミットメントの応用として、例えば複数のユーザーが自身のデータを秘匿したまま協力して計算をする秘密計算プロトコルがあり、本成果は将来的に量子計算機に対してより安全でより効率的な秘密計算プロトコルの開発につながることが期待されます。
　本成果は理論計算機科学における最高峰の国際会議であるIEEE Symposium on Foundations of Computer Science (FOCS) 2023に採択され、11/6のSession 4Aにおいて発表される予定です。なお、山川特別研究員の論文がFOCSに採択されるのは、一昨年度、昨年度（※7）に続き3年連続となります。

3．今後の予定

今回導入した新たな安全性証明手法はコミットメントに限らずより広範な応用を持つことが期待されます。今後は本手法を秘密計算プロトコル等の他の暗号プロトコルに適用することを通じ、耐量子安全性を証明することをめざします。
　本研究を通じ、量子計算機時代の到来に向けた、安心・安全な通信を提供する暗号プロトコルの開発に貢献します。

^（※1）頑強性：あるユーザーがあるメッセージに対してコミットした際に、別のユーザーがそれを改ざんして関連したメッセージに対してコミットすることは出来ないという性質

^（※2）定数ラウンド性：送信者と受信者の間の通信の往復回数が達成したい安全性強度によらず一定であるという性質

^（※3）コミットメント：将棋の封じ手を電子的に実現する暗号プロトコル。つまり、「コミット」したメッセージは後に公開するまでは秘密であるという性質（秘匿性）と「コミット」した後はメッセージを変えることが出来ないという性質（拘束性）を同時に実現するようなプロトコル。ゼロ知識証明や秘密計算等のより高機能な暗号プロトコルの構成要素として幅広い応用を持つ。

^（※4）一方向性関数：計算するのは容易だが逆算するのは困難であるような関数。暗号理論における最低限の構成要素であるとされる。

^（※5）FOCS 2023 https://focs.computer.org/2023/

^（※6）A New Approach to Post-Quantum Non-Malleability. Xiao Liang (NTT Research), Omkant Pandey (Stony Brook University), Takashi Yamakawa (NTT Social Informatics Laboratories)

^（※7）https://group.ntt/jp/topics/2022/02/08/accepted_paper_focs2021.html
https://group.ntt/jp/newsrelease/2022/10/31/221031b.html