权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
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で発表予定である。

This year, a method for solving the discrete number problem on the curve of Shor is proposed. To solve the inverse problem on the curve, it is necessary to calculate the inverse element of the second order. The quantum GCD inverse element calculation method and the quantum FLT inverse element calculation method are known as the former and the latter as the latter. The quantum FLT inverse element calculation method has been developed. In particular, quantum FLT inverse element calculation method is different from Itoh-Tsujii classical FLT inverse element calculation method. Quantum FLT inverse element calculation can be realized by quantization and generalization. The result of the calculation is that the calculation is possible. In this paper, we discuss the application of the existing quantum FLT inverse element calculation method to solve the discrete pair problem on the quantum loop. The results of this paper are presented in the CT-RSA 2023 International Conference. The problem of syndrome decoding is solved by improving the information set decoding algorithm. Information set decoding is a new way to solve the problem of high speed syndrome decoding. The results of this paper are based on the results of ACISP 2023.