客观日本

评估密码技术安全风险,日本用量子计算机成功解答离散对数问题

2020年12月25日 信息通信

本文根据NICT成果发布编译整理而成

日本的信息通信研究机构(NICT)、庆应义塾大学、三菱日联金融集团(MUFG)及瑞穗金融集团(MHFG)组成的研究团队,在IBM Q Hub at Keio University所在的庆应义塾大学量子计算中心(KQCC)利用量子计算机IBM Quantum成功解答了小规模离散对数问题。

离散对数问题是非常重要的问题,是支撑现代信息社会的密码技术安全的基础之一,了解能用量子计算机解答的离散对数问题的规模是一项重要课题。另外,离散对数问题可以做实验的量子程序的选择范围很广,此次的实验是基于初步研究、即是否适用于将来预测密码威胁的量子计算机实验而实施的。

为确保量子计算机时代的密码安全,此次研究团队针对通过离散对数问题确保安全性的密码方式的破解时间评估,编写了了离散对数问题专用肖尔算法的程序,由此,利用量子计算机解答离散对数问题的实验全球首次取得了成功。

title

图1:此次研究的关于密码破解时间预测的成果图

在此次的实验中,NICT设计好实验用量子程序后,庆应大学、MUFG和MHFG针对超导量子计算机IBM Quantum提高了程序效率,并在IBM Quantum实机上进行了实验。通过共同对输出结果进行研究,确认解答了问题。

在实验中,研究团队针对离散对数问题的一些例题,面向量子计算机进行编程,调查了程序规模达到多大程度才能利用量子计算机解答问题。图2按规模大小列出了实验的程序,总结了利用量子计算机实机做实验的结果。执行此次实验中规模最小的量子程序①时,量子计算机输出了非常好的结果,但规模更大的程序②和③并没有输出良好的结果。

因此得出了以下结论:可利用现有技术解答的量子程序的规模介于图中的①和②之间。这是首次利用量子计算机实机解答离散对数问题。另外,对程序②的输出结果进行验证后得出的结论是,如果能把程序规模改小一些,还是有可能解出来的。

title

图2:解答离散对数问题的量子计算机程序的规模与实验结果

日语发布资料
编译:JST客观日本编辑部

专题网页