ある種の不定方程式の求解問題に基づく準同型暗号

摘要

耐量子公開鍵暗号の候補の 1 つと考える代数曲面暗号を発展させ，準同型性を持った公開鍵暗号を構成した。本暗号は不定方程式の求解問題に関連するある種の LWE 問題に安全性の根拠をおいており，乗算回数には制約はあるものの，多ビットの加減乗算が可能となっている。また，同様の性質を持つ格子暗号と比較すると鍵サイズが短いという特長がある。本稿ではアルゴリズムの概要と安全性仮定の妥当性に関する計算機実験結果を示す。