室井 謙典
abstract
耐量子暗号の候補の一つであるGiophantus[AGO+17]は, 不定方程式の最小解を求める問題の計算困難性に基づいている. また, LWE問題と多変数多項式を組み合わせたIE-LWE問題という新しい分布識別問題の計算困難性を仮定すれば, GiophantusはIND-CPA安全である. 本研究ではIE-LWE問題に対する新しいt=1の代入識別攻撃を提案する. 提案攻撃では, IE-LWE問題を整数上の最近ベクトル問題に帰着することで分布を識別する. 計算機実験により, 既存の代入攻撃に強力なパラメータに対しても現実的な時間で攻撃できることを示した.