研究室

出町メッセ長崎で開催されたSCIS2024（2024年1月23日–26日））にて，研究室から以下の発表を行いました．

• NARKsのためのReed-Solomon符号語に基づくVector Oracleコンパイラ，by 赤田 真悟，國廣昇，2B3-3
• 複数Approximate Divisor Multiplesを解くアルゴリズムの提案とその応用，by 下江 直輝，國廣 昇，2B4-4
• ECDSAのランダムなnonceに対するフーリエ解析ベース攻撃，by 大﨑俊輔，國廣昇，4B2-6

沖縄県OISTで開催されたQIT49（2023年12月17日—19日）にて，研究室から以下の1件のポスター発表を行いました．

• タイトル：量子読み出し専用メモリの効率化とNISQデバイスを想定した小さな整数に対する素因数分解への適用
• 著者： 桂潔成，國廣昇
• 妙録：ショアの素因数分解アルゴリズムの発見により，現在用いられているRSA暗号が将来的に解読可能となることが知られている．そのため，解読可能な時期を正確に見積もるために，現在の実機の持つ素因数分解能力を評価する必要がある．ショアの素因数分解アルゴリズムの実機による実験は行われているが，汎用回路構成ではCX深さが大きく実験が困難なことから，回路の大幅な簡略化が行われており正確な評価となっていない．また，複数提案されている汎用回路構成の中で，小さい整数の素因数分解に対してどれが最も効率的かどうかは明らかではない．そこで本研究では，汎用回路構成の効率化のために，構成要素の一つである量子読み出し専用メモリのより効率的な回路構成を提案する．加えて，複数の素因数分解回路構成をqiskit上で実装することで，小さい整数の素因数分解を行う場合に最も効率的な回路構成とその計算リソースを明らかにする．結果として，量子読み出し専用メモリの改良により素因数分解回路のCX深さを$16%$改善し，$N=21$の素因数分解に$24$量子ビット，CX深さ$8187$の量子回路で実現可能であることがわかった．しかしながら，現在のNISQデバイスの性能では依然として実験は困難であり，更なる効率化が必要である．

アクロス福岡で開催されたCSS2023（2023年10月30日—11月2日））にて，研究室から以下の発表を行いました．

• ECDSAに対する4-list sum algorithmを用いた攻撃の評価， by 大﨑俊輔，國廣 昇，2E3-3，CSS2023, 2023年10月
• Approximate Divisor Multiples問題の多変数線形方程式への拡張，by 下江直輝，國廣昇，3E2-1，CSS2023, 2023年10月

京都大学桂キャンパスで開催されたQIT48（2023年05月29日–30日）にて，研究室から以下の1件の発表を行いました．

• タイトル：量子状態の事前設定による効率的な耐故障性近似量子フーリエ変換
• 著者： 大西健斗（三菱電機），國廣昇
• 妙録：本稿では，耐故障性を考慮した，近似量子フーリエ変換の効率化を行う．量子フーリエ変換は，量子計算機が古典計算機より優位性を持つための重要な演算であり，多数の構成法が考案されている．その中でも，特に，近似量子フーリエ変換は，小さな誤りを許す代わりに，計算コストの大幅な減少が可能である．しかし，耐故障性を考慮する場合，量子フーリエ変換を構成する位相ゲートは，その計算量のオーダーを増大させるほど多大なコストを必要とする．本研究では，計算時間の期待値が定数となる位相ゲートを利用した，効率的な近似量子フーリエ変換を提案した．特に，本研究の提案手法は，計算で利用する量子状態を保存するための補助ビットを用意する代わりに，時間計算量の大幅な短縮に成功した．

福岡県リーガロイヤルホテル小倉で開催されたSCIS2023（2023年1月24日–27日））にて，研究室から以下の発表を行いました．

• 素因数分解問題に対するShorアルゴリズムの実装と量子計算機シミュレータを用いた実験，by 山口 純平（富士通），伊豆 哲也（富士通），國廣 昇，4A2-3

