(57)【要約】【課題】ＧＧＨ暗号において、ユークリッドノルムを大きく、かつ、復号誤りが十分に低くなるようにエラーベクトルを設定する技術を提供すること。【解決手段】送信側装置１１０の乱数生成部１１９は、０の値から離れると、出現確率が低くなるように乱数の値を生成し、暗号処理部１１８は、乱数生成部１１９が生成した乱数の値を要素値とするエラーベクトルを生成し、ＧＧＨ暗号における暗号文を生成する。【選択図】図２
2011002810.tif 000002
【特許請求の範囲】
【請求項１】
ＧＧＨ暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置であって、
予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、
前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、
を行う制御部を備える
ことを特徴とする暗号化装置。
【請求項２】
請求項１に記載の暗号化装置であって、
前記制御部は、
前記乱数生成処理として、予め設定された平均の値及び分散の値で特定される確率分布に沿うように、前記乱数の値を生成する
ことを特徴とする暗号化装置。
【請求項３】
請求項２に記載の暗号化装置であって、
前記制御部は、
前記乱数生成処理で生成された乱数の値から算出される平均の値が、予め設定された平均の値に対して予め定められた閾値の範囲内となり、かつ、前記乱数生成処理で生成された乱数の値から算出される分散の値が、予め設定された分散の値に対して予め定められた閾値の範囲内となるように、前記乱数の値を生成する
ことを特徴とする暗号化装置。
【請求項４】
請求項１から３の何れか一項に記載の暗号化装置であって、
前記制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルを前記復号化装置に送信する処理と、を行うことで、
前記復号化装置において、前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、前記暗号化装置から送られてきたエラーベクトルと比較することで、送信元の検証を行うことができるようにしたこと、
を特徴とする暗号化装置。
【請求項５】
請求項１から３の何れか一項に記載の暗号化装置であって、
前記制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルのハッシュ値を前記復号化装置に送信する処理と、を行うことで、
前記復号化装置において、前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、算出したエラーベクトルのハッシュ値を算出する処理と、前記暗号化装置から送られてきたエラーベクトルのハッシュ値と比較することで、送信元の検証を行うことができるようにしたこと、
を特徴とする暗号化装置。
【請求項６】
コンピュータを、ＧＧＨ暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置として機能させるプログラムであって、
前記コンピュータを、
予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、
前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、
を行う制御手段として機能させる
ことを特徴とするプログラム。
【請求項７】
請求項６に記載のプログラムであって、
前記制御手段に、
前記乱数生成処理として、予め設定された平均の値及び分散の値で特定される確率分布に沿うように、前記乱数の値を生成させる
ことを特徴とするプログラム。
【請求項８】
請求項７に記載のプログラムであって、
前記制御手段に、
前記乱数生成処理で生成された乱数の値から算出される平均の値が、予め設定された平均の値に対して予め定められた閾値の範囲内となり、かつ、前記乱数生成処理で生成された乱数の値から算出される分散の値が、予め設定された分散の値に対して予め定められた閾値の範囲内となるように、前記乱数の値を生成させる
ことを特徴とするプログラム。
【請求項９】
コンピュータを、ＧＧＨ暗号における鍵情報を用いて、暗号文を復号する復号化装置として機能させるプログラムであって、
前記コンピュータを、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出する処理と、
前記暗号化装置から送られてきたエラーベクトルと比較することで、送信元を検証する処理と、を行う制御手段として機能させる
ことを特徴とするプログラム。
【請求項１０】
コンピュータを、ＧＧＨ暗号における鍵情報を用いて、暗号文を復号する復号化装置として機能させるプログラムであって、
前記コンピュータを、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、算出したエラーベクトルのハッシュ値を算出する処理と、
前記暗号化装置から送られてきたエラーベクトルのハッシュ値と比較することで、送信元の検証を行う処理と、を行う制御手段として機能させる
ことを特徴とするプログラム。
【請求項１１】
ＧＧＨ暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置と、ＧＧＨ暗号における鍵情報を用いて、前記暗号文を復号する復号化装置と、を備える暗号システムであって、
前記暗号化装置は、
予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、
前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、
を行う制御部を備える
ことを特徴とする暗号システム。
【請求項１２】
請求項１１に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記乱数生成処理として、予め設定された平均の値及び分散の値で特定される確率分布に沿うように、前記乱数の値を生成する
ことを特徴とする暗号システム。
【請求項１３】
請求項１２に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記乱数生成処理で生成された乱数の値から算出される平均の値が、予め設定された平均の値に対して予め定められた閾値の範囲内となり、かつ、前記乱数生成処理で生成された乱数の値から算出される分散の値が、予め設定された分散の値に対して予め定められた閾値の範囲内となるように、前記乱数の値を生成する
ことを特徴とする暗号システム。
【請求項１４】
請求項１１から１３の何れか一項に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルを前記復号化装置に送信する処理と、を行い、
前記復号化装置は、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出する処理と、前記暗号化装置から送られてきたエラーベクトルと比較することで、送信元を検証する処理と、を行う制御部を備える
ことを特徴とする暗号システム。
【請求項１５】
請求項１１から１３の何れか一項に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルのハッシュ値を前記復号化装置に送信する処理と、を行い、
前記復号化装置は、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、算出したエラーベクトルのハッシュ値を算出する処理と、前記暗号化装置から送られてきたエラーベクトルのハッシュ値と比較することで、送信元の検証を行う処理と、を行う制御部を備える
ことを特徴とする暗号システム。
【請求項１６】
請求項１４または１５いずれか一に記載の暗号システムであって、
前記復号化装置は、ＧＧＨ暗号における鍵情報に、前記暗号文を掛け合わせて、前記復号文を生成し、
前記復号化装置の前記制御部は、
前記暗号文から前記エラーベクトルを特定する誤差テーブルを作成する処理と、
前記鍵情報と前記誤差テーブルに格納された値とを掛け合わせて前記エラーベクトルを特定する処理と、を行う
ことを特徴とする暗号システム。
【請求項１７】
ＧＧＨ暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置が行う暗号化方法であって、
前記暗号化装置の制御部が、予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理を行う過程と、
前記暗号化装置の制御部が、前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理を行う過程と、
を備える
ことを特徴とする暗号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＧＧＨ暗号を用いてデータを暗号化する技術に関する。
【背景技術】
【０００２】
公開鍵暗号の安全性は、数学的な問題の困難性に安全性の根拠をおくのがほとんどである。例えば、ＲＳＡ暗号は素因数分解問題の困難性、楕円曲線暗号は楕円曲線上の離散対数問題の困難性、を安全性の根拠としている。
【０００３】
一方、これらの公開鍵暗号は、現在の標準的な計算機（Ｔｕｒｉｎｇ機械)に対して安全性を検証しているが、近年の量子計算機上の解読アルゴリズムの発展により、これまで解読困難であった数学的な問題が効率的に解読され、既存の公開鍵暗号が破られる危険性がある。
【０００４】
このため、量子計算機に対しても解読困難であるよう、１９９７年に近似ベクトル問題と呼ばれる一種の格子問題の困難性を安全性の根拠とする公開鍵暗号アルゴリズム（以降、ＧＧＨ暗号と呼ぶ）がGoldreichらによって提案された（非特許文献１を参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Oded Goldreich, Shafi Goldwasser, and Shai Halevi.  “Public−Key Cryptosystems from Lattice Reduction Problems”. In Advances in Cryptology（Crypto'97）, volume 1294 of Lecture Notes in Computer Science, pages 112-131（1997).
【非特許文献２】Phong Q. Nguyen.  “Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto'97”. In Advances in Cryptology（Crypto'99), volume 1666 of Lecture Notes in Computer Science, pages 288--304（1999).
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ｎ個の線形独立なベクトルｂ１，・・・，ｂｎ、
【数１】
2011002810.tif 000003
をもつ行列Ｂ、
【数２】
2011002810.tif 000004
が張る格子Ｌ（Ｂ）は、
【数３】
2011002810.tif 000005
で表される。
【０００７】
このとき、行列Ｂによって生成される格子Ｌの行列式はｄｅｔ（Ｌ（Ｂ））＝ｄｅｔ（Ｂ）の関係式が成り立つ。また、格子Ｌがｎ次元のとき、その最短ベクトルの長さは、
【数４】
2011002810.tif 000006
と推定することができる。
【０００８】
これに対して、最短ベクトル問題を効率的に（多項式時間で）解くアルゴリズムは知られていないものの、その近似解は効率的に（多項式時間で）ＬＬＬアルゴリズムで解読可能である。
【０００９】
このＬＬＬアルゴリズムを用い、
【数５】
2011002810.tif 000007
を満たすベクトルｖが見つかれば、ｖは（近似解ではなく）最短ベクトルそのものであると期待できる。
【００１０】
ただし、
【数６】
2011002810.tif 000008
はベクトルｖのユークリッドノルム（各要素値の自乗の和の平方根）を指す。即ち、ｖの要素値をｖｉ
【数７】
2011002810.tif 000009
とするとき、次の（８）式が成り立つ。
【数８】
2011002810.tif 000010
【００１１】
ここで、ｖに対する格子Ｌの期待比（expected gap）は、比率
【数９】
2011002810.tif 000011
で表せる。この期待比が大きいほど、ＬＬＬアルゴリズムが最短ベクトルを見つけやすいことが知られている。
【００１２】
一方、ＧＧＨ暗号が安全性の根拠とする問題を、近似ベクトル問題から上記の最短ベクトル問題に帰着させる方法が知られている。ＧＧＨ暗号における公開鍵Ｂと暗号文ｃから、新たに（ｎ＋１）行（ｎ＋１）列の行列Ｂ’を生成する。
【数１０】
2011002810.tif 000012
【００１３】
暗号文ｃに最も近い格子点が平文ｍの場合、Ｌ（Ｂ’)の最短ベクトルは（ｃ−Ｂｍ,１)であると期待できる。従って、Ｌ（Ｂ’)の最短ベクトルが計算できれば、平文ｍが得られる。一般に、（ｃ−Ｂｍ,１)に対するＬの期待比（expected gap)は、ｃ−Ｂｍのユークリッドノルムが小さいほど大きくなる。
【００１４】
ＧＧＨ暗号では、エラーベクトルｅのユークリッドノルムが最大でも
【数１１】
2011002810.tif 000013
（全ての要素値がｓまたは−ｓの場合）である。復号誤りを十分に低くするためにはｓの値も小さくする必要があるため、結果的にエラーベクトルｅのユークリッドノルムが小さく、ｖに対する格子Ｌの期待比が大きくなってしまい、ＧＧＨ暗号には上記の攻撃は適用可能である。
【課題を解決するための手段】
【００１５】
本明細書では、ＧＧＨ暗号において、ユークリッドノルムを大きく、かつ、復号誤りが十分に低くなるようにエラーベクトルを設定する技術が開示される。
【００１６】
また、ユークリッドノルムの大きなエラーベクトルを用いたＧＧＨ暗号において、暗号文から正しい平文を復号化する技術が開示される。
【００１７】
開示する一つの例によれば、予め定められた値から離れると、出現確率が低くなるように生成された乱数の値を要素値とするエラーベクトルを用いてＧＧＨ暗号化を施す。
【００１８】
また、開示する他の一つの例によれば、エラーベクトルによる誤り箇所を検出し、特定された箇所における正しい値の候補を含んで構成されるテーブルを用い、ＧＧＨ復号化を施す。
【００１９】
例えば、ＧＧＨ暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置であって、予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、を行う制御部を備える暗号化装置が開示される。
【発明の効果】
【００２０】
本明細書が提供する技術によれば、ＧＧＨ暗号において、ユークリッドノルムを大きく、かつ、復号誤りが十分に低くなるようにエラーベクトルを設定することができる。また、ユークリッドノルムの大きなエラーベクトルを用いたＧＧＨ暗号において、暗号文から正しい平文を復号化することが可能になる。
【図面の簡単な説明】
【００２１】
【図１】暗号システムの概略を例示する図。
【図２】送信側装置の機能概略を例示する図。
【図３】正規分布の概略を例示する図。
【図４】コンピュータの概略構成を例示する図。
【図５】乱数生成器の機能の概略を例示する図。
【図６】受信側装置の機能の概略を例示する図。
【図７】送信側装置と受信側装置とが、送信文を共有する処理を例示するシーケンス図。
【図８】エラーベクトルｅの生成処理を例示するフローチャート。
【図９】乱数の値を生成する処理を例示するフローチャート。
【図１０】送信側装置と受信側装置とが、共通鍵を用いて送信文を共有する処理を例示するシーケンス図。
【図１１】送信側装置の機能の概略を例示する図。
【図１２】受信側装置の機能の概略を例示する図。
【図１３】暗号文の送信元を証明する処理を例示するシーケンス図。
【図１４】エラーベクトルｅの生成処理を例示するフローチャート。
【図１５】暗号文を復号化する処理を例示するフローチャート。
【図１６】暗号文の復号化処理において用いるテーブルの概略を例示する図。
【発明を実施するための形態】
【００２２】
図１は、本発明の第一の実施形態である暗号システム１００の概略図である。図示するように、暗号システム１００は、送信側装置１１０と、受信側装置１３０と、を備え、これらは、ネットワーク１５０を介して相互に情報を送受信することができるようにされている。
【００２３】
ここで、本実施形態における送信側装置１１０は、ＧＧＨ暗号における鍵情報（公開鍵）を用いて暗号化を行う暗号化装置として機能し、受信側装置１３０は、ＧＧＨ暗号における鍵情報（秘密鍵）を用いて復号化を行う復号化装置として機能する。
【００２４】
図２は、送信側装置１１０の機能概略図である。図示するように、送信側装置１１０は、記憶部１１１と、制御部１１６と、入力部１２１と、出力部１２２と、通信部１２３と、を備える。
【００２５】
記憶部１１１は、送信文記憶領域１１２と、公開鍵記憶領域１１３と、一時情報記憶領域１１４と、を備える。
【００２６】
送信文記憶領域１１２には、受信側装置１３０に送信する文書データである送信文を特定する情報が記憶される。
【００２７】
公開鍵記憶領域１１３には、公開鍵を特定する情報が記憶される。ここで、本実施形態においては、受信側装置１３０より送信されてきたＧＧＨ暗号における公開鍵Ｂを特定する情報が記憶される。
【００２８】
一時情報記憶領域１１４には、制御部１１６での処理で必要となる情報が記憶される。
【００２９】
制御部１１６は、全体制御部１１７と、暗号処理部１１８と、乱数生成部１１９と、を備える。
【００３０】
全体制御部１１７は、送信側装置１１０での処理の全体を制御する。
【００３１】
例えば、本実施形態においては、全体制御部１１７は、入力部１２１を介して，入力を受け付けた送信文を送信文記憶領域１１２に記憶する処理を行う。
【００３２】
また、全体制御部１１７は、受信側装置１３０より、通信部１２３を介して受信した公開鍵を公開鍵記憶領域１１３に記憶する処理を行う。
【００３３】
さらに、全体制御部１１７は、暗号処理部１１８で生成された暗号文を、通信部１２３を介して、受信側装置１１０に送信する処理を行う。
【００３４】
加えて、全体制御部１１７は、入力部１２１を介して、平均と分散の値の入力を受け付けて、一時情報記憶領域１１４に記憶する処理を行う。
【００３５】
暗号処理部１１８は、ＧＧＨ暗号における暗号化処理を行う。
【００３６】
例えば、本実施形態においては、送信文記憶領域１１２に記憶されている文書データ
【数１２】
2011002810.tif 000014
から暗号文
【数１３】
2011002810.tif 000015
を生成する。暗号文ｃは、下記の（１５）式に示すように、格子点Ｂｍにエラーベクトル
【数１４】
2011002810.tif 000016
を加えた値を有する。
【数１５】
2011002810.tif 000017
【００３７】
ただし、エラーベクトルｅは、乱数生成部１１９で生成された乱数の値を要素値とする。なお、エラーベクトルｅの要素値の割り振りが偏ると、復号化時の誤りが発生したり、安全性が失われたりする恐れがある。そのため、平均値を抑えるように、各要素値を調整する。
【００３８】
乱数生成部１１９は、暗号処理部１１８で暗号化を行う際に必要となるエラーベクトルｅの要素値となる乱数の値を生成する。
【００３９】
ここで、乱数生成部１１９で生成する乱数の値は、平均が予め定められた閾値の範囲内であり、乱数の値が平均から離れると、当該乱数の値の出現確率が小さくなるようになっている。
【００４０】
本実施形態においては、乱数生成部１１９で生成する乱数の値は、例えば、図３（正規分布の概略図）に示すような、正規分布に沿うように算出される。
【００４１】
正規分布では、確率変数（乱数の値）ｘの確率密度関数ｆ（ｘ）が、下記の（１６）式で与えられる。
【数１６】
2011002810.tif 000018
【００４２】
ここで、πは円周率、exp（a)はeaを指す。また、uとｓは正規分布の平均（中心の位置）と分散（ばらつき）を規定するパラメータである。なお、本実施形態において、uの値が予め定められた敷値の範囲内にあり、ｓの値が設定された分散の値から予め定められた敷値の範囲内にある場合には、乱数の値は正規分布に沿っているものとする。
【００４３】
また、図３においては、（１）は、ｕ＝０、σ＝１とする正規分布であり、（２）は、ｕ＝０、σ＝３とする正規分布であり、（３）は、ｕ＝０、σ＝１０とする正規分布である。
【００４４】
このように、平均ｕの値を小さく、分散ｓの値を大きくした正規分布を用いて算出された乱数の値を要素値とすることで、小さい平均値で、かつ、ユークリッドノルムが大きいエラーベクトルを生成できる。
【００４５】
なお、平均ｕの値は「０」だけでなく、任意の値を設定することができる。
【００４６】
入力部１２１は、情報の入力を受け付ける。
【００４７】
出力部１２２は、情報を出力する。
【００４８】
通信部１２３は、ネットワーク１５０を介した情報の送受信を行う。
【００４９】
以上に記載した送信側装置１１０は、例えば、図４（コンピュータ８００の概略図）に示すような、ＣＰＵ（Central Processing Unit）８０１と、メモリ８０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置８０３と、ＣＤ（Compact Disk）やＤＶＤ（Digital Versatile Disk）等の可搬性を有する記憶媒体８０４に対して情報を読み書きする読書装置８０５と、キーボードやマウスなどの入力装置８０６と、ディスプレイなどの出力装置８０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置８０８と、これらを連結するシステムバスなどの内部通信線（システムバスという）８０９と、を備えた一般的なコンピュータ８００で実現できる。
【００５０】
例えば、記憶部１１１は、ＣＰＵ８０１がメモリ８０２又は外部記憶装置８０３を利用することにより実現可能であり、制御部１１６と制御部１１６に含まれる各処理部は、外部記憶装置８０３に記憶されている所定のプログラムをメモリ８０２にロードしてＣＰＵ８０１で実行することで実現可能であり、入力部１２１は、ＣＰＵ８０１が入力装置８０６を利用することで実現可能であり、出力部１２２は、ＣＰＵ８０１が出力装置８０７を利用することで実現可能であり、通信部１２３は、ＣＰＵ８０１が通信装置８０８を利用することで実現可能である。
【００５１】
この所定のプログラムは、読書装置８０５を介して記憶媒体８０４から、あるいは、通信装置８０８を介してネットワークから、外部記憶装置８０３にダウンロードされ、それから、メモリ８０２上にロードされてＣＰＵ８０１により実行されるようにしてもよい。また、読書装置８０５を介して記憶媒体８０４から、あるいは、通信装置８０８を介してネットワーク１５０から、メモリ８０２上に直接ロードされ、ＣＰＵ８０１により実行されるようにしてもよい。
【００５２】
但し、本実施形態の乱数生成部１１９については、コンピュータシステム上にソフトウェア的に実現されるものに限定されない。例えば、ＡＳＩＣ（Application Specific Integrated Circuits）、ＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実現されるもの、例えば、図５（乱数生成器９００の概略図）に示すような乱数生成器９００で構成することも可能である。
【００５３】
図示するように、乱数生成器９００は、プログラム用メモリ９０１と、制御回路９０２と、レジスタ９０３と、アキュムレータ９０４と、一時データ用メモリ９０５と、クロック発生器９０６と、Ｉ／Ｆ９０７と、を備える。
【００５４】
プログラム用メモリ９０１には、制御回路９０２で正規分布に沿った乱数の値を生成するための乱数生成用プログラムが記憶されている。
【００５５】
制御回路９０２は、プログラム用メモリ９０１より読み込んだ乱数生成用プログラムを実行して、乱数の値を生成し、アキュムレータ９０４に出力する。出力された乱数の値は、Ｉ／Ｆ９０７を介して、図４に示すシステムバス８０９よりＣＰＵ８０１が取得する。
【００５６】
図６は、受信側装置１３０の概略図である。図示するように、受信側装置１３０は、記憶部１３１と、制御部１３６と、入力部１４１と、出力部１４２と、通信部１４３と、を備える。
【００５７】
記憶部１３１は、秘密鍵記憶領域１３２と、公開鍵記憶領域１３３と、一時情報記憶領域１３４と、を備える。
【００５８】
秘密鍵記憶領域１３２には、秘密鍵を特定する情報が記憶される。ここで、本実施形態においては、後述する鍵生成部１３８が生成したＧＧＨ暗号における秘密鍵Ｒ及びその逆元Ｒ−１、並びに、ユニモジュラ行列Ｔ及びその逆行列Ｔ−１を特定する情報が記憶される。
【００５９】
公開鍵記憶領域１３３には、公開鍵を特定する情報が記憶される。ここで、本実施形態においては、後述する鍵生成部１３８が生成したＧＧＨ暗号における公開鍵Ｂを特定する情報が記憶される。
【００６０】
一時情報記憶領域１３４には、制御部１３６での処理で必要となる情報が記憶される。
【００６１】
制御部１３６は、全体制御部１３７と、鍵生成部１３８と、復号処理部１３９と、を備える。
【００６２】
全体制御部１３７は、受信側装置１３０での処理の全体を制御する。例えば、本実施形態においては、鍵生成部１３８が生成した公開鍵を特定する情報を、通信部１４３を介して、送信側装置１１０に送信する処理を行う。
【００６３】
鍵生成部１３８は、ＧＧＨ暗号における秘密鍵及び公開鍵を生成し、それぞれ、秘密鍵記憶領域１３２及び公開鍵記憶領域１３３に記憶する処理を行う。
【００６４】
例えば、本実施形態においては、鍵生成部１３８は、
【数１７】
2011002810.tif 000019
但し、
【数１８】
2011002810.tif 000020
である。ｌは任意の整数でよく、ｋは、
【数１９】
2011002810.tif 000021
などの関係式から作成した整数である。
【００６５】
秘密鍵Ｒと公開鍵Ｂはｎ行ｎ列の行列であり、公開鍵Ｂは、秘密鍵Ｒと同じ格子を張る格子基底
【数２０】
2011002810.tif 000022
で、ユニモジュラ行列
【数２１】
2011002810.tif 000023
と秘密鍵Ｒを用いてＢ＝ＲＴから生成する。ただし、ユニモジュラ行列とは、行列式の絶対値が１であるような行列を指す。ここで、公開鍵Ｂから、秘密鍵Ｒが特定されないよう、複数のユニモジュラ行列を生成し、Ｒに複数回それらのユニモジュラ行列を掛け合わせて公開鍵Ｂを生成してもよい。
【００６６】
復号処理部１３９は、送信側装置１１０から送られてきた暗号文から送信文を復号化する。
【００６７】
例えば、本実施形態においては、復号処理部１３９は、ユニモジュラ行列Ｔの逆行列Ｔ−１、秘密鍵Ｒの逆元Ｒ−１、暗号文ｃを、それぞれ掛け合わせ、Ｔ−１[Ｒ−１ｃ]を計算する。
【００６８】
ただし、
【数２２】
2011002810.tif 000024
はベクトルａの全ての要素値の少数点以下を四捨五入した値である。エラーベクトルの各要素値が十分に小さい場合、極めて高い確率で
【数２３】
2011002810.tif 000025
である。従って、次の（２５）式に従い、
【数２４】
2011002810.tif 000026
から平文ｍを復元する。
【数２５】
2011002810.tif 000027
【００６９】
入力部１４１は、情報の入力を受け付ける。
【００７０】
出力部１４２は、情報を出力する。
【００７１】
通信部１４３は、ネットワークを介して情報を送受信する。
【００７２】
以上に記載した受信側装置１３０は、例えば、図４に示すような一般的なコンピュータ８００で実現できる。
【００７３】
例えば、記憶部１３１は、ＣＰＵ８０１がメモリ８０２又は外部記憶装置８０３を利用することにより実現可能であり、制御部１３６と制御部１３６に含まれる各処理部は、外部記憶装置８０３に記憶されている所定のプログラムをメモリ８０２にロードしてＣＰＵ８０１で実行することで実現可能であり、入力部１４１は、ＣＰＵ８０１が入力装置８０６を利用することで実現可能であり、出力部１４２は、ＣＰＵ８０１が出力装置８０７を利用することで実現可能であり、通信部１４３は、ＣＰＵ８０１が通信装置８０８を利用することで実現可能である。
【００７４】
この所定のプログラムは、読書装置８０５を介して記憶媒体８０４から、あるいは、通信装置８０８を介してネットワークから、外部記憶装置８０３にダウンロードされ、それから、メモリ８０２上にロードされてＣＰＵ８０１により実行されるようにしてもよい。また、読書装置８０５を介して記憶媒体８０４から、あるいは、通信装置８０８を介してネットワーク１５０から、メモリ８０２上に直接ロードされ、ＣＰＵ８０１により実行されるようにしてもよい。
【００７５】
図７は、ＧＧＨ暗号における暗号化プロトコルを用いて、送信側装置１１０と受信側装置１３０とが送信文を共有する処理を示すシーケンス図である。
【００７６】
なお、送信文は、暗号化の対象となるデータ全般を指し、例えば、鍵データ、プログラムデータ、動画データ、ドキュメントデータ等が含まれる。
【００７７】
まず、送信側装置１１０の全体制御部１１７は、入力部１２１を介して、暗号文の作成指示の入力を受け付ける（Ｓ１０）。
【００７８】
次に、送信側装置１１０の暗号処理部１１８は、乱数生成部１１９より乱数の値を取得して、エラーベクトルｅを生成する（Ｓ１１）。このステップＳ１１での処理は、図８を用いて詳細に説明する。
【００７９】
そして、送信側装置１１０の暗号処理部１１８は、公開鍵記憶領域１１３に記憶されている公開鍵Ｂ及び送信文記憶領域１１２に記憶されている送信文ｍを取得し、取得した公開鍵Ｂに送信文ｍを掛け合わせ、エラーベクトルｅを足すことにより、（Ｂｍ＋ｅ）の値を有する暗号文ｃを生成する（Ｓ１２）。
【００８０】
次に、送信側装置１１０の全体制御部１１７は、通信部１２３を介して、生成した暗号文ｃを受信側装置１３０に送信する（Ｓ１３）。
【００８１】
受信側装置１３０の全体制御部１３７は、通信部１４３を介して、暗号文ｃを受信する（Ｓ１４）。
【００８２】
そして、受信側装置１３０の全体制御部１３７は、入力部１４１を介して、暗号文ｃの復号化指示の入力と受け付けると（Ｓ１５）、復号処理部１３９に暗号文ｃの復号処理を行わせる（Ｓ１６）。
【００８３】
ここで、復号処理部１３９は、秘密鍵記憶領域１３２に記憶されている秘密鍵Ｒの逆元Ｒ−１及びユニモジュラ行列Ｔの逆行列Ｔ−１を取得し、Ｔ−１[Ｒ−１ｃ]を計算し、暗号文ｃを復号化した復号文ｍ’を取得する。
【００８４】
そして、受信側装置１３０の全体制御部１３７は、復号文ｍ’を一時情報記憶領域１３４に記憶する（Ｓ１７）。
【００８５】
なお、ネットワーク１５０におけるデータ配送の誤りや、暗号化又は復号化プロトコルにおける誤りから、送信文ｍと復号文ｍ’の値が異なるおそれある。そこで、ステップＳ１６の後に、復号文ｍ’の真正性を検査する処理、復号文ｍ’の誤りを訂正する処理、復号文ｍ’の真正性の真正性が認められない場合に、送信側装置１１０に再送を要求する処理、等を追加してもよい。
【００８６】
なお、復号文ｍ’の真正性の検査では、暗号文ｃの一部に格納された、または別に配送されたｍ’またはＲ−１ｃのパリティの比較処理や、ｍ’またはＲ−１ｃのハッシュ値の照合処理を追加しても良い。
【００８７】
さらに、復号文ｍ’の誤り訂正処理では、誤り訂正符号等を利用し、復号文ｍ’の誤りを訂正する処理を追加してもよい。
【００８８】
図８は、送信側装置１１０の暗号処理部１１８におけるエラーベクトルｅの生成処理を示すフローチャートである。
【００８９】
まず、送信側装置１１０の暗号処理部１１８は、乱数生成部１１９に統計処理の設定命令を行う（Ｓ２０）。この設定命令については、入力部１２１を介して予め入力されている、平均ｕの値、分散ｓの値、乱数の値の数、が含まれる。
【００９０】
そして、乱数生成部１１９は、統計処理の設定命令に含まれる平均ｕの値と、分散ｓの値と、乱数の値の数と、を統計処理の設定値として設定する（Ｓ２１）。
【００９１】
そして、暗号処理部１１８は、乱数生成部１１９に開始命令を行い（Ｓ２２）、乱数生成部１１９が乱数の値を生成する（Ｓ２３）。なお、ステップＳ２３での処理については、図９を用いて詳細に説明する。
【００９２】
次に、乱数生成部１１９は、必要な数の乱数の値の生成が終了すると、終了通知を暗号処理部１１８に通知する（Ｓ２４）。
【００９３】
そして、暗号処理部１１８は、生成された乱数の値を一時情報記憶領域１１４より取得して、エラーベクトルの要素値とする（Ｓ２５）。
【００９４】
なお、ステップＳ２５での処理が終了した後、暗号処理部１１８は、必要に応じ、取得した乱数値を変換する。例えば、取得した乱数値が極端に大きいまたは小さい場合、その値を他の値に変換してもよい。この場合でも、入力された平均ｕと分散ｓの値で特定される正規分布に対応した出現回数となるように、他の値を選択すればよい。
【００９５】
例えば、暗号処理部１１８は、閾値に満たない値については、閾値を満たす最小の値から順に、正規分布に対応した出現回数となるように他の値を割り振り、また、閾値を超えた値については、閾値を満たす最大の値から順に、正規分布に対応した出現回数となるように他の値を割り振る等により他の値に変更すればよい。
【００９６】
また、暗号処理部１１８は、取得した乱数値が整数ではない（小数点を含む)場合、小数点第一位以下の切り捨てや切り上げ、または四捨五入により、少数を整数に丸める処理を行ってもよい。
【００９７】
また、暗号処理部１１８は、取得した乱数値が正規分布に対応したものか否かを検査して、乱数値の再生成が必要かを検査するようにしてもよい。そして、再生成をする場合はステップＳ２２に戻り、処理を繰り返すことも可能である。
【００９８】
さらに、暗号処理部１１８は、エラーベクトルの要素値の要素番号を変更したい場合は、要素値の順序の変更処理（シャッフル）を行うことも可能である。
【００９９】
また、乱数生成部１１９が、正規分布とは無関係に、ランダムに固定ビット長（１６０ビット、１２８ビット等）の整数を出力する場合には、乱数生成部１１９が出力した乱数の値から、改めて正規分布に沿った、乱数へ変更する処理を図８の処理フローに追加してもよい。例えば、乱数生成部１１９が出力する乱数または乱数の一部と、ある確率分布に沿った変数への写像から、確率分布に沿った乱数が生成できる。また、同様の手法は、乱数生成部１１９が出力する乱数の値の確率分布が不明な場合にも適用できる。
【０１００】
図９は、送信側装置１１０の乱数生成部１１９が、乱数の値を生成する処理を示すフローチャートである。
【０１０１】
まず、乱数生成部１１９は、暗号処理部１１８より統計処理の設定命令（例えば、平均ｕと分散ｓを指すパラメータ、乱数の値の数等）を受信すると（Ｓ３０）、乱数生成部１１９は、これらのパラメータ等を統計処理の設定値として設定する。
【０１０２】
次に、乱数生成部１１９は、暗号処理部１１８より開始命令を受けると（Ｓ３２）、設定命令で特定された数の乱数の値が、設定命令に含まれているパラメータで特定される正規分布に従うように、乱数の値を生成する（Ｓ３２）。
【０１０３】
ここで、乱数生成部１１９の乱数の値の生成は、設定命令に含まれているパラメータで特定される正規分布に従うように予め記憶部１１１に記憶されている乱数の値を抽出するようにしてもよく、また、乱数生成部１１９でランダムに抽出した乱数の値が、必要な乱数の値の数に対して、設定命令に含まれているパラメータで特定される正規分布で特定される出現回数となるように、当該乱数の値を抽出するようにしてもよい。
【０１０４】
そして、乱数生成部１１９は、生成した乱数の値を一時情報記憶領域１１４に記憶する（Ｓ３３）。
【０１０５】
ここで、出力された乱数の値は、一定の確率で偏る可能性がある（例えば、極めて低い確率であるが、全ての値が０である、など）ので、乱数生成部１１９は、出力された乱数の値が、設定命令に含まれているパラメータで特定される正規分布に沿うか否かを検査して（Ｓ３４）、沿わない場合には（ステップＳ３４でＹｅｓ）ステップＳ３２に戻り処理を繰り返す。
【０１０６】
設定命令に含まれているパラメータで特定される正規分布に沿うか否かについては、例えば、乱数生成部１１９は、一時情報記憶領域１１４に記憶された乱数の値の平均値が設定命令に含まれているパラメータである平均値ｕに対して予め定められた閾値の範囲内にあり、かつ、一時情報記憶領域１１４に記憶された乱数の値の分散の値が設定命令に含まれているパラメータである分散ｓに対して予め定められた閾値の範囲内にある場合には、設定命令に含まれているパラメータで特定される正規分布に沿うと判断する。
【０１０７】
なお、以上に記載した実施形態においては、図７に示すシーケンス図で、ＧＧＨ暗号における暗号化プロトコルを用いて送信文を暗号化して送信側装置１１０から受信側装置１３０に送信する処理を示したが、このような態様に限定されず、例えば、図１０に示すように、ＧＧＨ暗号における暗号化プロトコルを用い、送信側装置１１０と受信側装置１３０とが、まず共通鍵を共有し、次に共通鍵暗号における暗号プロトコルを用い、送信文を共有するようにしてもよい。
【０１０８】
例えば、図１０において、送信側装置１１０では、図７のステップＳ１０からＳ１２までの処理と同様の処理を、暗号化の対象を共通鍵として実行し、暗号文ｃを生成して、送信側装置１１０の全体制御部１１７は、生成した暗号文ｃを受信側装置１３０に送信する（Ｓ４０）。
【０１０９】
そして、受信側装置１３０は、図７のステップＳ１４からＳ１６まで処理と同様の処理を、受信した暗号文ｃに対して実行し、復号された共通鍵を記憶部１３１に記憶する（Ｓ４１）。なお、受信側装置１３０が無事に共通鍵を復号化できた場合、受信側装置１３０の全体制御部１３７は、通信部１４３を介して、送信側装置１１０に受信通知を送付しても良い。また、復号化できなかった場合は、受信側装置１３０の全体制御部１３７は、通信部１４３を介して、送信側装置１１０に再送処理を要求しても良い。このような再送処理の要求を受信した送信側装置１１０では、ステップＳ４０に戻り処理を繰り返す。
【０１１０】
次に、送信側装置１１０の暗号処理部１１８は、共通鍵を用い、共通鍵暗号で送信用データを暗号化することで暗号化データを生成する（Ｓ４２）。共通鍵暗号は、ブロック暗号でも、ストリーム暗号でも良い。
【０１１１】
そして、送信側装置１１０は、生成した暗号化データを、通信部１２３を介して、受信側装置１３０に送信する（Ｓ４３）。
【０１１２】
次に、受信側装置１３０は、通信部１４３を介して、暗号化データを受信する（Ｓ４４）。
【０１１３】
そして、受信側装置１３０は、受信した暗号化データを、ステップＳ４１で記憶部１３１に記憶した共通鍵で復号化して復号化データを生成し（Ｓ４５）、復号化データを記憶部１３１に記憶する（Ｓ４６）。
【０１１４】
以上に記載した実施形態においては、正規分布に沿うように乱数の値を生成したが、このような態様に限定されず、正規分布以外のガンマ分布、指数分布などの他の確率分布にも適用可能である。
【０１１５】
例えば、確率密度関数f（x)が以下の式で与えられるガンマ分布を用いてよい。
【数２６】
2011002810.tif 000028
【０１１６】
ここで、α＞０かつβは共に定数である。
【０１１７】
また、以上に記載した実施形態においては、乱数生成部１１９が生成した乱数の値でエラーベクトルを生成し、ＧＧＨ暗号に適用し、暗号化プロトコルや鍵配送プロトコルなどの実現方法を示した。しかし、本手法は、ＧＧＨ暗号に限定だけでなく、エラーベクトルや乱数を用いる他の公開鍵暗号（例えば、ＧＧＨ暗号の特殊な実装形式であるＰＪＨ暗号など）にも適用できる。
【０１１８】
さらに、以上に記載した実施形態においては、乱数生成部１１９が生成したエラーベクトルをｎ行ｎ列の秘密鍵と公開鍵を用いた公開鍵暗号へ適用した。しかし、本手法を適用する秘密鍵と公開鍵は、行と列の数が同じである必要はなく、ｍ行ｎ列またはｎ行ｍ列からなる、秘密鍵または公開鍵を用いた公開鍵暗号にも適用できる（ただし、ｍ≠ｎとする）。
【０１１９】
また、以上に記載した実施形態においては、公開鍵暗号への適用を記載した。しかし、本手法は共通鍵暗号や、グループ署名、秘密分散等の他の暗号系にも同様に適用できる。
【０１２０】
次に、本発明の第二の実施形態について説明する。ここで、第二の実施形態においては、第一の実施形態と比較して、送信側装置２１０及び受信側装置２３０が異なっているため、以下、これらの異なっている部分に関連する事項について説明する。
【０１２１】
なお、第二の実施形態においては、エラーベクトルを利用した暗号システムを用い、エラーベクトルの一意性から、暗号文の送付元を証明する技術を提供する。
【０１２２】
図１１は、第二の実施形態における送信側装置２１０の概略図である。図示するように、送信側装置２１０は、記憶部２１１と、制御部２１６と、入力部１２１と、出力部１２２と、通信部１２３と、を備え、第一の実施形態と比較して、記憶部２１１及び制御部２１６が異なっているため、以下、これらについて説明する。
【０１２３】
記憶部２１１は、送信文記憶領域１１２と、公開鍵記憶領域１１３と、一時情報記憶領域１１４と、エラーベクトル記憶領域２２４と、を備え、第一の実施形態と比較して、エラーベクトル記憶領域２２４が異なっているため、以下、エラーベクトル記憶領域２２４について説明する。
【０１２４】
エラーベクトル記憶領域２２４には、暗号処理部１１８で生成されたエラーベクトルを特定する情報が格納される。
【０１２５】
制御部２１６は、全体制御部２１７と、暗号処理部１１８と、乱数生成部１１９と、関数処理部２２６と、を備え、第一の実施形態と比較して、全体制御部２１７及び関数処理部２２６が異なっているため、以下これらに関連する事項について説明する。
【０１２６】
全体制御部２１７は、送信側装置２１０での処理の全体を制御し、第一の実施形態の全体制御部１１７が行う処理と同様の処理を行うほか、暗号処理部１１８が生成したエラーベクトルをエラーベクトル記憶領域２２４に記憶する処理を行う。
【０１２７】
また、本実施形態における全体制御部２１７は、通信部１２３を介して、関数処理部２２６が生成したハッシュ値を受信側装置１３０に送信する処理を行う。
【０１２８】
関数処理部２２６は、予め定められたハッシュ関数を用いて、ハッシュ値を算出する処理を行う。
【０１２９】
図１２は、受信側装置２３０の概略図である。図示するように、受信側装置２３０は、記憶部２３１と、制御部２３６と、入力部１４１と、出力部１４２と、通信部１４３と、を備え、第一の実施形態と比較して、記憶部２３１及び制御部２３６が異なっているため、以下これらに関連する事項について説明する。
【０１３０】
記憶部２３１は、秘密鍵記憶領域１３２と、公開鍵記憶領域１３３と、一時情報記憶領域１３４と、暗号文記憶領域２４５と、復号文記憶領域２４６と、を備え、第一の実施形態と比較して、暗号文記憶領域２４５及び復号文記憶領域２４６が異なっているため、以下、これらに関連する事項について説明する。
【０１３１】
暗号文記憶領域２４５には、送信側装置２１０から受信した暗号文を特定する情報が記憶される。
【０１３２】
復号文記憶領域２４６には、復号処理部１３９が復号した復号文を特定する情報が記憶される。
【０１３３】
制御部２３６は、全体制御部２３７と、鍵生成部１３８と、復号処理部２３９と、関数処理部２４８と、を備え、第一の実施形態と比較して、全体制御部２３７、復号処理部２３９及び関数処理部２４８が異なっているため、以下これらに関連する事項について説明する。
【０１３４】
全体制御部２３７は、受信側装置２３０での処理の全体を制御し、第一の実施形態と同様の処理を行うほか、送信側装置２１０より受信した暗号文を暗号文記憶領域２４５に記憶する処理を行う。
【０１３５】
また、全体制御部２３７は、復号処理部１３９で復号された復号文を復号文記憶領域２４６に記憶する処理を行う。
【０１３６】
本実施形態における復号処理部２３９は、第一の実施形態における復号処理部１３９と同様の処理を行うほか、公開鍵Ｂと復号文ｍ’を掛け合わせた値と暗号文ｃの差分を計算（ｃ−Ｂｍ’）することにより、エラーベクトルｅ’（＝ｃ−Ｂｍ’）を算出する処理を行う。
【０１３７】
関数処理部２４８は、予め定められたハッシュ関数を用いて、ハッシュ値を算出する処理を行う。
【０１３８】
図１３は、ＧＧＨ暗号における暗号化プロトコルを用い、暗号文の送信元を証明する処理を示すシーケンス図である。
【０１３９】
なお、図１３のシーケンスの前提として、送信側装置２１０は、受信側装置２３０に暗号化した暗号文を既に送信済みであり、暗号文の作成時に利用したエラーベクトルは、送信側装置２１０のエラーベクトル記憶領域２２４に記憶されているものとする。
【０１４０】
また、受信側装置２３０は、送信側装置２１０から送信された暗号文と、暗号文から復号化した復号文と、をそれぞれ暗号文記憶領域２４５及び復号文記憶領域２４６に記憶しているものとする。
【０１４１】
なお、これらの状態は、第一の実施形態で行った処理により実現可能である。
【０１４２】
まず、送信側装置２１０の全体制御部２１７は、入力部１２１を介して、ハッシュ値の送信指示の入力を受け付ける（Ｓ５０）。
【０１４３】
次に、送信側装置２１０の関数処理部２２６は、エラーベクトル記憶領域２２４に記憶されているエラーベクトルを取得し（Ｓ５１）予め定められた暗号学的ハッシュ関数（ＳＨＡ−１やＭＤ５等）により、取得したエラーベクトルのハッシュ値を算出する（Ｓ５２）。
【０１４４】
そして、送信側装置２１０の全体制御部２１７は、関数処理部２２６が算出したハッシュ値を、通信部１２３を介して、受信側装置２３０に送信する（Ｓ５３）。
【０１４５】
次に、受信側装置２３０の全体制御部２３７は、通信部１４３を介して、ハッシュ値を受信し、一時情報記憶領域１３４に記憶する（Ｓ５４）。
【０１４６】
そして、受信側装置２３０の全体制御部２３７が、入力部１４１を介して、暗号文の証明指示の入力を受け付けると（Ｓ５５）、受信側装置２３０の復号処理部２３９は、公開鍵記憶領域１１３に記憶されている公開鍵Ｂ、暗号文記憶領域２４５に記憶されている暗号文ｃ及び復号文記憶領域２４６に記憶されている復号文ｍ’を取得し、公開鍵Ｂと復号文ｍ’を掛け合わせた値と暗号文ｃの差分を計算（ｃ−Ｂｍ’）した値をエラーベクトルｅ’（＝ｃ−Ｂｍ’）とし、一時情報記憶領域１３４に記憶する（Ｓ５６）。
【０１４７】
そして、受信側装置２３０の関数処理部２４８は、エラーベクトルｅ’のハッシュ値を算出して一時情報記憶領域１３４に記憶する（Ｓ５７）。
【０１４８】
そして、受信側装置２３０の全体制御部２３７は、ステップＳ５４で受信したハッシュ値と、ステップＳ５７で算出したハッシュ値と、を比較して、これらが一致する場合には、暗号文の送信元が送信側装置２１０であると判断し、これらが異なる場合には、暗号文の送信元が送信側装置２１０ではないと判断する（Ｓ５８）。
【０１４９】
なお、暗号文の送信元を証明する処理については、図１３での処理に限定されるものではなく、例えば、送信側装置２１０はエラーベクトルのハッシュ値を計算する処理（Ｓ５２）を省き、エラーベクトルそのものを受信側装置２３０に送信するようにしてもよい。
このような場合、受信側装置２３０では、エラーベクトルのハッシュ値に代えてエラーベクトルを受信して（Ｓ５４）、ステップＳ５６で算出されたエラーベクトルｅ’と比較するようにすればよい。このときには、受信側装置２３０に関数処理部２４８は不要となる。
【０１５０】
また、例えば、受信側装置２３０は、エラーベクトルｅ’を先に計算しておいて、後から送られてくるエラーベクトルと比較するようにしてもよい。
【０１５１】
さらに、送信側装置２１０は、エラーベクトルのハッシュ値を計算しておき、エラーベクトルの替わりに、そのハッシュ値を記憶部２１１に格納するようにしてもよい。
【０１５２】
第一の実施形態では、送信側装置と受信側装置がデータの安全に共有する方法を開示したが、第二の実施形態では、受信側装置による、メッセージ送信元の送信側装置の特定を可能にし、なりすましの問題を解決することが可能になる。なお、なりすましとは、例えば、送信者装置がネットワーク経由で受信側装置に送信したメッセージを、異なる別の送信者装置が送信したメッセージのように受信側装置に見せかけることを指す。
【０１５３】
次に、第三の実施形態について説明する。ここで、第三の実施形態においては、第一の実施形態と比較して、送信側装置１１０が異なっているため、以下、これらの異なっている部分に関連する事項について説明する。
【０１５４】
第三の実施形態では、以下の文献などに方法が開示されている不正解読を防ぐよう、エラーベクトルの設定に、二つの確率分布を用いる方法について説明する。
【０１５５】
Phong Q. Nguyen.  “Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto'97”. In Advances in Cryptology（Crypto'99), volume 1666 of Lecture Notes in Computer Science, pages 288--304（1999).
第三の実施形態では、送信側装置３１０は、記憶部３１１と、制御部３１６と、入力部１４１と、出力部１４２と、通信部１４３と、を備えている。以下、第一の実施形態との相違点について説明する。
【０１５６】
記憶部３１１は、送信文記憶領域１１２と、公開鍵記憶領域１１３と、一時情報記憶領域１１４と、パラメータ記憶領域３１５を備え、第一の実施形態と比較して、パラメータ記憶領域３１５が異なっている。
【０１５７】
パラメータ記憶領域３１５には、乱数処理部１１９に与える統計処理の設定命令を特定する情報が記憶される。例えば、平均ｕの値と、乱数の値の数、乱数の値域を指す要素値、分布の数などがこれに当たる。
【０１５８】
制御部３１６は、全体制御部３１７と、暗号処理部１１８と、乱数生成部１１９と、を備え、第一の実施形態と比較して、全体制御部３１７が異なっている。
【０１５９】
全体制御部３１７は、送信側装置３１０での処理の全体を制御し、第一の実施形態の全体制御部１１７が行う処理と同様の処理を行うほか、パラメータ記憶領域３１５に記憶された統計処理に関する情報に従い、乱数生成部１１９が生成した乱数を一時記憶領域１１４に記憶する処理を行う。
【０１６０】
図１４は、ＧＧＨ暗号における暗号化プロトコルにおいて、送信側装置３１０の暗号処理部１１８におけるエラーベクトルeの生成処理を示すフローチャートである。
【０１６１】
図１４に示すＳ１３０１からＳ１３０９の処理フローは、第一の実施形態における図７に示す処理フローのＳ１１の処理を詳細化したものである。任意の正の整数s1、s2において、各要素値{-s1, -（s1-1),・・・s2-1,s2}の集合Ｓと、t＞dである整数t,dにおいて、各要素値{-t, -（t-1), ・・・-（d-1),-d, d, d+1, t-1, t}の集合Ｔを用いて、エラーベクトルｅの要素値を設定する。
【０１６２】
まず、送信側装置３１０の暗号処理部１１８は、集合Ｓと集合Ｔから選択する要素の数を設定する。格子の次元（公開鍵または秘密鍵の次元でもよい）がｎである場合、集合Ｓから選択する要素数aと集合Ｔから選択する要素数ｂの間には、恒等式a + b ＝ nが成り立つ。例えば、格子が100次元（n ＝ 100）である場合には、a＝ 80、b ＝ 20や、a＝70、b＝30でよい（Ｓ１３０１）。
【０１６３】
送信側装置３１０の暗号処理部１１８は、乱数生成部１１９に統計処理の設定命令を行う。乱数生成部１１９は、統計処理の設定命令に含まれる平均uの値と、乱数の値の数と、を統計処理の設定値として設定する（Ｓ１３０２）。
【０１６４】
暗号処理部１１８は、乱数生成部１１９に開始命令を行い、乱数生成部１１９が乱数rを生成する（Ｓ１３０３）。なお、生成する乱数rは、任意の確率分布に従う。乱数が一様分布に従う場合、ある区間内で全実数が同確率で現れる。例えば、区間が0以上１未満で設定された場合、0≦r<1を満たす乱数rを生成する。なお、Ｓ１３０３は、一回の処理で乱数rを一つ生成してもよいし、複数個を生成してもよい。乱数生成部１１９は、必要な乱数の値の生成が修了すると、終了通知を暗号処理部１１８に通知する。
【０１６５】
暗号処理部１１８は、生成された乱数の値rに基づき、任意の確率分布に従う、エラーベクトルの要素値eiを設定する。例えば、集合Ｓの一様分布であるように要素値eiの出現頻度を設定する場合、0≦r<1の区間における一様乱数rを用い、式ei ＝ [r（s1+s2) - s2+0.5]を満たすeiを生成すればよい。また、集合Ｔの一様分布に従う場合、
式ei ＝ [2r（t-d) + d-0.5] （0.0≦r< 0.5のとき)
式ei ＝ -[（2r-1)（t-d) - d+0.5] （0.5≦r< 1.0のとき)
上式を満たす要素値eiを生成すればよい（Ｓ１３０４）。
【０１６６】
Ｓ１３０３と同様、Ｓ１３０４において、一回の処理でエラーベクトルの一つ分の要素値ei（ただし、i∈（1、・・・、n))を生成してもよいし、複数分を生成してもよい。
【０１６７】
暗号処理部１１８は、全ての要素値e1、・・・enを生成したかを確認する。例えば、iを１から始まる要素番号とし、Ｓ１３０４においてエラーベクトルeiを生成する度に、iを１ずつインクリメントし、i＝nを満たせば、全ての要素値e1、・・・enが生成されたとみなしてよい。また、Ｓ１３０４において複数個のエラーベクトルeiを生成する場合は、iをインクリメントする数を変更すればよい。全ての要素値が生成されていればＳ１３０６へと進み、また生成されていない要素値があれば、Ｓ１３０３に戻る（Ｓ１３０５）。
【０１６８】
暗号処理部１１８はS１３０１からS１３０３と同様の手順で、乱数rを生成する（Ｓ１３０６）。
【０１６９】
暗号処理部１１８はＳ１３０６で生成した乱数rに基づき、エラーベクトルeiの要素番号iとエラーベクトルejの要素番号jを変更する。例えば、0≦r1, r2&#60;1の区間における一様乱数r1とr2を用い、式i ＝ [nr1]と式j ＝ [nr2]から、要素番号iと要素番号jを生成する（Ｓ１３０７）。Ｓ１３０４と同様、Ｓ１３０７は、一回の処理で二つのエラーベクトルの要素番号を交換してもよいし、まとめて三つ以上の要素番号を交換してもよい。
【０１７０】
要素番号の変更が一定回数を越えたかを判断する。例えば、kを１から始まる要素番号とし、Ｓ１３０７においてエラーベクトルの要素番号を交換する度に、kを１ずつインクリメントし、kがあるしきい値を越えれば、要素番号が十分にシャッフルされたとみなしてよい。要素番号が十分にシャッフルされていればＳ１３０９へと進み、また生成されていない要素値があれば、Ｓ１３０６に戻る（Ｓ１３０８）。
【０１７１】
第三の実施形態では、エラーベクトルの設定に、二つの確率分布を用いたが、これに限定せずに、二つ以上の任意の個数の確率分布を用いてエラーベクトルを生成してもよい。
【０１７２】
第一の実施形態では、一つの分布に従う乱数を用い、高い確率で、大きなノルムのエラーベクトルを利用する手段を開示した。第三の実施形態では、第一の実施形態と異なり、エラーベクトルの生成に、相対的に値の小さな分布と大きな分布を複数用い、ノルムの大きなエラーベクトルを、確実に利用可能となる。
【０１７３】
次に、第四の実施形態について説明する。ここで、第四の実施形態においては、第一の実施形態と比較して、受信側装置１３０が異なっているため、以下、これらの異なっている部分に関連する事項について説明する。
【０１７４】
第四の実施形態では、暗号文から平文に復号化する正常な処理において、従来のＧＧＨ暗号では修正できなかった誤りを修正し、正しく平文に復号化する方法を説明する。
【０１７５】
従来のＧＧＨ暗号では、復号化処理において、Ｒ−１e の全ての要素値を最近傍の整数に修正し、[Ｒ−１e]＝{0}nとするため、Ｒ−１eの全要素値が-0.5より大きく0.5より小さい必要があった。（以下の数式を参照)
【数２７】
2011002810.tif 000029
【０１７６】
そのため、[Ｒ−１e]≠{0}nのときには、Ｔ−１[Ｒ−１ｃ]   ≠ｍであり、暗号文ｃから平文ｍに正しく復号化できないという課題がある。そこで、[Ｒ−１e]≠{0}nの場合にも、正しく復号化する処理手順を以下に説明する。
【０１７７】
暗号文ｃから復号化したｍ’が、送信文ｍと同じ値であるためには、Ｒ （Ｒ−１c) ‐ ｍ’ ＝ eでなければならない。そこで、Ｒ （（Ｒ−１c) ‐ ｍ’）の任意の要素値が確かにエラーベクトルeの要素値であるかを効率的に検証するシーケンスを示す。
【０１７８】
第四の実施形態では、受信側装置４３０は、記憶部４３１と、制御部４３６と、入力部１４１と、出力部１４２と、通信部１４３と、を備え、第一の実施形態との相違点について説明する。
【０１７９】
記憶部４３１は、秘密鍵記憶領域４３２と、公開鍵記憶領域４３３と、一時情報記憶領域４３４と、テーブル記憶領域４３５と、を備え、第一の実施形態と比較して、テーブル記憶領域４３５が異なっている。
【０１８０】
図１６は、テーブル記憶領域４３５の概略図である。図示するように、誤差テーブル（１）、誤差テーブル（２）、成功値と、を備える。誤差テーブル（１）は、要素番号と、整数部と、少数部と、を備える。誤差テーブル（２）は、要素順を表す変数iと、要素番号と、を備える。成功値は、誤差テーブル（２）における変数ｉを指す情報、を記憶する。
【０１８１】
制御部４３６は、全体制御部１３７と、鍵生成部１３８と、復号処理部４３９と、を備え、第一の実施形態と比較して、復号処理部４３９が異なっている。
【０１８２】
復号処理部４３９は、テーブル記憶領域に記憶する情報を用い、送信側装置１１０から送られてきた暗号文を復号化する。
【０１８３】
図１５は、ＧＧＨ暗号における復号化プロトコルにおいて、受信側装置４３０の復号処理部４３９における処理を示すフローチャートである。
【０１８４】
図１５に示すＳ１４０３からＳ１４２５の処理フローは、第一の実施形態における図７に示す処理フローのＳ１６の処理を詳細化したものである。
【０１８５】
既に、受信側装置２は、送信側装置１がネットワーク経由で送信した暗号文を受信しているものとする。
【０１８６】
復号処理部４３９は、誤差テーブル（２）における要素順を表す変数ｉ（１５１２）を0に初期化する（Ｓ１４０３）。
【０１８７】
復号処理部４３９は、暗号文ｃに秘密鍵Ｒ−１を掛け合わせ、Ｒ−１ｃの要素ごとにバイナリ（２進数）表現で誤差テーブル（１）に記憶する（Ｓ１４０４）。誤差テーブル（１）には、昇順の要素番号（１５０２）ごとに、左側にある最上位ビットから、右側にある最下位ビットまで、各要素値を並べる。このとき、Ｒ−１ｃの整数部分は、誤差テーブル（１）の整数部に、小数部分は誤差テーブル（２）の少数部に記憶する。
【０１８８】
復号処理部４３９は、誤差テーブル（１）の少数部（１５０４）が０．２５以上から０．７５未満であるかを確認する（Ｓ１４０５）。すなわち、少数部（１５０４）の第一位と第二位が01または10であるかを検査する（ （Ｒ−１c)  ｍ’の計算は必要ない）。
【０１８９】
以降では、誤差テーブル（１）の少数部（１５０４）をベクトルe’で表し、ベクトルe’の各要素値は要素番号ｊを用いてej’で表す。
【数２８】
2011002810.tif 000030
【０１９０】
Ｓ１４０５において、該当するＲ-1ｃの要素が存在した場合、［Ｒ−１e］≠｛0｝ｎとなり、復号化が失敗する可能性が高い。ベクトルe’の要素番号ｊと数値０を誤差テーブル（２）に記憶する。また、復号処理部４３９は、誤差テーブル（２）１５１１に格納した要素番号ｊ（１５１３）の個数をカウントし、ｈ＝２ｊ−１の式から、閾値ｈをメモリユニット２３に格納する（たとえば、要素番号ｊ＝１，１０、１００を格納したとき、要素番号ｊの個数は３、閾値ｈ＝７（＝２３−１）である。）。（Ｓ１４０６）
【０１９１】
ｈ＝０のとき、変数ｉを成功値（１５２１）として記憶し、Ｓ１４１４へと進む（Ｓ１４０７）。
【０１９２】
復号処理部４３９は、誤差テーブル（２）の変数ｉ（１５１２）を１つインクリメントする（Ｓ１４０８）。
【０１９３】
復号処理部４３９は、誤差テーブル（１）１５０１より、ベクトルe’をロードする（Ｓ１４０９）。
【０１９４】
復号処理部４３９は、要素番号ｊ（１５１３）をロードする。また、誤差テーブル（２）１５１１の行（変数ｉ（１５１２）に対応）と列（要素番号ｊ（１５１３））から、値ｓi,jをロードする（Ｓ１４１０）。
【０１９５】
演算ユニットは、要素番号ｊ（１５１３）と値ｓi,jを用い、ベクトルe’の要素値ej’を次式に従って、更新する（Ｓ１４１１）。
【数２９】
2011002810.tif 000031
【０１９６】
復号処理部４３９は、ベクトルe’に秘密鍵Ｒを掛け合わせて得られるベクトルが、全て適切なエラーベクトルの要素値であるかを検証する。例えば、第三の実施形態では、エラーベクトルｅの要素値が{-s1, -（s1-1),・・・s2-1,s2}の集合Ｓまたは、{-t, -（t-1), ・・・-（d-1),-d, d, d+1, t-1, t}の集合Ｔ（ただし、t＞d）に含まれているかを確認する。Ｒe’の全ての要素が適切なエラーベクトルの要素値であれば、変数iを成功値（１５２１）として記憶する（Ｓ１４１２）。
【０１９７】
復号処理部４３９は、変数ｉ（１５１２）が閾値ｈと値を比較し、変数ｉ（１５１２）が閾値ｈの値と等しい、または大きければ、Ｓ１４１８へ進む（Ｓ１４１４）。
【０１９８】
復号処理部４３９は、Ｓ１４１０でロードとした値ｓi,jのうち一つを、０から１に更新する（Ｓ１４１５）。
【０１９９】
復号処理部４３９は、誤差テーブル（２）における変数ｉ（１５１２）を１つインクリメントする（Ｓ１４１６）。
【０２００】
復号処理部４３９は、変数ｉ（１５１２）を行、要素番号ｊ（１５１３）を列とするｓi,jを誤差テーブル（２）１５１１に追加する。Ｓ１４０７へ戻る（Ｓ１４１７）。
【０２０１】
復号処理部４３９は、成功値ｉを１つロードする（Ｓ１４１８）。
【０２０２】
復号処理部４３９は、誤差テーブル（２）１５１１の行（成功値ｉに対応）と列（要素番号ｊ（１５１３））から、値ｓi,jをロードする（Ｓ１４１９）。
【０２０３】
演算ユニットは、要素番号ｊ（１５１３）と値ｓi,jを用い、ベクトルe’の要素値ej’を次式に従って、更新する（Ｓ１４２０）。
【数２９】
2011002810.tif 000032
【０２０４】
復号処理部４３９は、誤差テーブル（１）１５０１の整数部（１５０３）をロードする。ロードした整数部（１５０３）をベクトルｍ’とし、ベクトルｍ’の各要素は要素番号ｊ（１５１３）を用いてｍj’で表す（Ｓ１４２１）。
【０２０５】
復号処理部４３９は、次式により、ベクトルｍ’を更新する（Ｓ１４２２）。
【数３０】
2011002810.tif 000033
【０２０６】
復号処理部４３９は、メモリユニット２３に格納された秘密鍵Ｔと暗号文ｃをロードする（Ｓ１４２３）。
【０２０７】
復号処理部４３９は、ｃ−Ｔ-1ｍ’を計算する（Ｓ１４２４）。
【０２０８】
復号処理部４３９は、Ｒe’を計算し、Ｓ１４２４で計算した（ｃ−Ｔ-1ｍ’）と値が等しいかを検証する。値が等しくなければ、Ｓ１４１９でロードした成功値ｉを削除し、Ｓ１４１９へ戻る。値が等しければ、エラーベクトルが正しく推定できているので、Ｓ１４２２で得たベクトル’を送信文とみなす（Ｓ１４２５）。
【０２０９】
第四の実施形態では、誤差テーブル（１）１５０１の選出に、Ｒ-1ｃの少数部（１５０４）が０．２５以上から０．７５未満であるかを確認した。しかし、本手法は、０．２５以上から０．７５未満という特定値である必要はなく、他の値でもかまわない。
【０２１０】
第四の実施形態では、変数ｉ（１５１２）の値が更新される度に、誤差テーブル（２）１５１１の全ての要素番号ｊ（１５１３）に対応する値ｓi,jを随時追加した。しかし、変更のあったｓi,jのみ追加し、他の値ｓi,jは更新前の変数ｉ（１５１２）における値ｓi,jを参照するように変更してもよい。
【０２１１】
第四の実施形態では、変数ｉ（１５１２）の値が更新される度に、誤差テーブル（２）１５１１に新たな列を追加した。しかし、誤差テーブル（２）１５１１の以前の列に新たなｓi,jを上書きするように変更してもよい。
【０２１２】
第四の実施形態では、Ｓ１４１１およびＳ１４２０において、変数ｉ（１５１２）ごとに、全ての要素番号ｊ（１５１３）を用いてベクトルｅ’を再計算した。しかし、以前に用いたベクトルｅ’を再利用し、値に変更があった要素番号ｊ（１５１３）のｓi,jのみを利用し、ベクトルｅ’を再計算するように変更してもよい。
【０２１３】
第四の実施形態では、Ｒ−１ｃの要素番号の昇順に誤差テーブル（１）を作成した。しかし、誤差テーブル（１）は、降順または順不同に作成してもかまわない。
【０２１４】
第四の実施形態では、Ｒ−１ｃの要素がバイナリ表現（2進数表現）である場合を示した。しかし、本手法はバイナリ表現に縛られるものではない。例えば、IEEE-754で規定される単精度表現（符号部、指数部、仮数部の3つで構成）や、倍精度表現等でも同様に適用できる。
【０２１５】
第四の実施形態では、変数ｉの昇順に誤差テーブル（２）を作成した。しかし、誤差テーブル（２）は、降順または順不同に作成してもかまわない。
【０２１６】
第四の実施形態では、各処理が逐次的に実施されるものとして、記述した。しかし、本処理は、処理手順や処理形態に依存するものではない。例えば、各作業を並列に処理する事が可能である。また、処理手順を入れ替えてもかまわない。
【０２１７】
第四の実施形態では、基本的に、演算ユニットが作成したデータをいったん記憶し、必要になるたびに、テーブル記憶領域４３５からデータをロードするよう処理手順を記述した。しかし、本処理は、記述した処理フローに依存するものではない。例えば、復号処理部が保持するデータなどで計算可能な場合、データの記憶や、データのロードを省いてもかまわない。
【０２１８】
第四の実施形態では、第一の実施形態におけるGGH復号化の復号化誤りの確率をより低下させることが可能になる。
【符号の説明】
【０２１９】
１００：暗号システム、１１０，３１０：送信側装置、１１１，２１１，３１１：記憶部、１１２：送信文記憶領域、１１３：公開鍵記憶領域、１１４：一時情報記憶領域、２２４：エラーベクトル記憶領域、３１５：パラメータ記憶領域、４３５：テーブル記憶領域、１１６：制御部、１１７，２１７：全体制御部、１１８：暗号処理部、１１９：乱数生成部、２２６：関数処理部、１２１：入力部、１２２：出力部、１２３：通信部、１３０，４３０：受信側装置、１３１，２３１，４３１：記憶部、１３２：秘密鍵記憶領域、１３３：公開鍵記憶領域、１３４：一時情報記憶領域、２４５：暗号文記憶領域、２４６：復号文記憶領域、１３６，２３６：制御部、１３７，２３７：全体制御部、１３８：鍵生成部、１３９：復号処理部、２４８：関数処理部、１４１：入力部、１４２：出力部、１４３：通信部、１５０１：誤差テーブル（１）、１５０２：誤差テーブル（２）、１５２１：成功値。
【図１】
2011002810.tif 000034
【図２】
2011002810.tif 000035
【図３】
2011002810.tif 000036
【図４】
2011002810.tif 000037
【図５】
2011002810.tif 000038
【図６】
2011002810.tif 000039
【図７】
2011002810.tif 000040
【図８】
2011002810.tif 000041
【図９】
2011002810.tif 000042
【図１０】
2011002810.tif 000043
【図１１】
2011002810.tif 000044
【図１２】
2011002810.tif 000045
【図１３】
2011002810.tif 000046
【図１４】
2011002810.tif 000047
【図１５】
2011002810.tif 000048
【図１６】
2011002810.tif 000049