暗号解折手法の計算量理論とよる改良とそれに基づく暗号方式

暗号の安全性に関する精密な解析手法に関しては、昨年度までのコーグルグラフから離れて一般のグラフを対象とした同型性に関する研究を行った。暗号の効率に関する精密な解析手法に関しては、NP-困難な問題に対して、ヒューリスティックスの理論的な解析、低指数関数計算量アルゴリズムの開発、構造的な計算量解析を行った。さらに、量子質問計算量の上下界の解析、量子計算量理論に基づく暗号系設計も行った。具体的暗号方式に関しては、格子暗号の複数ビット化に関する研究を行った。ここでは、よく知られている1ビット格子暗号を対象に、共通の手法を導入し、公開鍵・秘密鍵・暗号文空間のサイズを変えることなく平文空間を複数ビット化した。具体的には、セキュリティパラメータをnとした際に、平文のビット数を0(log n)とすることができた。また、複数ビット化した格子暗号も、元の1ビット格子暗号と同様に安全性を証明することができた。その際、格子暗号中で使われているガウス分布と安全性の基となる格子問題の解析を行い、平文のビット数・復号エラーの確率と安全性の基となる格子問題の間にトレードオフがあることが分かった。また我々は、擬似準同型性、という概念を導入した。通常の暗号の準同型性は、2つの暗号文の和または積が暗号文になるという性質である。一方、擬似準同型性は、2つの暗号文の和が暗号文にはなるとは限らないが,無視できる確率を除いて正しく復号できるという性質である。複数ビット化した格子暗号は、ガウス分布の再生性により擬似準同型性をもつ。ただし、復号エラーを抑えるために、和の回数はある程度制限される。さらに、先と同様の手法により、その方式の安全性も証明した。

暗号の安全性に関する精密な解析手法に関しては、昨年度までのコーグルグラフから離れて一般のグラフを対象とした同型性に関する研究を行った。暗号の効率に関する精密な解析手法に関しては、NP-困難な問題に対して、ヒューリスティックスの理論的な解析、低指数関数計算量アルゴリズムの開発、構造的な計算量解析を行った。さらに、量子質問計算量の上下界の解析、量子計算量理論に基づく暗号系設計も行った。具体的暗号方式に関しては、格子暗号の複数ビット化に関する研究を行った。ここでは、よく知られている1ビット格子暗号を対象に、共通の手法を導入し、公開鍵・秘密鍵・暗号文空間のサイズを変えることなく平文空間を複数ビット化した。具体的には、セキュリティパラメータをnとした際に、平文のビット数を0(log n)とすることができた。また、複数ビット化した格子暗号も、元の1ビット格子暗号と同様に安全性を証明することができた。その際、格子暗号中で使われているガウス分布と安全性の基となる格子問題の解析を行い、平文のビット数・復号エラーの確率と安全性の基となる格子問題の間にトレードオフがあることが分かった。また我々は、擬似準同型性、という概念を導入した。通常の暗号の準同型性は、2つの暗号文の和または積が暗号文になるという性質である。一方、擬似準同型性は、2つの暗号文の和が暗号文にはなるとは限らないが,無視できる確率を除いて正しく復号できるという性質である。複数ビット化した格子暗号は、ガウス分布の再生性により擬似準同型性をもつ。ただし、復号エラーを抑えるために、和の回数はある程度制限される。さらに、先と同様の手法により、その方式の安全性も証明した。