説明

暗号化装置、プログラム、暗号システム及び暗号化方法

【課題】GGH暗号において、ユークリッドノルムを大きく、かつ、復号誤りが十分に低くなるようにエラーベクトルを設定する技術を提供すること。
【解決手段】送信側装置110の乱数生成部119は、0の値から離れると、出現確率が低くなるように乱数の値を生成し、暗号処理部118は、乱数生成部119が生成した乱数の値を要素値とするエラーベクトルを生成し、GGH暗号における暗号文を生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、GGH暗号を用いてデータを暗号化する技術に関する。
【背景技術】
【0002】
公開鍵暗号の安全性は、数学的な問題の困難性に安全性の根拠をおくのがほとんどである。例えば、RSA暗号は素因数分解問題の困難性、楕円曲線暗号は楕円曲線上の離散対数問題の困難性、を安全性の根拠としている。
【0003】
一方、これらの公開鍵暗号は、現在の標準的な計算機(Turing機械)に対して安全性を検証しているが、近年の量子計算機上の解読アルゴリズムの発展により、これまで解読困難であった数学的な問題が効率的に解読され、既存の公開鍵暗号が破られる危険性がある。
【0004】
このため、量子計算機に対しても解読困難であるよう、1997年に近似ベクトル問題と呼ばれる一種の格子問題の困難性を安全性の根拠とする公開鍵暗号アルゴリズム(以降、GGH暗号と呼ぶ)がGoldreichらによって提案された(非特許文献1を参照)。
【先行技術文献】
【非特許文献】
【0005】
【非特許文献1】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).
【非特許文献2】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).
【発明の概要】
【発明が解決しようとする課題】
【0006】
n個の線形独立なベクトルb,・・・,b
【数1】


をもつ行列B、
【数2】



が張る格子L(B)は、
【数3】


で表される。
【0007】
このとき、行列Bによって生成される格子Lの行列式はdet(L(B))=det(B)の関係式が成り立つ。また、格子Lがn次元のとき、その最短ベクトルの長さは、
【数4】


と推定することができる。
【0008】
これに対して、最短ベクトル問題を効率的に(多項式時間で)解くアルゴリズムは知られていないものの、その近似解は効率的に(多項式時間で)LLLアルゴリズムで解読可能である。
【0009】
このLLLアルゴリズムを用い、
【数5】


を満たすベクトルvが見つかれば、vは(近似解ではなく)最短ベクトルそのものであると期待できる。
【0010】
ただし、
【数6】


はベクトルvのユークリッドノルム(各要素値の自乗の和の平方根)を指す。即ち、vの要素値をv
【数7】



とするとき、次の(8)式が成り立つ。
【数8】

【0011】
ここで、vに対する格子Lの期待比(expected gap)は、比率
【数9】


で表せる。この期待比が大きいほど、LLLアルゴリズムが最短ベクトルを見つけやすいことが知られている。
【0012】
一方、GGH暗号が安全性の根拠とする問題を、近似ベクトル問題から上記の最短ベクトル問題に帰着させる方法が知られている。GGH暗号における公開鍵Bと暗号文cから、新たに(n+1)行(n+1)列の行列B’を生成する。
【数10】

【0013】
暗号文cに最も近い格子点が平文mの場合、L(B’)の最短ベクトルは(c−Bm,1)であると期待できる。従って、L(B’)の最短ベクトルが計算できれば、平文mが得られる。一般に、(c−Bm,1)に対するLの期待比(expected gap)は、c−Bmのユークリッドノルムが小さいほど大きくなる。
【0014】
GGH暗号では、エラーベクトルeのユークリッドノルムが最大でも
【数11】


(全ての要素値がsまたは−sの場合)である。復号誤りを十分に低くするためにはsの値も小さくする必要があるため、結果的にエラーベクトルeのユークリッドノルムが小さく、vに対する格子Lの期待比が大きくなってしまい、GGH暗号には上記の攻撃は適用可能である。
【課題を解決するための手段】
【0015】
本明細書では、GGH暗号において、ユークリッドノルムを大きく、かつ、復号誤りが十分に低くなるようにエラーベクトルを設定する技術が開示される。
【0016】
また、ユークリッドノルムの大きなエラーベクトルを用いたGGH暗号において、暗号文から正しい平文を復号化する技術が開示される。
【0017】
開示する一つの例によれば、予め定められた値から離れると、出現確率が低くなるように生成された乱数の値を要素値とするエラーベクトルを用いてGGH暗号化を施す。
【0018】
また、開示する他の一つの例によれば、エラーベクトルによる誤り箇所を検出し、特定された箇所における正しい値の候補を含んで構成されるテーブルを用い、GGH復号化を施す。
【0019】
例えば、GGH暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置であって、予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、を行う制御部を備える暗号化装置が開示される。
【発明の効果】
【0020】
本明細書が提供する技術によれば、GGH暗号において、ユークリッドノルムを大きく、かつ、復号誤りが十分に低くなるようにエラーベクトルを設定することができる。また、ユークリッドノルムの大きなエラーベクトルを用いたGGH暗号において、暗号文から正しい平文を復号化することが可能になる。
【図面の簡単な説明】
【0021】
【図1】暗号システムの概略を例示する図。
【図2】送信側装置の機能概略を例示する図。
【図3】正規分布の概略を例示する図。
【図4】コンピュータの概略構成を例示する図。
【図5】乱数生成器の機能の概略を例示する図。
【図6】受信側装置の機能の概略を例示する図。
【図7】送信側装置と受信側装置とが、送信文を共有する処理を例示するシーケンス図。
【図8】エラーベクトルeの生成処理を例示するフローチャート。
【図9】乱数の値を生成する処理を例示するフローチャート。
【図10】送信側装置と受信側装置とが、共通鍵を用いて送信文を共有する処理を例示するシーケンス図。
【図11】送信側装置の機能の概略を例示する図。
【図12】受信側装置の機能の概略を例示する図。
【図13】暗号文の送信元を証明する処理を例示するシーケンス図。
【図14】エラーベクトルeの生成処理を例示するフローチャート。
【図15】暗号文を復号化する処理を例示するフローチャート。
【図16】暗号文の復号化処理において用いるテーブルの概略を例示する図。
【発明を実施するための形態】
【0022】
図1は、本発明の第一の実施形態である暗号システム100の概略図である。図示するように、暗号システム100は、送信側装置110と、受信側装置130と、を備え、これらは、ネットワーク150を介して相互に情報を送受信することができるようにされている。
【0023】
ここで、本実施形態における送信側装置110は、GGH暗号における鍵情報(公開鍵)を用いて暗号化を行う暗号化装置として機能し、受信側装置130は、GGH暗号における鍵情報(秘密鍵)を用いて復号化を行う復号化装置として機能する。
【0024】
図2は、送信側装置110の機能概略図である。図示するように、送信側装置110は、記憶部111と、制御部116と、入力部121と、出力部122と、通信部123と、を備える。
【0025】
記憶部111は、送信文記憶領域112と、公開鍵記憶領域113と、一時情報記憶領域114と、を備える。
【0026】
送信文記憶領域112には、受信側装置130に送信する文書データである送信文を特定する情報が記憶される。
【0027】
公開鍵記憶領域113には、公開鍵を特定する情報が記憶される。ここで、本実施形態においては、受信側装置130より送信されてきたGGH暗号における公開鍵Bを特定する情報が記憶される。
【0028】
一時情報記憶領域114には、制御部116での処理で必要となる情報が記憶される。
【0029】
制御部116は、全体制御部117と、暗号処理部118と、乱数生成部119と、を備える。
【0030】
全体制御部117は、送信側装置110での処理の全体を制御する。
【0031】
例えば、本実施形態においては、全体制御部117は、入力部121を介して,入力を受け付けた送信文を送信文記憶領域112に記憶する処理を行う。
【0032】
また、全体制御部117は、受信側装置130より、通信部123を介して受信した公開鍵を公開鍵記憶領域113に記憶する処理を行う。
【0033】
さらに、全体制御部117は、暗号処理部118で生成された暗号文を、通信部123を介して、受信側装置110に送信する処理を行う。
【0034】
加えて、全体制御部117は、入力部121を介して、平均と分散の値の入力を受け付けて、一時情報記憶領域114に記憶する処理を行う。
【0035】
暗号処理部118は、GGH暗号における暗号化処理を行う。
【0036】
例えば、本実施形態においては、送信文記憶領域112に記憶されている文書データ
【数12】


