公開鍵や暗号文サイズが小さく計算効率の高い同種写像暗号QFESTAを開発 ～NIST標準化候補（SIKE）を破った攻撃手法を利用し新たな構成に成功～

発表のポイント：

従来の同種写像暗号SIKEが2022年に破られて以降、複数の代替案が考案されてきた中でQFESTAは最も計算効率が良い。
QFESTAの構成要素として開発した新たな同種写像暗号計算アルゴリズムRandIsogImagesは汎用性が高く、今後の同種写像暗号の開発を推進する構成要素と期待される。

　日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：島田　明、以下「NTT」）は、同種写像（※1）を用いて、量子計算機に対する高い安全性（IND-CCA（※2））と計算効率性を両立する新たな暗号方式QFESTAを構成しました。耐量子計算機暗号の候補である同種写像暗号は、ほかと比べ公開鍵や暗号文のデータサイズが小さいことから注目されており、中でもSIKEが注目を浴びていました。しかし、2022年にSIKEの安全性を破る攻撃手法が発見され、その後代替案が模索されてきましたが、いずれも暗号化と復号にかかる計算コストに大きな課題を抱えていました。
　今回NTTは、SIKEの代替案として提案された数多くの方式の中で、最も計算効率が高いQFESTAという方式を開発しました。今後はQFESTAの構成要素であるRandIsogImagesの電子署名等の暗号プロトコルへの応用についても検討を進めて参ります。
　なお、本成果を2024年8月に開催された暗号理論における最高峰国際会議であるCRYPTO 2024（※3）において発表しました。　　

1．背景
　量子計算機は量子力学の原理を応用した計算機で、現在世界中で開発競争が進められています。1994年に示されたShorのアルゴリズム(※4)により、現在広く使われているRSA暗号や楕円曲線暗号は量子計算機が実現すれば解読されてしまうことが判明しています。このため、量子計算機でも解読不可能な耐量子計算機暗号の研究が近年活発に行われています。
　耐量子計算機暗号の候補には、格子暗号、符号暗号、同種写像暗号などいくつかの種類があり、ポートフォリオ戦略として同時進行で研究が進められています。中でも、同種写像に基づく暗号方式である同種写像暗号は、ほかの候補と比べて公開鍵や暗号文のデータサイズが小さいことから注目されています。 (図1：QFESTAと主要な耐量子暗号のデータサイズの比較)
　特に、同種写像に基づく暗号方式(カプセル化方式（※5）)であるSIKEは、アメリカ国立標準技術局（NIST）の標準化コンペ(※6)でRound 4に残るなど注目を浴びていました。しかしながら、 2022年にSIKEの安全性を破る攻撃手法（※7）が発見されたことで、この方式はもはや安全ではなくなりました。それ以降、多くの代替案が提示されてきましたが、いずれも暗号化と復号にかかる計算コストに大きな課題を抱えていました。この課題を解決するため、新たな同種写像暗号の開発が進めら
れており競争が激化しています。