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

基于计算复杂度理论的密码破译方法及其密码系统的改进

基本信息

批准号：
16092206
负责人：
田中圭介
金额：
$ 14.46万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

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

关于密码学安全性相关的精确分析方法，我们放弃了直到去年才研究的Kogl图，而是针对一般图进行了同构研究。关于密码效率的精确分析方法，我们进行了启发式理论分析、低指数复杂度算法的开发以及NP难题的结构计算复杂度分析。此外，我们分析了量子查询复杂度的上下界，并设计了基于量子复杂度理论的密码系统。对于具体的密码学方法，我们进行了多比特格密码学的研究。这里，我们介绍了众所周知的1位格密码的通用方法，在不改变公钥、私钥和密文空间大小的情况下，将明文空间转换为多个位。具体地，当安全参数为n时，可以将明文比特数设置为0(log n)。此外，多位格密码能够证明与原始1位格密码相同的安全性。当时我们分析了格加密中使用的高斯分布和作为安全基础的格问题，并在明文位数、解码错误概率和作为基础的格问题之间进行了权衡事实证明是有的。我们还引入了伪同态的概念。普通密码学中的同态是指密文是两个密文的和或乘积的性质。另一方面，伪同态是这样一种性质：尽管两个密文之和不一定产生密文，但除非概率可以忽略不计，否则它可以被正确解密。由于高斯分布的再现性，多位格密码具有伪同态。然而，为了抑制解码错误，对求和的次数进行了一定程度的限制。此外，使用与之前相同的方法，我们也证明了该方法的安全性。