から暗号文
【数13】


を生成する。暗号文cは、下記の(15)式に示すように、格子点Bmにエラーベクトル
【数14】


を加えた値を有する。
【数15】

【0037】
ただし、エラーベクトルeは、乱数生成部119で生成された乱数の値を要素値とする。なお、エラーベクトルeの要素値の割り振りが偏ると、復号化時の誤りが発生したり、安全性が失われたりする恐れがある。そのため、平均値を抑えるように、各要素値を調整する。
【0038】
乱数生成部119は、暗号処理部118で暗号化を行う際に必要となるエラーベクトルeの要素値となる乱数の値を生成する。
【0039】
ここで、乱数生成部119で生成する乱数の値は、平均が予め定められた閾値の範囲内であり、乱数の値が平均から離れると、当該乱数の値の出現確率が小さくなるようになっている。
【0040】
本実施形態においては、乱数生成部119で生成する乱数の値は、例えば、図3(正規分布の概略図)に示すような、正規分布に沿うように算出される。
【0041】
正規分布では、確率変数(乱数の値)xの確率密度関数f(x)が、下記の(16)式で与えられる。
【数16】

【0042】
ここで、πは円周率、exp(a)はeaを指す。また、uとsは正規分布の平均(中心の位置)と分散(ばらつき)を規定するパラメータである。なお、本実施形態において、uの値が予め定められた敷値の範囲内にあり、sの値が設定された分散の値から予め定められた敷値の範囲内にある場合には、乱数の値は正規分布に沿っているものとする。
【0043】
また、図3においては、(1)は、u=0、σ=1とする正規分布であり、(2)は、u=0、σ=3とする正規分布であり、(3)は、u=0、σ=10とする正規分布である。
【0044】
このように、平均uの値を小さく、分散sの値を大きくした正規分布を用いて算出された乱数の値を要素値とすることで、小さい平均値で、かつ、ユークリッドノルムが大きいエラーベクトルを生成できる。
【0045】
なお、平均uの値は「0」だけでなく、任意の値を設定することができる。
【0046】
入力部121は、情報の入力を受け付ける。
【0047】
出力部122は、情報を出力する。
【0048】
通信部123は、ネットワーク150を介した情報の送受信を行う。
【0049】
以上に記載した送信側装置110は、例えば、図4(コンピュータ800の概略図)に示すような、CPU(Central Processing Unit)801と、メモリ802と、HDD(Hard Disk Drive)等の外部記憶装置803と、CD(Compact Disk)やDVD(Digital Versatile Disk)等の可搬性を有する記憶媒体804に対して情報を読み書きする読書装置805と、キーボードやマウスなどの入力装置806と、ディスプレイなどの出力装置807と、通信ネットワークに接続するためのNIC(Network Interface Card)等の通信装置808と、これらを連結するシステムバスなどの内部通信線(システムバスという)809と、を備えた一般的なコンピュータ800で実現できる。
【0050】
例えば、記憶部111は、CPU801がメモリ802又は外部記憶装置803を利用することにより実現可能であり、制御部116と制御部116に含まれる各処理部は、外部記憶装置803に記憶されている所定のプログラムをメモリ802にロードしてCPU801で実行することで実現可能であり、入力部121は、CPU801が入力装置806を利用することで実現可能であり、出力部122は、CPU801が出力装置807を利用することで実現可能であり、通信部123は、CPU801が通信装置808を利用することで実現可能である。
【0051】
この所定のプログラムは、読書装置805を介して記憶媒体804から、あるいは、通信装置808を介してネットワークから、外部記憶装置803にダウンロードされ、それから、メモリ802上にロードされてCPU801により実行されるようにしてもよい。また、読書装置805を介して記憶媒体804から、あるいは、通信装置808を介してネットワーク150から、メモリ802上に直接ロードされ、CPU801により実行されるようにしてもよい。
【0052】
但し、本実施形態の乱数生成部119については、コンピュータシステム上にソフトウェア的に実現されるものに限定されない。例えば、ASIC(Application Specific Integrated Circuits)、FPGA(Field Programmable Gate Array)等の集積ロジックICによりハード的に実現されるもの、例えば、図5(乱数生成器900の概略図)に示すような乱数生成器900で構成することも可能である。
【0053】
図示するように、乱数生成器900は、プログラム用メモリ901と、制御回路902と、レジスタ903と、アキュムレータ904と、一時データ用メモリ905と、クロック発生器906と、I/F907と、を備える。
【0054】
プログラム用メモリ901には、制御回路902で正規分布に沿った乱数の値を生成するための乱数生成用プログラムが記憶されている。
【0055】
制御回路902は、プログラム用メモリ901より読み込んだ乱数生成用プログラムを実行して、乱数の値を生成し、アキュムレータ904に出力する。出力された乱数の値は、I/F907を介して、図4に示すシステムバス809よりCPU801が取得する。
【0056】
図6は、受信側装置130の概略図である。図示するように、受信側装置130は、記憶部131と、制御部136と、入力部141と、出力部142と、通信部143と、を備える。
【0057】
記憶部131は、秘密鍵記憶領域132と、公開鍵記憶領域133と、一時情報記憶領域134と、を備える。
【0058】
秘密鍵記憶領域132には、秘密鍵を特定する情報が記憶される。ここで、本実施形態においては、後述する鍵生成部138が生成したGGH暗号における秘密鍵R及びその逆元R−1、並びに、ユニモジュラ行列T及びその逆行列T−1を特定する情報が記憶される。
【0059】
公開鍵記憶領域133には、公開鍵を特定する情報が記憶される。ここで、本実施形態においては、後述する鍵生成部138が生成したGGH暗号における公開鍵Bを特定する情報が記憶される。
【0060】
一時情報記憶領域134には、制御部136での処理で必要となる情報が記憶される。
【0061】
制御部136は、全体制御部137と、鍵生成部138と、復号処理部139と、を備える。
【0062】
全体制御部137は、受信側装置130での処理の全体を制御する。例えば、本実施形態においては、鍵生成部138が生成した公開鍵を特定する情報を、通信部143を介して、送信側装置110に送信する処理を行う。
【0063】
鍵生成部138は、GGH暗号における秘密鍵及び公開鍵を生成し、それぞれ、秘密鍵記憶領域132及び公開鍵記憶領域133に記憶する処理を行う。
【0064】
例えば、本実施形態においては、鍵生成部138は、
【数17】


但し、
【数18】


である。lは任意の整数でよく、kは、
【数19】


