NTTは2023年11月6日、量子計算機に対する安全性(頑強性)と通信効率性(定数ラウンド性)を両立するコミットメントを、一方向性関数のみで構成する方法を見出したと発表した。一方向性関数が破られないという仮定の下で安全性と通信効率性が両立することで、量子計算機に対する安全性と効率性を両立する秘密計算への応用が期待できるとしている。同社は今回の成果を、理論計算機科学の国際会議「IEEE Symposium on Foundations of Computer Science(FOCS) 2023」で発表する。
NTTは、量子計算機に対する安全性(頑強性)と通信効率性(定数ラウンド性)を両立するコミットメントを、一方向性関数のみで構成する方法を見出した。一方向性関数が破られないという仮定の下で、一方向性関数のみで安全性と通信効率性を両立するというもの(図1)。
拡大画像表示
コミットメントとは、送信者と受信者の間で値を共有するプロトコルのこと。送信者が受信者に暗号化済みの値を送信し、後から付加的な情報を送って受信者が値を参照できるようにする。応用例として、複数のユーザーが自身のデータを秘匿したまま協力して計算をする秘密計算がある。今回の成果により、量子計算機に対する安全性と効率性を両立する秘密計算への応用が期待できるとしている。
「量子計算機の性能が将来向上すると、巨大な合成数であっても容易に素因数分解できるようになり、現在広く使われているRSA暗号は解読されてしまう。このため、量子計算機でも解読が難しい耐量子暗号の研究が活発に行われている。なかでも公開鍵暗号、電子署名、鍵交換については米国立標準技術局(NIST)が標準化を進めるなど実用レベルの研究が進んでいる」(NTT)
一方で、その他の暗号プロトコルの量子計算機に対する安全性については、理論的に未解明な部分が多いと指摘。なかでもコミットメントについては、量子計算機に対して頑強性を満たすには、達成したい安全性強度に応じて通信回数を増やすか、一方向性関数よりも強い構成要素を用いるかのどちらかの方法しか知られていなかったという。
今回、NTT特別研究員の山川高志氏は、NTT Research Cryptography & Information Security LabのXiao Liang博士とStony Brook大学のOmkant Pandey准教授と共著で投稿した論文において、量子計算機に対する頑強性と、達成したい安全性強度に通信回数が依存しないという通信効率性(定数ラウンド性)を同時に満たすコミットメントを、一方向性関数のみで構成した(図2)。
拡大画像表示
古典計算機に対する安全性のみであれば、同様の性質を持つコミットメントは2011年から知られていたという。一方、量子計算機に対する安全性を達成することは未解決だった。今回、従来とは異なる手法でコミットメントを設計し直すことによって、量子計算機に対する頑強性を証明したという。