格子に基づく最悪時/平均時の関係を持つ電子署名および認証方式の構成

研究計画に基づき格子を利用した認証方式および署名方式を構成した。また、これまでに得られた知見を元に、認証方式の構成、既存の暗号方式の改良、新しい暗号方式の提案を行った。これらは、量子計算機であっても困難であると考えられている問題に基づいており、高い安全性を期待できる方式である。各研究の具体的内容は以下である。1.昨年度構成した格子問題に基づく認証用プロトコルの応用を行った。NTRUと呼ばれる多項式を用いた暗号方式がある。これと、先の認証用プロトコルの類似点を用いて、NTRUに適したゼロ知識証明プロトコルを提案した。また、NTRU暗号の困難性に安全性の根拠をおく認証方式を提案した。今までNTRUに基づいた認証方式は無かった。2.昨年度に引き続き、イデアル格子に基づく暗号方式の研究を行った。電子署名、認証方式に引き続き、公開鍵暗号方式、IDベース暗号方式を構成し、その安全性を証明した。これにより既存の格子暗号の鍵サイズや計算効率を上げることができる。3.代理人再暗号化と呼ばれる暗号方式がある。代理人は変換鍵を所持している場合、暗号文の中身を知ることなく、ある受信者用の暗号文を別の受信者用の暗号文に変換できる。2005年に提案されたRegev暗号に着目し、新たなアルゴリズムを加えることで、代理人再暗号化方式を構成した。既存の代理人再暗号化方式は全て離散対数問題と呼ばれる数論的な問題に基づいている。よって、今回,初めて組合わせ系の問題に基づいて代理人再暗号化方式を構成したことになる。

研究計画に基づき格子を利用した認証方式および署名方式を構成した。また、これまでに得られた知見を元に、認証方式の構成、既存の暗号方式の改良、新しい暗号方式の提案を行った。これらは、量子計算機であっても困難であると考えられている問題に基づいており、高い安全性を期待できる方式である。各研究の具体的内容は以下である。1.昨年度構成した格子問題に基づく認証用プロトコルの応用を行った。NTRUと呼ばれる多項式を用いた暗号方式がある。これと、先の認証用プロトコルの類似点を用いて、NTRUに適したゼロ知識証明プロトコルを提案した。また、NTRU暗号の困難性に安全性の根拠をおく認証方式を提案した。今までNTRUに基づいた認証方式は無かった。2.昨年度に引き続き、イデアル格子に基づく暗号方式の研究を行った。電子署名、認証方式に引き続き、公開鍵暗号方式、IDベース暗号方式を構成し、その安全性を証明した。これにより既存の格子暗号の鍵サイズや計算効率を上げることができる。3.代理人再暗号化と呼ばれる暗号方式がある。代理人は変換鍵を所持している場合、暗号文の中身を知ることなく、ある受信者用の暗号文を別の受信者用の暗号文に変換できる。2005年に提案されたRegev暗号に着目し、新たなアルゴリズムを加えることで、代理人再暗号化方式を構成した。既存の代理人再暗号化方式は全て離散対数問題と呼ばれる数論的な問題に基づいている。よって、今回,初めて組合わせ系の問題に基づいて代理人再暗号化方式を構成したことになる。