などの関係式から作成した整数である。
【0065】
秘密鍵Rと公開鍵Bはn行n列の行列であり、公開鍵Bは、秘密鍵Rと同じ格子を張る格子基底
【数20】


で、ユニモジュラ行列
【数21】


と秘密鍵Rを用いてB=RTから生成する。ただし、ユニモジュラ行列とは、行列式の絶対値が1であるような行列を指す。ここで、公開鍵Bから、秘密鍵Rが特定されないよう、複数のユニモジュラ行列を生成し、Rに複数回それらのユニモジュラ行列を掛け合わせて公開鍵Bを生成してもよい。
【0066】
復号処理部139は、送信側装置110から送られてきた暗号文から送信文を復号化する。
【0067】
例えば、本実施形態においては、復号処理部139は、ユニモジュラ行列Tの逆行列T−1、秘密鍵Rの逆元R−1、暗号文cを、それぞれ掛け合わせ、T−1[R−1c]を計算する。
【0068】
ただし、
【数22】


はベクトルaの全ての要素値の少数点以下を四捨五入した値である。エラーベクトルの各要素値が十分に小さい場合、極めて高い確率で
【数23】


である。従って、次の(25)式に従い、
【数24】


から平文mを復元する。
【数25】

【0069】
入力部141は、情報の入力を受け付ける。
【0070】
出力部142は、情報を出力する。
【0071】
通信部143は、ネットワークを介して情報を送受信する。
【0072】
以上に記載した受信側装置130は、例えば、図4に示すような一般的なコンピュータ800で実現できる。
【0073】
例えば、記憶部131は、CPU801がメモリ802又は外部記憶装置803を利用することにより実現可能であり、制御部136と制御部136に含まれる各処理部は、外部記憶装置803に記憶されている所定のプログラムをメモリ802にロードしてCPU801で実行することで実現可能であり、入力部141は、CPU801が入力装置806を利用することで実現可能であり、出力部142は、CPU801が出力装置807を利用することで実現可能であり、通信部143は、CPU801が通信装置808を利用することで実現可能である。
【0074】
この所定のプログラムは、読書装置805を介して記憶媒体804から、あるいは、通信装置808を介してネットワークから、外部記憶装置803にダウンロードされ、それから、メモリ802上にロードされてCPU801により実行されるようにしてもよい。また、読書装置805を介して記憶媒体804から、あるいは、通信装置808を介してネットワーク150から、メモリ802上に直接ロードされ、CPU801により実行されるようにしてもよい。
【0075】
図7は、GGH暗号における暗号化プロトコルを用いて、送信側装置110と受信側装置130とが送信文を共有する処理を示すシーケンス図である。
【0076】
なお、送信文は、暗号化の対象となるデータ全般を指し、例えば、鍵データ、プログラムデータ、動画データ、ドキュメントデータ等が含まれる。
【0077】
まず、送信側装置110の全体制御部117は、入力部121を介して、暗号文の作成指示の入力を受け付ける(S10)。
【0078】
次に、送信側装置110の暗号処理部118は、乱数生成部119より乱数の値を取得して、エラーベクトルeを生成する(S11)。このステップS11での処理は、図8を用いて詳細に説明する。
【0079】
そして、送信側装置110の暗号処理部118は、公開鍵記憶領域113に記憶されている公開鍵B及び送信文記憶領域112に記憶されている送信文mを取得し、取得した公開鍵Bに送信文mを掛け合わせ、エラーベクトルeを足すことにより、(Bm+e)の値を有する暗号文cを生成する(S12)。
【0080】
次に、送信側装置110の全体制御部117は、通信部123を介して、生成した暗号文cを受信側装置130に送信する(S13)。
【0081】
受信側装置130の全体制御部137は、通信部143を介して、暗号文cを受信する(S14)。
【0082】
そして、受信側装置130の全体制御部137は、入力部141を介して、暗号文cの復号化指示の入力と受け付けると(S15)、復号処理部139に暗号文cの復号処理を行わせる(S16)。
【0083】
ここで、復号処理部139は、秘密鍵記憶領域132に記憶されている秘密鍵Rの逆元R−1及びユニモジュラ行列Tの逆行列T−1を取得し、T−1[R−1c]を計算し、暗号文cを復号化した復号文m’を取得する。
【0084】
そして、受信側装置130の全体制御部137は、復号文m’を一時情報記憶領域134に記憶する(S17)。
【0085】
なお、ネットワーク150におけるデータ配送の誤りや、暗号化又は復号化プロトコルにおける誤りから、送信文mと復号文m’の値が異なるおそれある。そこで、ステップS16の後に、復号文m’の真正性を検査する処理、復号文m’の誤りを訂正する処理、復号文m’の真正性の真正性が認められない場合に、送信側装置110に再送を要求する処理、等を追加してもよい。
【0086】
なお、復号文m’の真正性の検査では、暗号文cの一部に格納された、または別に配送されたm’またはR−1cのパリティの比較処理や、m’またはR−1cのハッシュ値の照合処理を追加しても良い。
【0087】
さらに、復号文m’の誤り訂正処理では、誤り訂正符号等を利用し、復号文m’の誤りを訂正する処理を追加してもよい。
【0088】
図8は、送信側装置110の暗号処理部118におけるエラーベクトルeの生成処理を示すフローチャートである。
【0089】
まず、送信側装置110の暗号処理部118は、乱数生成部119に統計処理の設定命令を行う(S20)。この設定命令については、入力部121を介して予め入力されている、平均uの値、分散sの値、乱数の値の数、が含まれる。
【0090】
そして、乱数生成部119は、統計処理の設定命令に含まれる平均uの値と、分散sの値と、乱数の値の数と、を統計処理の設定値として設定する(S21)。
【0091】
そして、暗号処理部118は、乱数生成部119に開始命令を行い(S22)、乱数生成部119が乱数の値を生成する(S23)。なお、ステップS23での処理については、図9を用いて詳細に説明する。
【0092】
次に、乱数生成部119は、必要な数の乱数の値の生成が終了すると、終了通知を暗号処理部118に通知する(S24)。
【0093】
そして、暗号処理部118は、生成された乱数の値を一時情報記憶領域114より取得して、エラーベクトルの要素値とする(S25)。
【0094】
なお、ステップS25での処理が終了した後、暗号処理部118は、必要に応じ、取得した乱数値を変換する。例えば、取得した乱数値が極端に大きいまたは小さい場合、その値を他の値に変換してもよい。この場合でも、入力された平均uと分散sの値で特定される正規分布に対応した出現回数となるように、他の値を選択すればよい。
【0095】
例えば、暗号処理部118は、閾値に満たない値については、閾値を満たす最小の値から順に、正規分布に対応した出現回数となるように他の値を割り振り、また、閾値を超えた値については、閾値を満たす最大の値から順に、正規分布に対応した出現回数となるように他の値を割り振る等により他の値に変更すればよい。
【0096】
また、暗号処理部118は、取得した乱数値が整数ではない(小数点を含む)場合、小数点第一位以下の切り捨てや切り上げ、または四捨五入により、少数を整数に丸める処理を行ってもよい。
【0097】
また、暗号処理部118は、取得した乱数値が正規分布に対応したものか否かを検査して、乱数値の再生成が必要かを検査するようにしてもよい。そして、再生成をする場合はステップS22に戻り、処理を繰り返すことも可能である。
【0098】
さらに、暗号処理部118は、エラーベクトルの要素値の要素番号を変更したい場合は、要素値の順序の変更処理(シャッフル)を行うことも可能である。
【0099】
また、乱数生成部119が、正規分布とは無関係に、ランダムに固定ビット長(160ビット、128ビット等)の整数を出力する場合には、乱数生成部119が出力した乱数の値から、改めて正規分布に沿った、乱数へ変更する処理を図8の処理フローに追加してもよい。例えば、乱数生成部119が出力する乱数または乱数の一部と、ある確率分布に沿った変数への写像から、確率分布に沿った乱数が生成できる。また、同様の手法は、乱数生成部119が出力する乱数の値の確率分布が不明な場合にも適用できる。
【0100】
図9は、送信側装置110の乱数生成部119が、乱数の値を生成する処理を示すフローチャートである。
【0101】
まず、乱数生成部119は、暗号処理部118より統計処理の設定命令(例えば、平均uと分散sを指すパラメータ、乱数の値の数等)を受信すると(S30)、乱数生成部119は、これらのパラメータ等を統計処理の設定値として設定する。
【0102】
次に、乱数生成部119は、暗号処理部118より開始命令を受けると(S32)、設定命令で特定された数の乱数の値が、設定命令に含まれているパラメータで特定される正規分布に従うように、乱数の値を生成する(S32)。
【0103】
ここで、乱数生成部119の乱数の値の生成は、設定命令に含まれているパラメータで特定される正規分布に従うように予め記憶部111に記憶されている乱数の値を抽出するようにしてもよく、また、乱数生成部119でランダムに抽出した乱数の値が、必要な乱数の値の数に対して、設定命令に含まれているパラメータで特定される正規分布で特定される出現回数となるように、当該乱数の値を抽出するようにしてもよい。
【0104】
そして、乱数生成部119は、生成した乱数の値を一時情報記憶領域114に記憶する(S33)。
【0105】
ここで、出力された乱数の値は、一定の確率で偏る可能性がある(例えば、極めて低い確率であるが、全ての値が0である、など)ので、乱数生成部119は、出力された乱数の値が、設定命令に含まれているパラメータで特定される正規分布に沿うか否かを検査して(S34)、沿わない場合には(ステップS34でYes)ステップS32に戻り処理を繰り返す。
【0106】
設定命令に含まれているパラメータで特定される正規分布に沿うか否かについては、例えば、乱数生成部119は、一時情報記憶領域114に記憶された乱数の値の平均値が設定命令に含まれているパラメータである平均値uに対して予め定められた閾値の範囲内にあり、かつ、一時情報記憶領域114に記憶された乱数の値の分散の値が設定命令に含まれているパラメータである分散sに対して予め定められた閾値の範囲内にある場合には、設定命令に含まれているパラメータで特定される正規分布に沿うと判断する。
【0107】
なお、以上に記載した実施形態においては、図7に示すシーケンス図で、GGH暗号における暗号化プロトコルを用いて送信文を暗号化して送信側装置110から受信側装置130に送信する処理を示したが、このような態様に限定されず、例えば、図10に示すように、GGH暗号における暗号化プロトコルを用い、送信側装置110と受信側装置130とが、まず共通鍵を共有し、次に共通鍵暗号における暗号プロトコルを用い、送信文を共有するようにしてもよい。
【0108】
例えば、図10において、送信側装置110では、図7のステップS10からS12までの処理と同様の処理を、暗号化の対象を共通鍵として実行し、暗号文cを生成して、送信側装置110の全体制御部117は、生成した暗号文cを受信側装置130に送信する(S40)。
【0109】
そして、受信側装置130は、図7のステップS14からS16まで処理と同様の処理を、受信した暗号文cに対して実行し、復号された共通鍵を記憶部131に記憶する(S41)。なお、受信側装置130が無事に共通鍵を復号化できた場合、受信側装置130の全体制御部137は、通信部143を介して、送信側装置110に受信通知を送付しても良い。また、復号化できなかった場合は、受信側装置130の全体制御部137は、通信部143を介して、送信側装置110に再送処理を要求しても良い。このような再送処理の要求を受信した送信側装置110では、ステップS40に戻り処理を繰り返す。
【0110】
次に、送信側装置110の暗号処理部118は、共通鍵を用い、共通鍵暗号で送信用データを暗号化することで暗号化データを生成する(S42)。共通鍵暗号は、ブロック暗号でも、ストリーム暗号でも良い。
【0111】
そして、送信側装置110は、生成した暗号化データを、通信部123を介して、受信側装置130に送信する(S43)。
【0112】
次に、受信側装置130は、通信部143を介して、暗号化データを受信する(S44)。
【0113】
そして、受信側装置130は、受信した暗号化データを、ステップS41で記憶部131に記憶した共通鍵で復号化して復号化データを生成し(S45)、復号化データを記憶部131に記憶する(S46)。
【0114】
以上に記載した実施形態においては、正規分布に沿うように乱数の値を生成したが、このような態様に限定されず、正規分布以外のガンマ分布、指数分布などの他の確率分布にも適用可能である。
【0115】
例えば、確率密度関数f(x)が以下の式で与えられるガンマ分布を用いてよい。
【数26】