慶應義塾大学矢上キャンパスで開催されたQIT47（2022年12月8日–9日）にて，研究室から以下の2件の発表を行いました．

1件目

• タイトル：近似量子フーリエ変換を用いた量子位相推定アルゴリズムの成功率評価
• 著者：桂潔成，國廣昇
• 概要：現在インターネット上で広く利用されているRSA暗号は，大規模な量子コンピュータが実現するとショアのアルゴリズムによって現実的な時間で解かれることが知られている．ショアのアルゴリズムでは，ゲート数削減のため，角度の小さい位相回転ゲートを削除する近似が行われるが，近似パラメータとアルゴリズムの成功確率とのトレードオフを知ることは，利用可能な計算リソースや扱う問題サイズから近似パラメータを決定する際に重要になる．本研究では，近似フーリエ変換を用いた量子位相推定の近似パラメータと成功率のトレードオフを明らかにする．そのために，アルゴリズムの成功確率を数値計算により評価した．ショアのアルゴリズムは量子位相推定の応用例であり，位相推定に対する成功率評価がそのまま適用できる．これにより，近似パラメータを適切に設定することが可能となる．

2件目

• タイトル：効率的な近似量子フーリエ変換を利用したShorアルゴリズム
• 著者： 大西健斗（三菱電機），國廣昇
• 妙録：Shorアルゴリズムは，素因数分解問題や離散対数問題を多項式時間で解く量子アルゴリズムであり，その計算量評価は，実社会にとって極めて重要である．本稿では，Shorアルゴリズムの実装方法の一つである，量子フーリエ変換(QFT)を利用したRinesとChuangの実装方法の改良を行う．本稿では，新たな近似QFTの実装方法を提案し，その近似QFTをRinesとChuangの実装方法に適用することで，$T$ゲート数が1/3，$T$-depthが$1/2$に減少することを示す．その上で，KQを最小にする量子回路のスケジューリング方法を提案する．

熊本県・熊本城ホールで開催されたCSS2022（2022年10月24日-27日）にて，研究室のメンバーが以下の発表を行いました．

1件目

• タイトル：複数ビットのnonce漏洩攻撃に対するECDSA署名数の評価
• 著者：大﨑俊輔，國廣昇
• 講演番号：4BII-2

グランキューブ大阪／オンラインで開催されたSCIS2022にて，研究室のメンバーが以下の3件の発表を行いました．

• フーリエ解析ベース攻撃に対するECDSAのエラーレートに基づく解析 , by 大﨑俊輔，國廣昇, 1C1-2
• サイドチャネル攻撃により得られるBinary GCD演算系列に対するエラーモデル，by 谷健太，國廣昇，1C1-5
• データ分布情報を用いたレンジクエリに対するボリューム漏洩攻撃，by 小谷俊輔，國廣昇，2B1-2

オンラインで開催されたCSS2021にて，研究室のメンバーが以下の2件の発表を行いました．

• エラー付きLS系列に対するエラー訂正アルゴリズム，谷健太，國廣昇，2E4-1
• レンジクエリに対するノイズ付きボリューム漏洩攻撃，小谷俊輔，國廣昇，2E4-2

オンラインで開催されたSCIS2021にて，研究室のメンバーが以下の4件の発表を行いました．

• Revisiting an improvement to the quaternion analogue of the l-isogeny path problems, by Jo Hyungrok, 2A2-3
• レンジクエリに対するボリューム漏洩攻撃の改良，by 小谷俊輔，國廣昇，2C2-4
• RSA暗号の鍵生成におけるBinary GCDアルゴリズムの安全性評価，by 谷健太，國廣昇，3D1-3
• 数論変換におけるサイドチャネル攻撃に対するRing-LWE暗号方式およびModule-LWE暗号方式の理論的な安全性解析，by 大西健斗，國廣昇，3D1-4