量子コンピュータとサイドチャネル攻撃に対して安全な公開鍵暗号

本年度は漏洩耐性をみたし，選択暗号文攻撃に対して安全(CCA安全)である耐量子暗号の実現に向けて研究を行なった．本年度は特に，耐量子暗号の一つである符号に基づいた暗号方式の安全性の根拠である Learning Parity with Noise (LPN) 問題に注目した．多くの計算問題と同様にLPN問題にも，与えられた問題の解を計算する探索問題と与えられた問題に解が存在するかを判定する判定問題の2つが定義できる．明らかに探索問題の方が難しく，その困難性を仮定する方が弱い仮定である．暗号方式の安全性の根拠として直接結び付けられることが多いのは判定問題の困難性であるが，探索問題の困難性を基準とした場合に暗号方式の安全性がどの程度担保されるかを調べるためには，2つの問題の困難性のギャップ，すなわち探索問題と判定問題の間の帰着とその効率を調べる必要がある．これまでそのような帰着は古典計算による方法が知られていたが，LPN問題に基づく暗号方式が量子コンピュータの存在下での利用が期待されているため，量子計算を用いた帰着を検討することがLPN問題への理解を深める上で有用である．そこで本年度は，LPN問題の探索と判定問題の間に初めて量子帰着，すなわち判定LPN問題を解くオラクルに重ね合わせ状態の質問をすることで探索LPN問題を解く方法を示した．特に，得られた量子帰着は既知の古典帰着よりオラクルへの質問回数という点で帰着効率を改善できる．つまり，量子コンピュータの存在下では，2つのLPN問題の困難性のギャップが小さくなり得ることが明らかになった．以上の結果を国内会議SCIS2022で報告した．

本年度は漏洩耐性をみたし，選択暗号文攻撃に対して安全(CCA安全)である耐量子暗号の実現に向けて研究を行なった．本年度は特に，耐量子暗号の一つである符号に基づいた暗号方式の安全性の根拠である Learning Parity with Noise (LPN) 問題に注目した．多くの計算問題と同様にLPN問題にも，与えられた問題の解を計算する探索問題と与えられた問題に解が存在するかを判定する判定問題の2つが定義できる．明らかに探索問題の方が難しく，その困難性を仮定する方が弱い仮定である．暗号方式の安全性の根拠として直接結び付けられることが多いのは判定問題の困難性であるが，探索問題の困難性を基準とした場合に暗号方式の安全性がどの程度担保されるかを調べるためには，2つの問題の困難性のギャップ，すなわち探索問題と判定問題の間の帰着とその効率を調べる必要がある．これまでそのような帰着は古典計算による方法が知られていたが，LPN問題に基づく暗号方式が量子コンピュータの存在下での利用が期待されているため，量子計算を用いた帰着を検討することがLPN問題への理解を深める上で有用である．そこで本年度は，LPN問題の探索と判定問題の間に初めて量子帰着，すなわち判定LPN問題を解くオラクルに重ね合わせ状態の質問をすることで探索LPN問題を解く方法を示した．特に，得られた量子帰着は既知の古典帰着よりオラクルへの質問回数という点で帰着効率を改善できる．つまり，量子コンピュータの存在下では，2つのLPN問題の困難性のギャップが小さくなり得ることが明らかになった．以上の結果を国内会議SCIS2022で報告した．