【0116】
ここで、α>0かつβは共に定数である。
【0117】
また、以上に記載した実施形態においては、乱数生成部119が生成した乱数の値でエラーベクトルを生成し、GGH暗号に適用し、暗号化プロトコルや鍵配送プロトコルなどの実現方法を示した。しかし、本手法は、GGH暗号に限定だけでなく、エラーベクトルや乱数を用いる他の公開鍵暗号(例えば、GGH暗号の特殊な実装形式であるPJH暗号など)にも適用できる。
【0118】
さらに、以上に記載した実施形態においては、乱数生成部119が生成したエラーベクトルをn行n列の秘密鍵と公開鍵を用いた公開鍵暗号へ適用した。しかし、本手法を適用する秘密鍵と公開鍵は、行と列の数が同じである必要はなく、m行n列またはn行m列からなる、秘密鍵または公開鍵を用いた公開鍵暗号にも適用できる(ただし、m≠nとする)。
【0119】
また、以上に記載した実施形態においては、公開鍵暗号への適用を記載した。しかし、本手法は共通鍵暗号や、グループ署名、秘密分散等の他の暗号系にも同様に適用できる。
【0120】
次に、本発明の第二の実施形態について説明する。ここで、第二の実施形態においては、第一の実施形態と比較して、送信側装置210及び受信側装置230が異なっているため、以下、これらの異なっている部分に関連する事項について説明する。
【0121】
なお、第二の実施形態においては、エラーベクトルを利用した暗号システムを用い、エラーベクトルの一意性から、暗号文の送付元を証明する技術を提供する。
【0122】
図11は、第二の実施形態における送信側装置210の概略図である。図示するように、送信側装置210は、記憶部211と、制御部216と、入力部121と、出力部122と、通信部123と、を備え、第一の実施形態と比較して、記憶部211及び制御部216が異なっているため、以下、これらについて説明する。
【0123】
記憶部211は、送信文記憶領域112と、公開鍵記憶領域113と、一時情報記憶領域114と、エラーベクトル記憶領域224と、を備え、第一の実施形態と比較して、エラーベクトル記憶領域224が異なっているため、以下、エラーベクトル記憶領域224について説明する。
【0124】
エラーベクトル記憶領域224には、暗号処理部118で生成されたエラーベクトルを特定する情報が格納される。
【0125】
制御部216は、全体制御部217と、暗号処理部118と、乱数生成部119と、関数処理部226と、を備え、第一の実施形態と比較して、全体制御部217及び関数処理部226が異なっているため、以下これらに関連する事項について説明する。
【0126】
全体制御部217は、送信側装置210での処理の全体を制御し、第一の実施形態の全体制御部117が行う処理と同様の処理を行うほか、暗号処理部118が生成したエラーベクトルをエラーベクトル記憶領域224に記憶する処理を行う。
【0127】
また、本実施形態における全体制御部217は、通信部123を介して、関数処理部226が生成したハッシュ値を受信側装置130に送信する処理を行う。
【0128】
関数処理部226は、予め定められたハッシュ関数を用いて、ハッシュ値を算出する処理を行う。
【0129】
図12は、受信側装置230の概略図である。図示するように、受信側装置230は、記憶部231と、制御部236と、入力部141と、出力部142と、通信部143と、を備え、第一の実施形態と比較して、記憶部231及び制御部236が異なっているため、以下これらに関連する事項について説明する。
【0130】
記憶部231は、秘密鍵記憶領域132と、公開鍵記憶領域133と、一時情報記憶領域134と、暗号文記憶領域245と、復号文記憶領域246と、を備え、第一の実施形態と比較して、暗号文記憶領域245及び復号文記憶領域246が異なっているため、以下、これらに関連する事項について説明する。
【0131】
暗号文記憶領域245には、送信側装置210から受信した暗号文を特定する情報が記憶される。
【0132】
復号文記憶領域246には、復号処理部139が復号した復号文を特定する情報が記憶される。
【0133】
制御部236は、全体制御部237と、鍵生成部138と、復号処理部239と、関数処理部248と、を備え、第一の実施形態と比較して、全体制御部237、復号処理部239及び関数処理部248が異なっているため、以下これらに関連する事項について説明する。
【0134】
全体制御部237は、受信側装置230での処理の全体を制御し、第一の実施形態と同様の処理を行うほか、送信側装置210より受信した暗号文を暗号文記憶領域245に記憶する処理を行う。
【0135】
また、全体制御部237は、復号処理部139で復号された復号文を復号文記憶領域246に記憶する処理を行う。
【0136】
本実施形態における復号処理部239は、第一の実施形態における復号処理部139と同様の処理を行うほか、公開鍵Bと復号文m’を掛け合わせた値と暗号文cの差分を計算(c−Bm’)することにより、エラーベクトルe’(=c−Bm’)を算出する処理を行う。
【0137】
関数処理部248は、予め定められたハッシュ関数を用いて、ハッシュ値を算出する処理を行う。
【0138】
図13は、GGH暗号における暗号化プロトコルを用い、暗号文の送信元を証明する処理を示すシーケンス図である。
【0139】
なお、図13のシーケンスの前提として、送信側装置210は、受信側装置230に暗号化した暗号文を既に送信済みであり、暗号文の作成時に利用したエラーベクトルは、送信側装置210のエラーベクトル記憶領域224に記憶されているものとする。
【0140】
また、受信側装置230は、送信側装置210から送信された暗号文と、暗号文から復号化した復号文と、をそれぞれ暗号文記憶領域245及び復号文記憶領域246に記憶しているものとする。
【0141】
なお、これらの状態は、第一の実施形態で行った処理により実現可能である。
【0142】
まず、送信側装置210の全体制御部217は、入力部121を介して、ハッシュ値の送信指示の入力を受け付ける(S50)。
【0143】
次に、送信側装置210の関数処理部226は、エラーベクトル記憶領域224に記憶されているエラーベクトルを取得し(S51)予め定められた暗号学的ハッシュ関数(SHA−1やMD5等)により、取得したエラーベクトルのハッシュ値を算出する(S52)。
【0144】
そして、送信側装置210の全体制御部217は、関数処理部226が算出したハッシュ値を、通信部123を介して、受信側装置230に送信する(S53)。
【0145】
次に、受信側装置230の全体制御部237は、通信部143を介して、ハッシュ値を受信し、一時情報記憶領域134に記憶する(S54)。
【0146】
そして、受信側装置230の全体制御部237が、入力部141を介して、暗号文の証明指示の入力を受け付けると(S55)、受信側装置230の復号処理部239は、公開鍵記憶領域113に記憶されている公開鍵B、暗号文記憶領域245に記憶されている暗号文c及び復号文記憶領域246に記憶されている復号文m’を取得し、公開鍵Bと復号文m’を掛け合わせた値と暗号文cの差分を計算(c−Bm’)した値をエラーベクトルe’(=c−Bm’)とし、一時情報記憶領域134に記憶する(S56)。
【0147】
そして、受信側装置230の関数処理部248は、エラーベクトルe’のハッシュ値を算出して一時情報記憶領域134に記憶する(S57)。
【0148】
そして、受信側装置230の全体制御部237は、ステップS54で受信したハッシュ値と、ステップS57で算出したハッシュ値と、を比較して、これらが一致する場合には、暗号文の送信元が送信側装置210であると判断し、これらが異なる場合には、暗号文の送信元が送信側装置210ではないと判断する(S58)。
【0149】
なお、暗号文の送信元を証明する処理については、図13での処理に限定されるものではなく、例えば、送信側装置210はエラーベクトルのハッシュ値を計算する処理(S52)を省き、エラーベクトルそのものを受信側装置230に送信するようにしてもよい。
このような場合、受信側装置230では、エラーベクトルのハッシュ値に代えてエラーベクトルを受信して(S54)、ステップS56で算出されたエラーベクトルe’と比較するようにすればよい。このときには、受信側装置230に関数処理部248は不要となる。
【0150】
また、例えば、受信側装置230は、エラーベクトルe’を先に計算しておいて、後から送られてくるエラーベクトルと比較するようにしてもよい。
【0151】
さらに、送信側装置210は、エラーベクトルのハッシュ値を計算しておき、エラーベクトルの替わりに、そのハッシュ値を記憶部211に格納するようにしてもよい。
【0152】
第一の実施形態では、送信側装置と受信側装置がデータの安全に共有する方法を開示したが、第二の実施形態では、受信側装置による、メッセージ送信元の送信側装置の特定を可能にし、なりすましの問題を解決することが可能になる。なお、なりすましとは、例えば、送信者装置がネットワーク経由で受信側装置に送信したメッセージを、異なる別の送信者装置が送信したメッセージのように受信側装置に見せかけることを指す。
【0153】
次に、第三の実施形態について説明する。ここで、第三の実施形態においては、第一の実施形態と比較して、送信側装置110が異なっているため、以下、これらの異なっている部分に関連する事項について説明する。
【0154】
第三の実施形態では、以下の文献などに方法が開示されている不正解読を防ぐよう、エラーベクトルの設定に、二つの確率分布を用いる方法について説明する。
【0155】
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).
第三の実施形態では、送信側装置310は、記憶部311と、制御部316と、入力部141と、出力部142と、通信部143と、を備えている。以下、第一の実施形態との相違点について説明する。
【0156】
記憶部311は、送信文記憶領域112と、公開鍵記憶領域113と、一時情報記憶領域114と、パラメータ記憶領域315を備え、第一の実施形態と比較して、パラメータ記憶領域315が異なっている。
【0157】
パラメータ記憶領域315には、乱数処理部119に与える統計処理の設定命令を特定する情報が記憶される。例えば、平均uの値と、乱数の値の数、乱数の値域を指す要素値、分布の数などがこれに当たる。
【0158】
制御部316は、全体制御部317と、暗号処理部118と、乱数生成部119と、を備え、第一の実施形態と比較して、全体制御部317が異なっている。
【0159】
全体制御部317は、送信側装置310での処理の全体を制御し、第一の実施形態の全体制御部117が行う処理と同様の処理を行うほか、パラメータ記憶領域315に記憶された統計処理に関する情報に従い、乱数生成部119が生成した乱数を一時記憶領域114に記憶する処理を行う。
【0160】
図14は、GGH暗号における暗号化プロトコルにおいて、送信側装置310の暗号処理部118におけるエラーベクトルeの生成処理を示すフローチャートである。
【0161】
図14に示すS1301からS1309の処理フローは、第一の実施形態における図7に示す処理フローのS11の処理を詳細化したものである。任意の正の整数s1、s2において、各要素値{-s1, -(s1-1),・・・s2-1,s2}の集合Sと、t>dである整数t,dにおいて、各要素値{-t, -(t-1), ・・・-(d-1),-d, d, d+1, t-1, t}の集合Tを用いて、エラーベクトルeの要素値を設定する。
【0162】
まず、送信側装置310の暗号処理部118は、集合Sと集合Tから選択する要素の数を設定する。格子の次元(公開鍵または秘密鍵の次元でもよい)がnである場合、集合Sから選択する要素数aと集合Tから選択する要素数bの間には、恒等式a + b = nが成り立つ。例えば、格子が100次元(n = 100)である場合には、a= 80、b = 20や、a=70、b=30でよい(S1301)。
【0163】
送信側装置310の暗号処理部118は、乱数生成部119に統計処理の設定命令を行う。乱数生成部119は、統計処理の設定命令に含まれる平均uの値と、乱数の値の数と、を統計処理の設定値として設定する(S1302)。
【0164】
暗号処理部118は、乱数生成部119に開始命令を行い、乱数生成部119が乱数rを生成する(S1303)。なお、生成する乱数rは、任意の確率分布に従う。乱数が一様分布に従う場合、ある区間内で全実数が同確率で現れる。例えば、区間が0以上1未満で設定された場合、0≦r<1を満たす乱数rを生成する。なお、S1303は、一回の処理で乱数rを一つ生成してもよいし、複数個を生成してもよい。乱数生成部119は、必要な乱数の値の生成が修了すると、終了通知を暗号処理部118に通知する。
【0165】
暗号処理部118は、生成された乱数の値rに基づき、任意の確率分布に従う、エラーベクトルの要素値eiを設定する。例えば、集合Sの一様分布であるように要素値eiの出現頻度を設定する場合、0≦r<1の区間における一様乱数rを用い、式ei = [r(s1+s2) - s2+0.5]を満たすeiを生成すればよい。また、集合Tの一様分布に従う場合、
式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を生成すればよい(S1304)。
【0166】
S1303と同様、S1304において、一回の処理でエラーベクトルの一つ分の要素値ei(ただし、i∈(1、・・・、n))を生成してもよいし、複数分を生成してもよい。
【0167】
暗号処理部118は、全ての要素値e1、・・・enを生成したかを確認する。例えば、iを1から始まる要素番号とし、S1304においてエラーベクトルeiを生成する度に、iを1ずつインクリメントし、i=nを満たせば、全ての要素値e1、・・・enが生成されたとみなしてよい。また、S1304において複数個のエラーベクトルeiを生成する場合は、iをインクリメントする数を変更すればよい。全ての要素値が生成されていればS1306へと進み、また生成されていない要素値があれば、S1303に戻る(S1305)。
【0168】
暗号処理部118はS1301からS1303と同様の手順で、乱数rを生成する(S1306)。
【0169】
暗号処理部118はS1306で生成した乱数rに基づき、エラーベクトルeiの要素番号iとエラーベクトルejの要素番号jを変更する。例えば、0≦r1, r2&#60;1の区間における一様乱数r1とr2を用い、式i = [nr1]と式j = [nr2]から、要素番号iと要素番号jを生成する(S1307)。S1304と同様、S1307は、一回の処理で二つのエラーベクトルの要素番号を交換してもよいし、まとめて三つ以上の要素番号を交換してもよい。
【0170】
要素番号の変更が一定回数を越えたかを判断する。例えば、kを1から始まる要素番号とし、S1307においてエラーベクトルの要素番号を交換する度に、kを1ずつインクリメントし、kがあるしきい値を越えれば、要素番号が十分にシャッフルされたとみなしてよい。要素番号が十分にシャッフルされていればS1309へと進み、また生成されていない要素値があれば、S1306に戻る(S1308)。
【0171】
第三の実施形態では、エラーベクトルの設定に、二つの確率分布を用いたが、これに限定せずに、二つ以上の任意の個数の確率分布を用いてエラーベクトルを生成してもよい。
【0172】
第一の実施形態では、一つの分布に従う乱数を用い、高い確率で、大きなノルムのエラーベクトルを利用する手段を開示した。第三の実施形態では、第一の実施形態と異なり、エラーベクトルの生成に、相対的に値の小さな分布と大きな分布を複数用い、ノルムの大きなエラーベクトルを、確実に利用可能となる。
【0173】
次に、第四の実施形態について説明する。ここで、第四の実施形態においては、第一の実施形態と比較して、受信側装置130が異なっているため、以下、これらの異なっている部分に関連する事項について説明する。
【0174】
第四の実施形態では、暗号文から平文に復号化する正常な処理において、従来のGGH暗号では修正できなかった誤りを修正し、正しく平文に復号化する方法を説明する。
【0175】
従来のGGH暗号では、復号化処理において、R−1e の全ての要素値を最近傍の整数に修正し、[R−1e]={0}nとするため、R−1eの全要素値が-0.5より大きく0.5より小さい必要があった。(以下の数式を参照)
【数27】

