量子アルゴリズムを活用した耐量子公開鍵暗号の安全性解析

使用量子算法进行抗量子公钥密码学的安全分析

基本信息

批准号：
19K20267
负责人：
高安敦
金额：
$ 2.58万
依托单位：
The University of Tokyo (2019, 2021-2022)National Institute of Information and Communications Technology (2020)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2019
资助国家：
日本
起止时间：
2019-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

今年度は、バイナリ楕円曲線上の離散対数問題を解くShorのアルゴリズムの効率的な実装法を提案した。バイナリ楕円曲線上の対数問題を解くShorのアルゴリズムでは、楕円曲線加算を行うために、2次拡大体における逆元計算を実行する必要がある。そのために、量子GCD逆元計算法と量子FLT逆元計算法が知られており、前者はより少ない量子ビットで実行可能であり、後者はより浅い回路で実行可能であることがわかっていた。我々は、量子FLT逆元計算法に着目して新たな成果を得る。特に、これまでの量子FLT逆元計算法はItoh-Tsujiiの古典FLT逆元計算法を量子化したものであったが、これを一般化し、任意の加法連鎖列に基づいて量子FLT逆元計算を実行可能であることを示した。その結果、これまでよりフレキシブルに演算過程を決定することが可能になった。事実、より適切な加法連鎖列を見つけることで、既存の量子FLT逆元計算法を用いた時よりもより量子ビット数や回路の深さを削減してバイナリ楕円曲線上の離散対数問題を解くShorのアルゴリズムを実装可能であることを示した。本結果は、査読付き国際会議CT-RSA 2023で発表を行った。また、耐量子計算機暗号の一つである符号問題に関わるsyndrome decoding問題を解くためのinformation set decodingアルゴリズムの改良を行なった。information set decodingアルゴリズムは古くから研究されており、これまで様々なアルゴリズムが提案されているが、我々は、量子ビットが制限されている状況では、既存の量子information set decodingアルゴリズムより高速にsyndrome decoding問題を解く新たなアルゴリズムを提案した。本結果は査読付き国際会議ACISP 2023で発表予定である。

今年，我们提出了对Shor算法的有效实施，以解决二进制椭圆曲线上的离散对数问题。在Shor的算法中，用于解决二元椭圆曲线上的对数问题，有必要在二次放大倍率上执行反相反的计算，以添加椭圆形曲线。因此，已知量子GCD逆和量子FLT逆计算，前者能够以较少的量子的速度执行，后者能够用较浅的电路执行。我们通过专注于量子FLT逆计算方法获得新的结果。特别是，从ITOH-TSUJII的经典FLT逆计算方法中量化了先前的量子FLT反相反计算方法，这被推广以表明可以根据任意加性链序列执行量子FLT逆计算。结果，比以前更灵活地确定计算过程变得有可能。实际上，我们已经表明，通过找到一个更合适的加性链序列，可以实现Shor的算法，该算法通过减少量子和电路深度的数量来解决二进制椭圆曲线上离散的对数问题，而不是使用现有的量子量子FLT FLT计算方法。结果是在同行评审的国际会议CT-RSA 2023上提出的。此外，我们改进了信息集解码算法，以解决与代码问题有关的综合征解码问题，这是量子耐药的计算机密码之一。信息集解码算法已经进行了很长时间，并且到目前为止已经提出了各种算法，但是我们提出了一种新算法，该算法与现有的量子信息集相比，在Qubits的情况下，解决综合征解码问题的速度要快。结果将在经过同行评审的国际会议ACISP 2023上介绍。