【0176】
そのため、[R−1e]≠{0}nのときには、T−1[R−1c] ≠mであり、暗号文cから平文mに正しく復号化できないという課題がある。そこで、[R−1e]≠{0}nの場合にも、正しく復号化する処理手順を以下に説明する。
【0177】
暗号文cから復号化したm’が、送信文mと同じ値であるためには、R (R−1c) ‐ m’ = eでなければならない。そこで、R ((R−1c) ‐ m’)の任意の要素値が確かにエラーベクトルeの要素値であるかを効率的に検証するシーケンスを示す。
【0178】
第四の実施形態では、受信側装置430は、記憶部431と、制御部436と、入力部141と、出力部142と、通信部143と、を備え、第一の実施形態との相違点について説明する。
【0179】
記憶部431は、秘密鍵記憶領域432と、公開鍵記憶領域433と、一時情報記憶領域434と、テーブル記憶領域435と、を備え、第一の実施形態と比較して、テーブル記憶領域435が異なっている。
【0180】
図16は、テーブル記憶領域435の概略図である。図示するように、誤差テーブル(1)、誤差テーブル(2)、成功値と、を備える。誤差テーブル(1)は、要素番号と、整数部と、少数部と、を備える。誤差テーブル(2)は、要素順を表す変数iと、要素番号と、を備える。成功値は、誤差テーブル(2)における変数iを指す情報、を記憶する。
【0181】
制御部436は、全体制御部137と、鍵生成部138と、復号処理部439と、を備え、第一の実施形態と比較して、復号処理部439が異なっている。
【0182】
復号処理部439は、テーブル記憶領域に記憶する情報を用い、送信側装置110から送られてきた暗号文を復号化する。
【0183】
図15は、GGH暗号における復号化プロトコルにおいて、受信側装置430の復号処理部439における処理を示すフローチャートである。
【0184】
図15に示すS1403からS1425の処理フローは、第一の実施形態における図7に示す処理フローのS16の処理を詳細化したものである。
【0185】
既に、受信側装置2は、送信側装置1がネットワーク経由で送信した暗号文を受信しているものとする。
【0186】
復号処理部439は、誤差テーブル(2)における要素順を表す変数i(1512)を0に初期化する(S1403)。
【0187】
復号処理部439は、暗号文cに秘密鍵R−1を掛け合わせ、R−1cの要素ごとにバイナリ(2進数)表現で誤差テーブル(1)に記憶する(S1404)。誤差テーブル(1)には、昇順の要素番号(1502)ごとに、左側にある最上位ビットから、右側にある最下位ビットまで、各要素値を並べる。このとき、R−1cの整数部分は、誤差テーブル(1)の整数部に、小数部分は誤差テーブル(2)の少数部に記憶する。
【0188】
復号処理部439は、誤差テーブル(1)の少数部(1504)が0.25以上から0.75未満であるかを確認する(S1405)。すなわち、少数部(1504)の第一位と第二位が01または10であるかを検査する( (R−1c) m’の計算は必要ない)。
【0189】
以降では、誤差テーブル(1)の少数部(1504)をベクトルe’で表し、ベクトルe’の各要素値は要素番号jを用いてej’で表す。
【数28】

【0190】
S1405において、該当するR-1cの要素が存在した場合、[R−1e]≠{0}となり、復号化が失敗する可能性が高い。ベクトルe’の要素番号jと数値0を誤差テーブル(2)に記憶する。また、復号処理部439は、誤差テーブル(2)1511に格納した要素番号j(1513)の個数をカウントし、h=2−1の式から、閾値hをメモリユニット23に格納する(たとえば、要素番号j=1,10、100を格納したとき、要素番号jの個数は3、閾値h=7(=2−1)である。)。(S1406)
【0191】
h=0のとき、変数iを成功値(1521)として記憶し、S1414へと進む(S1407)。
【0192】
復号処理部439は、誤差テーブル(2)の変数i(1512)を1つインクリメントする(S1408)。
【0193】
復号処理部439は、誤差テーブル(1)1501より、ベクトルe’をロードする(S1409)。
【0194】
復号処理部439は、要素番号j(1513)をロードする。また、誤差テーブル(2)1511の行(変数i(1512)に対応)と列(要素番号j(1513))から、値si,jをロードする(S1410)。
【0195】
演算ユニットは、要素番号j(1513)と値si,jを用い、ベクトルe’の要素値ej’を次式に従って、更新する(S1411)。
【数29】

【0196】
復号処理部439は、ベクトルe’に秘密鍵Rを掛け合わせて得られるベクトルが、全て適切なエラーベクトルの要素値であるかを検証する。例えば、第三の実施形態では、エラーベクトルeの要素値が{-s1, -(s1-1),・・・s2-1,s2}の集合Sまたは、{-t, -(t-1), ・・・-(d-1),-d, d, d+1, t-1, t}の集合T(ただし、t>d)に含まれているかを確認する。Re’の全ての要素が適切なエラーベクトルの要素値であれば、変数iを成功値(1521)として記憶する(S1412)。
【0197】
復号処理部439は、変数i(1512)が閾値hと値を比較し、変数i(1512)が閾値hの値と等しい、または大きければ、S1418へ進む(S1414)。
【0198】
復号処理部439は、S1410でロードとした値si,jのうち一つを、0から1に更新する(S1415)。
【0199】
復号処理部439は、誤差テーブル(2)における変数i(1512)を1つインクリメントする(S1416)。
【0200】
復号処理部439は、変数i(1512)を行、要素番号j(1513)を列とするsi,jを誤差テーブル(2)1511に追加する。S1407へ戻る(S1417)。
【0201】
復号処理部439は、成功値iを1つロードする(S1418)。
【0202】
復号処理部439は、誤差テーブル(2)1511の行(成功値iに対応)と列(要素番号j(1513))から、値si,jをロードする(S1419)。
【0203】
演算ユニットは、要素番号j(1513)と値si,jを用い、ベクトルe’の要素値ej’を次式に従って、更新する(S1420)。
【数29】

【0204】
復号処理部439は、誤差テーブル(1)1501の整数部(1503)をロードする。ロードした整数部(1503)をベクトルm’とし、ベクトルm’の各要素は要素番号j(1513)を用いてmj’で表す(S1421)。
【0205】
復号処理部439は、次式により、ベクトルm’を更新する(S1422)。
【数30】

【0206】
復号処理部439は、メモリユニット23に格納された秘密鍵Tと暗号文cをロードする(S1423)。
【0207】
復号処理部439は、c−T-1m’を計算する(S1424)。
【0208】
復号処理部439は、Re’を計算し、S1424で計算した(c−T-1m’)と値が等しいかを検証する。値が等しくなければ、S1419でロードした成功値iを削除し、S1419へ戻る。値が等しければ、エラーベクトルが正しく推定できているので、S1422で得たベクトル’を送信文とみなす(S1425)。
【0209】
第四の実施形態では、誤差テーブル(1)1501の選出に、R-1cの少数部(1504)が0.25以上から0.75未満であるかを確認した。しかし、本手法は、0.25以上から0.75未満という特定値である必要はなく、他の値でもかまわない。
【0210】
第四の実施形態では、変数i(1512)の値が更新される度に、誤差テーブル(2)1511の全ての要素番号j(1513)に対応する値si,jを随時追加した。しかし、変更のあったsi,jのみ追加し、他の値si,jは更新前の変数i(1512)における値si,jを参照するように変更してもよい。
【0211】
第四の実施形態では、変数i(1512)の値が更新される度に、誤差テーブル(2)1511に新たな列を追加した。しかし、誤差テーブル(2)1511の以前の列に新たなsi,jを上書きするように変更してもよい。
【0212】
第四の実施形態では、S1411およびS1420において、変数i(1512)ごとに、全ての要素番号j(1513)を用いてベクトルe’を再計算した。しかし、以前に用いたベクトルe’を再利用し、値に変更があった要素番号j(1513)のsi,jのみを利用し、ベクトルe’を再計算するように変更してもよい。
【0213】
第四の実施形態では、R−1cの要素番号の昇順に誤差テーブル(1)を作成した。しかし、誤差テーブル(1)は、降順または順不同に作成してもかまわない。
【0214】
第四の実施形態では、R−1cの要素がバイナリ表現(2進数表現)である場合を示した。しかし、本手法はバイナリ表現に縛られるものではない。例えば、IEEE-754で規定される単精度表現(符号部、指数部、仮数部の3つで構成)や、倍精度表現等でも同様に適用できる。
【0215】
第四の実施形態では、変数iの昇順に誤差テーブル(2)を作成した。しかし、誤差テーブル(2)は、降順または順不同に作成してもかまわない。
【0216】
第四の実施形態では、各処理が逐次的に実施されるものとして、記述した。しかし、本処理は、処理手順や処理形態に依存するものではない。例えば、各作業を並列に処理する事が可能である。また、処理手順を入れ替えてもかまわない。
【0217】
第四の実施形態では、基本的に、演算ユニットが作成したデータをいったん記憶し、必要になるたびに、テーブル記憶領域435からデータをロードするよう処理手順を記述した。しかし、本処理は、記述した処理フローに依存するものではない。例えば、復号処理部が保持するデータなどで計算可能な場合、データの記憶や、データのロードを省いてもかまわない。
【0218】
第四の実施形態では、第一の実施形態におけるGGH復号化の復号化誤りの確率をより低下させることが可能になる。
【符号の説明】
【0219】
100:暗号システム、110,310:送信側装置、111,211,311:記憶部、112:送信文記憶領域、113:公開鍵記憶領域、114:一時情報記憶領域、224:エラーベクトル記憶領域、315:パラメータ記憶領域、435:テーブル記憶領域、116:制御部、117,217:全体制御部、118:暗号処理部、119:乱数生成部、226:関数処理部、121:入力部、122:出力部、123:通信部、130,430:受信側装置、131,231,431:記憶部、132:秘密鍵記憶領域、133:公開鍵記憶領域、134:一時情報記憶領域、245:暗号文記憶領域、246:復号文記憶領域、136,236:制御部、137,237:全体制御部、138:鍵生成部、139:復号処理部、248:関数処理部、141:入力部、142:出力部、143:通信部、1501:誤差テーブル(1)、1502:誤差テーブル(2)、1521:成功値。

【特許請求の範囲】
【請求項1】
GGH暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置であって、
予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、
前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、
を行う制御部を備える
ことを特徴とする暗号化装置。
【請求項2】
請求項1に記載の暗号化装置であって、
前記制御部は、
前記乱数生成処理として、予め設定された平均の値及び分散の値で特定される確率分布に沿うように、前記乱数の値を生成する
ことを特徴とする暗号化装置。
【請求項3】
請求項2に記載の暗号化装置であって、
前記制御部は、
前記乱数生成処理で生成された乱数の値から算出される平均の値が、予め設定された平均の値に対して予め定められた閾値の範囲内となり、かつ、前記乱数生成処理で生成された乱数の値から算出される分散の値が、予め設定された分散の値に対して予め定められた閾値の範囲内となるように、前記乱数の値を生成する
ことを特徴とする暗号化装置。
【請求項4】
請求項1から3の何れか一項に記載の暗号化装置であって、
前記制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルを前記復号化装置に送信する処理と、を行うことで、
前記復号化装置において、前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、前記暗号化装置から送られてきたエラーベクトルと比較することで、送信元の検証を行うことができるようにしたこと、
を特徴とする暗号化装置。
【請求項5】
請求項1から3の何れか一項に記載の暗号化装置であって、
前記制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルのハッシュ値を前記復号化装置に送信する処理と、を行うことで、
前記復号化装置において、前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、算出したエラーベクトルのハッシュ値を算出する処理と、前記暗号化装置から送られてきたエラーベクトルのハッシュ値と比較することで、送信元の検証を行うことができるようにしたこと、
を特徴とする暗号化装置。
【請求項6】
コンピュータを、GGH暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置として機能させるプログラムであって、
前記コンピュータを、
予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、
前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、
を行う制御手段として機能させる
ことを特徴とするプログラム。
【請求項7】
請求項6に記載のプログラムであって、
前記制御手段に、
前記乱数生成処理として、予め設定された平均の値及び分散の値で特定される確率分布に沿うように、前記乱数の値を生成させる
ことを特徴とするプログラム。
【請求項8】
請求項7に記載のプログラムであって、
前記制御手段に、
前記乱数生成処理で生成された乱数の値から算出される平均の値が、予め設定された平均の値に対して予め定められた閾値の範囲内となり、かつ、前記乱数生成処理で生成された乱数の値から算出される分散の値が、予め設定された分散の値に対して予め定められた閾値の範囲内となるように、前記乱数の値を生成させる
ことを特徴とするプログラム。
【請求項9】
コンピュータを、GGH暗号における鍵情報を用いて、暗号文を復号する復号化装置として機能させるプログラムであって、
前記コンピュータを、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出する処理と、
前記暗号化装置から送られてきたエラーベクトルと比較することで、送信元を検証する処理と、を行う制御手段として機能させる
ことを特徴とするプログラム。
【請求項10】
コンピュータを、GGH暗号における鍵情報を用いて、暗号文を復号する復号化装置として機能させるプログラムであって、
前記コンピュータを、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、算出したエラーベクトルのハッシュ値を算出する処理と、
前記暗号化装置から送られてきたエラーベクトルのハッシュ値と比較することで、送信元の検証を行う処理と、を行う制御手段として機能させる
ことを特徴とするプログラム。
【請求項11】
GGH暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置と、GGH暗号における鍵情報を用いて、前記暗号文を復号する復号化装置と、を備える暗号システムであって、
前記暗号化装置は、
予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理と、
前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理と、
を行う制御部を備える
ことを特徴とする暗号システム。
【請求項12】
請求項11に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記乱数生成処理として、予め設定された平均の値及び分散の値で特定される確率分布に沿うように、前記乱数の値を生成する
ことを特徴とする暗号システム。
【請求項13】
請求項12に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記乱数生成処理で生成された乱数の値から算出される平均の値が、予め設定された平均の値に対して予め定められた閾値の範囲内となり、かつ、前記乱数生成処理で生成された乱数の値から算出される分散の値が、予め設定された分散の値に対して予め定められた閾値の範囲内となるように、前記乱数の値を生成する
ことを特徴とする暗号システム。
【請求項14】
請求項11から13の何れか一項に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルを前記復号化装置に送信する処理と、を行い、
前記復号化装置は、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出する処理と、前記暗号化装置から送られてきたエラーベクトルと比較することで、送信元を検証する処理と、を行う制御部を備える
ことを特徴とする暗号システム。
【請求項15】
請求項11から13の何れか一項に記載の暗号システムであって、
前記暗号化装置の制御部は、
前記暗号文を復号化装置に送信する処理と、
前記暗号文の生成に使用したエラーベクトルのハッシュ値を前記復号化装置に送信する処理と、を行い、
前記復号化装置は、
前記暗号文から、前記暗号文を復号した復号文に前記鍵情報を掛け合わせた値を減算することで、エラーベクトルを算出し、算出したエラーベクトルのハッシュ値を算出する処理と、前記暗号化装置から送られてきたエラーベクトルのハッシュ値と比較することで、送信元の検証を行う処理と、を行う制御部を備える
ことを特徴とする暗号システム。
【請求項16】
請求項14または15いずれか一に記載の暗号システムであって、
前記復号化装置は、GGH暗号における鍵情報に、前記暗号文を掛け合わせて、前記復号文を生成し、
前記復号化装置の前記制御部は、
前記暗号文から前記エラーベクトルを特定する誤差テーブルを作成する処理と、
前記鍵情報と前記誤差テーブルに格納された値とを掛け合わせて前記エラーベクトルを特定する処理と、を行う
ことを特徴とする暗号システム。
【請求項17】
GGH暗号における鍵情報に、暗号化の対象となるデータを掛け合わせて、エラーベクトルを加算することで、当該データを暗号化した暗号文を生成する暗号化装置が行う暗号化方法であって、
前記暗号化装置の制御部が、予め定められた値から離れると、出現確率が低くなるように乱数の値を生成する乱数生成処理を行う過程と、
前記暗号化装置の制御部が、前記乱数の値を要素値としてエラーベクトルを生成するエラーベクトル生成処理を行う過程と、
を備える
ことを特徴とする暗号化方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate


【公開番号】特開2011−2810(P2011−2810A)
【公開日】平成23年1月6日(2011.1.6)
【国際特許分類】
【出願番号】特願2010−33066(P2010−33066)
【出願日】平成22年2月18日(2010.2.18)
【出願人】(000005108)株式会社日立製作所 (27,607)
【Fターム(参考)】