(57)【要約】【課題】接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるような接頭一致保存型暗号であって、平文に対する暗号文が従来ほど長くない暗号に対応した暗号化装置を提供する。【解決手段】平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備える。【選択図】図２−Ａ
2012141554.tif 000002
【特許請求の範囲】
【請求項１】
平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置。
【請求項２】
請求項１に記載の暗号化装置であって、
前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とする暗号化装置。
【請求項３】
請求項１又は２に記載の暗号化装置であって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
を備え、
第１の擬似ランダム信号生成部は、秘密鍵を基に、第１の擬似ランダム信号を生成し、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部は、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と平文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部に入力されたビットとを基に、第ｉの擬似ランダム信号を生成し、
第ｉのビット抽出部は、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出し、
第ｉの排他的論理和計算部は、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、平文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とする暗号化装置。
【請求項４】
暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置。
【請求項５】
請求項４に記載の復号装置であって、
前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とする復号装置。
【請求項６】
請求項４又は５に記載の復号装置であって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
を備え、
第１の擬似ランダム信号生成部は、秘密鍵を基に、第１の擬似ランダム信号を生成し、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部は、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と暗号文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットを復号することにより得た平文の所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部から出力されたビットとを基に、第ｉの擬似ランダム信号を生成し、
第ｉのビット抽出部は、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出し、
第ｉの排他的論理和計算部は、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、暗号文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とする復号装置。
【請求項７】
平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化するステップを有することを特徴とする接頭一致保存型の暗号化方法。
【請求項８】
暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号するステップを有することを特徴とする接頭一致保存型の復号方法。
【請求項９】
平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、接頭一致保存型の暗号化装置及び復号装置、それらの方法並びにそれらのプログラムに関する。
【背景技術】
【０００２】
データベースに登録されている情報の漏洩対策として、登録情報の暗号化が挙げられる。しかし、一般的な暗号方式を単純に用いると、データベースの利便性が大きく損なわれる。例えば暗号化されて登録されているデータに対し、範囲検索を行うことを考える。ここで、範囲検索とは、或る第１の値から或る第２の値の範囲にあるデータを検索することである。但し、第１の値と第２の値とは等しくてもよい。このとき、通常の暗号化方式を用いる場合には、或るデータが目的の範囲に含まれているかどうかの判断を、その或る元のデータを暗号化して得た暗号化データを基に、することできない。従って、通常の暗号化方式を用いる場合には、データが条件を満たしているかどうかの判断は出来ず、従って、範囲検索は困難になってしまう。暗号化されたデータのすべてを復号し、条件にあった値かどうかを確認することはできるが、データベース中に含まれている暗号文のすべてを復号する必要があり、非効率的である。
【０００３】
このような問題を解決する手段の１つとして、特殊な性質を持った暗号化方法を用いる方法が知られている。
【０００４】
暗号化処理が施される前のデータを平文とし、暗号化処理が施された後のデータを暗号文と呼ぶとする。非特許文献１では、接頭が一致している２つの平文にそれぞれ対応する２つの暗号文の接頭が、その２つの平文の接頭一致の程度に応じて一致するという性質を持った暗号化方法を利用し、暗号文の集合に対して範囲検索を行う方法が提案されている。
【０００５】
前述の性質を例を挙げて簡単に説明すると、一文字の平文が一文字に暗号化される場合であれば、平文0011の暗号文がABCDであるときには、平文0001の暗号文がABEFとなり、平文の文頭の00の一致に応じ、暗号文の文頭ABが一致するような性質を指す。
【０００６】
以上の例では、一文字の平文が一文字の暗号文に対応しているが、暗号文の一部分が、平文のどの箇所に対応しているかがわかるような方法であってもよい。
【０００７】
以降、このような暗号化方法を接頭一致性保存型の暗号化方法と呼ぶ。
【０００８】
非特許文献１に記載されている接頭一致性保存型の暗号化方法を用いて範囲検索を行う方法は以下の通りである。
【０００９】
［非特許文献１に記載の方法］
この方法では、範囲に含まれているかどうかの判定を接頭の一致の判定へと変換する方法によって、実行する。平文が0と1の2進表現で表された８ビット列であるとき、00100000以上であって01101111以下であることを判定することは、接頭が001、010、0110であるかどうかを判定するに等しい。
【００１０】
つまり、接頭一致保存型の暗号を用いている場合には、001を接頭に持つ平文、010を接頭に持つ平文、0110を接頭に持つ平文をそれぞれ暗号化し、その暗号化により得た３つの暗号文のうちの何れかの暗号文と接頭が等しい暗号文を範囲検索対象の暗号文集合から抽出することで、範囲検索を実行することができる。
【００１１】
つまり、接頭一致性保存型の暗号化方法によれば、復号処理を伴わないで暗号文集合からの範囲検索を可能とする。前述の説明では、一致判定が1ビット単位で行われていることを前提としている。しかし、一致判定が２ビット単位である接頭一致性保存型暗号を用いる場合であっても、先に挙げた範囲検索は行える。例えば、001が接頭である暗号文を検索したい場合ならば、接頭が0010,0011のいずれかである暗号文を検索すればよい。しかし、各暗号文について、多くの暗号文との接頭一致判定を行うことになり、処理が複雑化する。そのため、一致判定の単位は適切に設定できるのがよい。
【００１２】
従来、提案されてきた接頭一致保存型の暗号としては、非特許文献２、非特許文献３、非特許文献４に記載されている暗号方式が挙げられる。以下で、これらのそれぞれについて説明を記載する。
【００１３】
非特許文献２に記載の方法
f_i()を、iビット列を入力とし、1ビットを出力する関数とする。なお、f_0は入力無しで、1ビットを出力する定数関数である。
【００１４】
このとき、ｎビット列m_1,m_2,...,m_nを以下のように暗号化する。(ex)を排他的論理和の２項演算子として用いる。
【００１５】
［暗号化方法］
1. i=1,2,...,nについて、c_i=m_i(ex)f_{i-1}を計算する。
【００１６】
2. c_1,...,c_nを出力する。
【００１７】
［復号方法］
1. i=1,2,...,nについて、m_i=c_i(ex)f_{i-1}を計算する。
【００１８】
2. m_1,..., m_nを出力する。
【００１９】
非特許文献２において、f_iは、入力に対する出力を予測することが計算量的に困難な関数R()と入力の最下位ビットを出力する関数L()を用いて以下のように構成されている。なお、R()は予測を計算量的に困難にするため、ランダムなデータを補助入力として要する。このデータにより表される情報を秘密鍵とよび、入力がA、補助入力がBである場合、R(A;B)と表す。Bが暗号における秘密鍵となる。Aが空列のときは、R(;B)と書く。
【００２０】
f_0=L(R(;K))
f_i=L(R(a_1,a_2,...,a_i;K))
以上のような構成においては、iビット目の暗号文はf_{i-1}とiビット目の平文の排他的論理和で求められる。f_{i-1}は1ビット目からi-1ビット目までの入力によって定まるため、接頭がkビット一致している平文に対する暗号文は必ずkビット目までが等しくなる。その後はRに対する入力が異なるため、R()の性質により、まったく違った系列になる。
【００２１】
この方法においては、f_iを計算するために1ビット目からiビット目のすべてを用いていることが特徴的である。つまり、入力のビット長が長ければ長いほど、後半のビットの計算への入力が長くなる。一般に、入力が長くなればなるほど、計算は困難になり、処理に時間がかかる。したがって、後半の出力においても計算が容易に実行可能であるような方法が好ましい。
【００２２】
次に、非特許文献２に記載されているシステムの構成を図面を参照して説明する。
【００２３】
このシステムは、暗号化装置１００、復号装置２００を含む。
【００２４】
図１−Ａは、暗号化装置１００のブロック図である。暗号化装置１００の構成について、図１−Ａを参照して説明を行う。
【００２５】
暗号化装置１００は、第１乃至第ｎの擬似ランダム信号生成部１０１−１乃至１０１−ｎと、第１乃至第ｎのビット抽出部１０２−１乃至１０２−ｎと、第１乃至第ｎの排他的論理和回路１０３−１乃至１０３−ｎを含む。
【００２６】
また、暗号化装置１００は、ｎビットの平文を入力する。この平文をビット列m_1,m_2,...,m_nで表す。更に、暗号化装置１００は、秘密鍵Kを入力する。更に、暗号化装置１００は、ｎビットの暗号文を出力する。この暗号文をビット列c_1,c_2,...,c_nで表す。
【００２７】
図１−Ｂは、復号装置２００のブロック図である。復号装置２００の構成について、図１−Ｂを参照して説明を行う。
【００２８】
復号装置２００は、第１乃至第ｎの擬似ランダム信号生成部２０１−１乃至２０１−ｎと、第１乃至第ｎのビット抽出部２０２−１乃至２０２−ｎと、第１乃至第ｎの排他的論理和回路２０３−１乃至２０３−ｎを含む。
【００２９】
また、復号装置２００は、ｎビットの暗号文を入力する。この暗号文をビット列c_1,c_2,...,c_nで表す。更に、復号装置２００は、秘密鍵Kを入力する。更に、復号装置２００は、ｎビットの平文を出力する。この平文をビット列m_1,m_2,...,m_nで表す。
【００３０】
次に、暗号化装置１００の動作を、図１−Ａ及び図３を参照して説明する。
【００３１】
暗号化装置１００は、平文m_1,m_2,...,m_nと秘密鍵Kを入力する(ステップＡ１)。
【００３２】
次に、第１の擬似ランダム信号生成部１０１−１は、秘密鍵Kを入力して、これを用いて第１の擬似ランダム信号を生成する(ステップＡ２)。
【００３３】
次に、第１のビット抽出部１０２−１は、第１の擬似ランダム信号のうちの最下位ビットを抽出する(ステップＡ３)。
【００３４】
次に、第１の排他的論理和回路１０３−１は、第１のビット抽出部１０２−１の出力と平文の第１ビットm_1との排他的論理和を計算し、その排他的論理和を暗号文の第１ビットc_1として出力する(ステップＡ４)。
【００３５】
次に、ステップＡ５ＳからステップＡ５Ｅまでの間にあるステップを、ｉ＝２からｉ＝ｎまで繰り返す。
【００３６】
第ｉの擬似ランダム信号生成部１０１−ｉは、秘密鍵Kと平文の第１ビット乃至第（ｉ−１）ビットであるm_1乃至m_{i-1}を入力し、これらを用いて第ｉの擬似ランダム信号を生成する（ステップＡ６）。
【００３７】
次に、第ｉのビット抽出部１０２−ｉは、第ｉの擬似ランダム信号のうちの最下位ビットを抽出する（ステップＡ７）。
【００３８】
次に、第ｉの排他的論理和回路１０３−ｉは、第ｉのビット抽出部１０２−ｉの出力と平文の第ｉビットm_iとの排他的論理和を計算し、その排他的論理和を暗号文の第ｉビットc_iとして出力する（ステップＡ８）。
【００３９】
次に、復号装置２００の動作を、図１−Ｂ及び図４を参照して説明する。
【００４０】
復号装置２００は、暗号文c_1,c_2,...,c_nと秘密鍵Kを入力する(ステップＢ１)。
【００４１】
次に、第１の擬似ランダム信号生成部２０２−１は、秘密鍵を入力して、これを用いて第１の擬似ランダム信号を生成する（ステップＢ２）。
【００４２】
次に、第１のビット抽出部２０２−１は、第１の擬似ランダム信号のうちの最下位ビットを抽出する（ステップＢ３）。
【００４３】
次に、第１の排他的論理和回路２０３−１は、第１のビット抽出部２０２−１の出力と暗号文の第１ビットc_1との排他的論理和を計算し、その排他的論理和を平文の第１ビットm_1として出力する（ステップＢ４）。
【００４４】
次に、ステップＢ５ＳからステップＢ５Ｅまでの間にあるステップを、ｉ＝２からｉ＝ｎまで繰り返す。
【００４５】
第ｉの擬似ランダム信号生成部２０１−ｉは、秘密鍵Kと暗号の第１ビット乃至第（ｉ−１）ビットであるc_1乃至c_{i-1}を入力し、これらを用いて第ｉの擬似ランダム信号を生成する（ステップＢ６）。
【００４６】
次に、第ｉのビット抽出部２０２−ｉは、第ｉの擬似ランダム信号のうちの最下位ビットを抽出する（ステップＢ７）。
【００４７】
次に、第ｉの排他的論理和回路２０３−ｉは、第ｉのビット抽出部２０２−ｉの出力と平文の第ｉビットc_iとの排他的論理和を計算し、その排他的論理和を平文の第ｉビットm_iとして出力する（ステップＢ８）。
【００４８】
なお、以上の説明では、擬似ランダム生成部101の出力から最下位の１ビットを抽出しているが、複数ビットを抽出し、平文情報を一度に暗号化してもよい。つまり、例えば、擬似ランダム生成部101の出力から２ビットを抽出し、平文情報を２ビットずつ暗号化してもよい。
【００４９】
前述した例では、第ｉのビット抽出部１０２−ｉ、２０２−ｉは、それぞれ、第ｉの擬似ランダム生成部１０１−ｉ、２０１−ｉの出力から最下位ビットを抽出していたが、第ｉの擬似ランダム生成部１０１−ｉ、２０１−ｉの出力に対して決定的であればどのビットを抽出してもよい。つまり決まった位置のビットであればどの位置のビットを抽出してもよい。
【００５０】
複数のビットを抽出する場合、m_1,m_2,...,m_nと表した平文の各要素も同様に複数ビットとすればよい。復号についても同様である。すなわち、例えば、各段のビット抽出部の出力を２ビットとして、各段について排他的論理和回路を２ビット分設け、平文を構成するビットのうち２ビットずつを各段で暗号化してもよい。
【００５１】
非特許文献３及び非特許文献４に記載されている技術では、ビット長の長いデータを暗号化する場合でも、各処理単位毎の計算量が一定であるが、処理単位が６４ビットや１２８ビットのような大きなサイズに定まっており、柔軟に設定できない。従って、前述したように、範囲検索に用いる場合には一致判定の負荷がかなり大きくなる。
【００５２】
特許文献１に記載の技術は、暗号化データの一部を他の部分を生成するために利用する。しかし、暗号化データの一部を生成する過程での中間データを他の部分を生成するために利用することはない。また、接頭一致保存型の暗号には対応していない。
【先行技術文献】
【特許文献】
【００５３】
【特許文献１】特開２００５−２０２０４８号公報
【非特許文献】
【００５４】
【非特許文献１】Jun. Li, and Edward. Omiecinski. Efficiency and Security Trade-Off in Supporting Range Queries on Encrypted Databases. pp. 69-83. DBSec 2005:
【非特許文献２】Jun. Xu, Jinliang. Fan, Mostafa. H. Ammar, and Sue. B. Moon. Prefix-preserving IP address anonymization: measurement-based security evaluation and a new cryptography-based scheme. In Proceedings of the 10th IEEE International Conference on Network Protocols
【非特許文献３】M. Bellare, A. Boldyreva, L. R. Knudsen, and C. Namprempre. Online ciphers and the Hash-CBC construction.(http://cseweb.ucsd.edu/~mihir/papers/olc.pdf)
【非特許文献４】Mridul Nandi: Two New Efficient CCA-Secure Online Ciphers: MHCBC and MCBC. INDOCRYPT 2008: 350-362
【発明の開示】
【発明が解決しようとする課題】
【００５５】
通常の接頭一致保存型暗号には、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるものは知られていなかった。
【００５６】
また、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるような接頭一致保存型暗号は、平文に対して暗号文が長かった。
【００５７】
そこで、本発明は、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるような接頭一致保存型暗号であって、平文に対する暗号文が従来ほど長くない暗号に対応した暗号化装置及び復号装置、暗号化方法及び復号方法並びに暗号化プログラム及び復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【００５８】
本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置が提供される。
【００５９】
また、本発明によれば、暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置が提供される。
【００６０】
更に、本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化するステップを有することを特徴とする接頭一致保存型の暗号化方法が提供される。
【００６１】
更に、本発明によれば、暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号するステップを有することを特徴とする接頭一致保存型の復号方法が提供される。
【００６２】
更に、本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置としてコンピュータを機能させるためのプログラムが提供される。
【００６３】
更に、本発明によれば、暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置としてコンピュータを機能させるためのプログラムが提供される。
【発明の効果】
【００６４】
本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えるので、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるような接頭一致保存型暗号であって、平文に対する暗号文が従来ほど長くない暗号に対応することができる。
【図面の簡単な説明】
【００６５】
【図１−Ａ】非特許文献２に記載されている暗号化装置の実施の形態を示すブロック図である。
【図１−Ｂ】非特許文献２に記載されている復号装置の実施の形態を示すブロック図である。
【図２−Ａ】本発明による暗号化装置の実施の形態を示すブロック図である。
【図２−Ｂ】本発明による復号装置の実施の形態を示すブロック図である。
【図３】図１−Ａに示す暗号化装置の実施の形態の動作の例を示すフローチャートである。
【図４】図１−Ｂに示す復号装置の実施の形態の動作の例を示すフローチャートである。
【図５】図２−Ａに示す暗号化装置の実施の形態の動作の例を示すフローチャートである。
【図６】図２−Ｂに示す復号装置の実施の形態の動作の例を示すフローチャートである。
【図７】図２−Ａ及び図２−Ｂに示す装置として機能するコンピュータの構成を示すブロック図である。
【発明を実施するための形態】
【００６６】
以下、図面を参照して本発明を実施するための形態について詳細に説明する。
【００６７】
本実施形態では、非特許文献２の方法と異なり、以下のような方法で、暗号化と復号を行う。二つのデータAとBについて、A｜｜Bと書いて、データAとBのビット連結を表す。
【００６８】
まず、以下のような関数g_iをR()を用いて構成する。
【００６９】
g_0=R(;K)
g_i=R(g_{i-1}｜｜m_{i-1};K)
［暗号化方法］
1. i=1,2,...,nについて、c_i=m_i(ex)L(g_{i-1})を計算する。
【００７０】
2. c_1,...,c_nを出力する。
【００７１】
［復号方法］
1. i=1,2,...,nについて、m_i=c_i(ex)L(g_{i-1})を計算する。
【００７２】
2. m_1,...,m_nを出力する。
【００７３】
以上のような構成においては、iビット目の暗号文はg_{i-1}の最下位ビットとiビット目の平文m_iの排他的論理和で求められる。また、g_0は秘密鍵Kによって決まる。従って、g_iはg_{i-1}とm_iと秘密鍵Kによって定まる。したがって、m_1からm_kまでが一致している場合、g_0からg_iまでが一致する。したがって、接頭がxビット一致している平文に対する暗号文は必ずxビット目までが等しくなる。m_{i-1}までが一致しており、m_iが異なっている場合、R()の性質により、g_i以降の系列がまったく違った系列となる。
【００７４】
この方法においては、g_iを計算するためには、g_{i-1}とm_iと秘密鍵を要する。つまり、入力のビット長の長さにかかわらず、g_iの計算量は定まる。したがって、後半の暗号文の計算も前半と同様の演算量で実行可能である。
【００７５】
このようにして、通常の方式の問題を解決する。
【００７６】
本実施形態によるシステムは、暗号化装置３００、復号装置４００を含む。
【００７７】
図２−Ａは、暗号化装置３００の実施の形態のブロック図である。暗号化装置３００の構成について、図２−Ａを参照して説明を行う。
【００７８】
暗号化装置３００は、第１乃至第ｎの擬似ランダム生成部３０１−１乃至３０１−ｎと、第１乃至第のビット抽出部３０２−１乃至３０２−ｎと、第１乃至第ｎの排他的論理和回路３０３−１乃至３０３−ｎと、第１乃至第（ｎ−１）のビット記憶部３０４−１乃至３０４−（ｎ−１）を含む。
【００７９】
また、暗号化装置３００は、ｎビットの平文を入力する。この平文をビット列m_1,m_2,...,m_nで表す。更に、暗号化装置３００は、秘密鍵Kを入力する。更に、暗号化装置３００は、nビットの暗号文を出力する。この暗号文をビット列c_1,c_2,...,c_nで表す。
【００８０】
なお、第１乃至第ｎの擬似ランダム生成部101は、秘密鍵なしで、入力に対する出力が予測が困難な関数を実現するものであればよい。
【００８１】
第１乃至第ｎのビット抽出部３０２−１乃至３０２−ｎはその入力から、一定のビット長の値を決定的に出力する関数を実現するものであればよい。
【００８２】
図２−Ａでは、暗号化装置３００は、複数の擬似ランダム信号生成部３０１−１乃至３０１−ｎと、複数のビット抽出部３０２−１乃至３０２−ｎを含むとしている。しかし、複数の擬似ランダム信号生成部３０１−１乃至３０１−ｎのうちの２以上が、１つの擬似ランダム信号生成部を時分割で利用することによって実現されてもよい。また、複数のビット抽出部３０２−１乃至３０２−ｎのうちの２以上が、１つのビット抽出部を時分割で利用することによって実現されてもよい。
【００８３】
図２−Ｂは復号装置４００の実施の形態のブロック図である。復号装置４００の構成について、図２−Ｂを参照して説明を行う。
【００８４】
復号装置４００は、第１乃至第ｎの擬似ランダム生成部４０１−１乃至４０１−ｎと、第１乃至第ｎのビット抽出部４０２−１乃至４０２−ｎと、第１乃至第ｎの排他的論理和回路４０３−１乃至４０３−ｎと第１乃至第（ｎ−１）のビット記憶部４０４−１乃至４０４−（ｎ−１）を含む。
【００８５】
また、復号装置４００は、nビットの暗号文を入力する。この暗号文をビット列c_1,c_2,...,c_nで表す。更に、復号装置４００は、秘密鍵Kを入力する。更に、復号装置４００は、nビットの平文を出力する。この平文をビット列m_1,m_2,...,m_nで表す。
【００８６】
第１乃至第ｎのビット抽出部４０２−１乃至４０２−ｎはその入力から、一定のビット長の値を決定的に出力する関数を実現するものであればよい。つまり、第１乃至第ｎのビット抽出部４０２−１乃至４０２−ｎは、他の部分との整合がとれていて、且つ、決まった位置の決まった数のビットであれば、どの位置のいかなる数のビットを抽出してもよい。
【００８７】
図２−Ｂでは、復号装置４００は、複数の擬似ランダム信号生成部４０１−１乃至４０１−ｎと、複数のビット抽出部４０２−１乃至４０２−ｎを含むとしている。しかし、複数の擬似ランダム信号生成部４０１−１乃至４０１−ｎのうちの２以上が、１つの擬似ランダム信号生成部を時分割で利用することによって実現されてもよい。また、複数のビット抽出部４０２−１乃至４０２−ｎのうちの２以上が、１つのビット抽出部を時分割で利用することによって実現されてもよい。
【００８８】
次に、暗号化装置３００の動作を、図２−Ａ及び図６を参照して説明する。
【００８９】
暗号化装置３００は、平文m_1,m_2,...,m_nと秘密鍵Kを入力する(ステップＣ１)。
【００９０】
次に、第１の擬似ランダム信号生成部３０１−１は、秘密鍵Kを入力して、これを用いて第１の擬似ランダム信号を生成する(ステップＣ２)。
【００９１】
次に、第１のビット記憶部３０４−１は、第１の擬似ランダム信号を記憶する（ステップＣ３）。
【００９２】
次に、第１のビット抽出部３０２−１は、第１の擬似ランダム信号のうちの最下位ビットを抽出する（ステップＣ４）。
【００９３】
次に、第１の排他的論理和回路３０３−１は、第１のビット抽出部３０２−１の出力と平文の第１ビットm_1との排他的論理和を計算し、その排他的論理和を暗号文の第１ビットc_1として出力する（ステップＣ５）。
【００９４】
次に、ステップＣ６ＳからステップＣ６Ｅまでの間にあるステップを、ｉ＝２からｉ＝ｎまで繰り返す。
【００９５】
第ｉの擬似ランダム信号生成部３０１−ｉは、秘密鍵Kと第（ｉ−１）のビット記憶部３０４−（ｎ−１）が記憶している第（ｉ−１）の擬似ランダム信号と平文の第（ｉ−１）ビットであるm_{i-1}を入力し、これらを用いて第ｉの擬似ランダム信号を生成する（ステップＣ７）。
【００９６】
次に、第ｉのビット記憶部３０４−ｉは、第ｉの擬似ランダム信号を記憶する（ステップＣ８）。
【００９７】
次に、第ｉのビット抽出部３０２−ｉは、第ｉの擬似ランダム信号のうちの最下位ビットを抽出する（ステップＣ９）。
【００９８】
次に、第ｉの排他的論理和回路３０３−ｉは、第ｉのビット抽出部３０２−ｉの出力と平文の第ｉビットm_iとの排他的論理和を計算し、その排他的論理和を暗号文の第ｉビットc_iとして出力する（ステップＣ１０）。
【００９９】
次に、復号装置４００の動作を、図２−Ｂ及び図６を参照して説明する。
【０１００】
復号装置４００は、暗号文c_1,c_2,...,c_nと秘密鍵Kを入力する(ステップＤ１)。
【０１０１】
次に、第１の擬似ランダム信号生成部４０１−１は、秘密鍵Kを入力して、これを用いて第１の擬似ランダム信号を生成する（ステップＤ２）。
【０１０２】
次に、第１のビット記憶部４０４−１は、第１の擬似ランダム信号を記憶する（ステップＤ３）。
【０１０３】
次に、第１のビット抽出部４０２−１は、第１の擬似ランダム信号のうちの最下位ビットを抽出する（ステップＤ４）。
【０１０４】
次に、第１の排他的論理和回路４０３−１は、第１のビット抽出部４０２−１の出力と暗号文の第１ビットc_1との排他的論理和を計算して、この計算により得た排他的論理和m_1を平文の第1ビットとして出力する（ステップＤ５）。
【０１０５】
次に、ステップＤ６ＳからステップＤ６Ｅまでの間にあるステップを、ｉ＝２からｉ＝ｎまで繰り返す。
【０１０６】
第ｉの擬似ランダム信号生成部４０１−ｉは、秘密鍵Kと第（ｉ−１）のビット記憶部４０４−（ｉ−１）が記憶している第（ｉ−１）の擬似ランダム信号と暗号文の第（ｉ−１）ビットであるc_{i-1}を入力し、これらを用いて第ｉの擬似ランダム信号を生成する（ステップＤ７）。
【０１０７】
次に、第ｉのビット記憶部４０４−ｉは、第ｉの擬似ランダム信号を記憶する（ステップＤ８）。
【０１０８】
次に、第ｉのビット抽出部４０２−ｉは、第ｉの擬似ランダム信号のうちの最下位ビットを抽出する（ステップＤ９）。
【０１０９】
次に、第ｉの排他的論理和回路４０３−ｉは、第ｉのビット抽出部４０２−ｉの出力と暗号文の第ｉビットc_iとの排他的論理和を計算し、その排他的論理和を平文の第ｉビットm_iとして出力する（ステップＤ１０）。
【０１１０】
なお、上記の説明では、第ｉのビット抽出部３０２−ｉ、４０２−ｉ（ｉ＝１〜ｎ）は、第ｉの擬似ランダム生成部３０１−ｉ、４０１−ｉの出力から最下位ビットを抽出しているが、複数ビットを抽出し、平文情報を一度に暗号化してもよい。
【０１１１】
つまり、第１乃至第ｎのビット抽出部３０２−１乃至３０２−ｎは、他の部分との整合がとれていて、且つ、決まった位置の決まった数のビットであれば、どの位置のいかなる数のビットを抽出してもよい。そして、第１乃至第ｎの排他的論理和回路３０３−１乃至３０３−ｎのそれぞれ３０３−ｉに含まれる排他的論理和ゲートの数をそれぞれに対応するビット抽出部３０２−ｉが出力するビット数に合わせる。各論理和ゲートは、平文を構成する１以上のビットのうち１ビットとビット抽出部３０２−ｉから出力される１以上のビットのうちの１ビットとの排他的論理和を計算する。第（ｉ＋１）の擬似ランダム信号生成部３０１−（ｉ＋１）は、第ｉの擬似ランダム信号と秘密鍵ｋの他に、平文を構成する１以上のビットのうち第ｉの排他的論理和回路３０３−ｉに入力された全てのビットを入力し、これらに基づいて、第（ｉ＋１）の擬似ランダム信号を生成する。
【０１１２】
同様に、第１乃至第ｎのビット抽出部４０２−１乃至４０２−ｎは、他の部分との整合がとれていて、且つ、決まった位置の決まった数のビットであれば、どの位置のいかなる数のビットを抽出してもよい。そして、第１乃至第ｎの排他的論理和回路４０３−１乃至４０３−ｎのそれぞれ４０３−ｉに含まれる排他的論理和ゲートの数をそれぞれに対応するビット抽出部４０２−ｉが出力するビット数に合わせる。各論理和ゲートは、暗号文を構成する１以上のビットのうち１ビットとビット抽出部４０２−ｉから出力される１以上のビットのうちの１ビットとの排他的論理和を計算する。第（ｉ＋１）の擬似ランダム信号生成部４０１−（ｉ＋１）は、第ｉの擬似ランダム信号と秘密鍵ｋの他に、平文を構成する１以上のビットのうち第ｉの排他的論理和回路４０３−ｉから出力された全てのビットを入力し、これらに基づいて、第（ｉ＋１）の擬似ランダム信号を生成する。
【０１１３】
図７に示す処理装置１０は、ＣＰＵ１１と、主記憶装置１２と、記録媒体１３と、データ蓄積部１４と、第１乃至第３のメモリ制御インターフェイス部１５−１乃至１５−３、第１乃至第２のＩ／Ｏインターフェイス部１６−１乃至１６−２、バス１８、入力装置２０及び出力装置を含む。
【０１１４】
記録媒体１３には、ＣＰＵ１１などを含む処理装置１０を暗号化装置３００又は復号装置４００として機能させるためのプログラムが記録されている。プログラムは、主記憶装置１２にロードされ、ＣＰＵ１１により読み込まれ、実行される。
【０１１５】
データ蓄積装置１４には、平文、暗号文及び秘密鍵が格納される。処理装置１０が暗号化装置３００として機能する時には、平文及び秘密鍵がデータ蓄積装置１４から読み出され、ＣＰＵ１１にロードされ、ＣＰＵ１１が生成した暗号文が、データ蓄積装置１４に格納される。処理装置１０が復号装置４００として機能する時には、暗号文及び秘密鍵がデータ蓄積装置１４から読み出され、ＣＰＵ１１にロードされ、ＣＰＵ１１が生成した平文が、データ蓄積装置１４に格納される。但し、秘匿性を考慮すれば、平文はデータ蓄積装置１４には蓄積されず、暗号化された通信路を介して入出力される。
【０１１６】
第ｉのビット記憶部３０４−ｉ、４０４−ｉ（ｉ＝１〜ｎ）は、プログラム制御されたＣＰＵ１１内のレジスタに設けてもよいし、主記憶装置１２に設けてもよいし、記録媒体１３に設けてもよいし、データ蓄積部１４に設けてもよい。
【０１１７】
第ｉの擬似ランダム生成部３０１−ｉ、４０１−ｉ、第ｉのビット抽出部３０２−ｉ、４０２−ｉ、第ｉの排他的論理和回路３０３−ｉ、４０３−ｉ（ｉ＝１〜ｎ）は、プログラム制御されたＣＰＵ１１のＡＬＵ(Arithmetic and Logic Unit)とレジスタなどにより構成される。「プログラム制御されたＣＰＵ」とは、プログラムを読み込んで実行しているＣＰＵを意味する。
【０１１８】
なお、データ蓄積装置１４は、処理装置１０内にある必要はなく、処理装置１０から独立して備えていてもよい。記録媒体１３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。
【０１１９】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１２０】
（付記１）
平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置。
【０１２１】
（付記２）
付記１に記載の暗号化装置であって、
前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とする暗号化装置。
【０１２２】
（付記３）
付記１又は２に記載の暗号化装置であって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
を備え、
第１の擬似ランダム信号生成部は、秘密鍵を基に、第１の擬似ランダム信号を生成し、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部は、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と平文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部に入力されたビットとを基に、第ｉの擬似ランダム信号を生成し、
第ｉのビット抽出部は、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出し、
第ｉの排他的論理和計算部は、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、平文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とする暗号化装置。
【０１２３】
（付記４）
付記３に記載の暗号化装置であって、
前記第１乃至第ｎの擬似ランダム信号生成部のうちの少なくとも２つは、１つの擬似ランダム信号生成部が時分割に動作することにより実現されることを特徴とする暗号化装置。
【０１２４】
（付記５）
付記３又は４に記載の暗号化装置であって、
前記第１乃至第ｎのビット抽出部のうちの少なくとも２つは、１つのビット抽出部が時分割に動作することにより実現されることを特徴とする暗号化装置。
【０１２５】
（付記６）
付記３乃至５の何れか１に記載の暗号化装置であって、
前記第１乃至第ｎの排他的論理和計算部のうちの少なくとも２つは、１つの排他的論理和計算部が時分割に動作することにより実現されることを特徴とする暗号化装置。
【０１２６】
（付記７）
暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置。
【０１２７】
（付記８）
付記７に記載の復号装置であって、
前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とする復号装置。
【０１２８】
（付記９）
付記７又は８に記載の復号装置であって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
を備え、
第１の擬似ランダム信号生成部は、秘密鍵を基に、第１の擬似ランダム信号を生成し、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部は、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と暗号文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットを復号することにより得た平文の所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部から出力されたビットとを基に、第ｉの擬似ランダム信号を生成し、
第ｉのビット抽出部は、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出し、
第ｉの排他的論理和計算部は、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、暗号文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とする復号装置。
【０１２９】
（付記１０）
付記９に記載の復号装置であって、
前記第１乃至第ｎの擬似ランダム信号生成部のうちの少なくとも２つは、１つの擬似ランダム信号生成部が時分割に動作することにより実現されることを特徴とする復号装置。
【０１３０】
（付記１１）
付記９又は１０に記載の復号装置であって、
前記第１乃至第ｎのビット抽出部のうちの少なくとも２つは、１つのビット抽出部が時分割に動作することにより実現されることを特徴とする復号装置。
【０１３１】
（付記１２）
付記９乃至１１の何れか１に記載の復号装置であって、
前記第１乃至第ｎの排他的論理和計算部のうちの少なくとも２つは、１つの排他的論理和計算部が時分割に動作することにより実現されることを特徴とする復号装置。
【０１３２】
（付記１３）
平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化するステップを有することを特徴とする接頭一致保存型の暗号化方法。
【０１３３】
（付記１４）
付記１３に記載の暗号化方法であって、
前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とする暗号化方法。
【０１３４】
（付記１５）
付記１３又は１４に記載の暗号化方法であって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
を用い、
第１の擬似ランダム信号生成部が、秘密鍵を基に、第１の擬似ランダム信号を生成するステップと、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部が、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と平文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部に入力されたビットとを基に、第ｉの擬似ランダム信号を生成するステップと、
第ｉのビット抽出部が、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出するステップと、
第ｉの排他的論理和計算部が、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、平文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算するステップと、
を有し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とする暗号化方法。
【０１３５】
（付記１６）
暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号するステップを有することを特徴とする接頭一致保存型の復号方法。
【０１３６】
（付記１７）
付記１６に記載の復号方法であって、
前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とする復号方法。
【０１３７】
（付記１８）
付記１６又は１７に記載の復号方法であって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
を用い、
第１の擬似ランダム信号生成部が、秘密鍵を基に、第１の擬似ランダム信号を生成するステップと、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部が、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と暗号文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットを復号することにより得た平文の所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部から出力されたビットとを基に、第ｉの擬似ランダム信号を生成するステップと、
第ｉのビット抽出部が、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出するステップと、
第ｉの排他的論理和計算部が、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、暗号文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算するステップと、
を有し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とする復号方法。
【０１３８】
（付記１９）
平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置としてコンピュータを機能させるためのプログラム。
【０１３９】
（付記２０）
付記１９に記載のプログラムであって、
前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とするプログラム。
【０１４０】
（付記２１）
付記１９又は２０に記載のプログラムであって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
としてコンピュータを機能させ、
第１の擬似ランダム信号生成部は、秘密鍵を基に、第１の擬似ランダム信号を生成し、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部は、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と平文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部に入力されたビットとを基に、第ｉの擬似ランダム信号を生成し、
第ｉのビット抽出部は、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出し、
第ｉの排他的論理和計算部は、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、平文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とするプログラム。
【０１４１】
（付記２２）
付記２１に記載のプログラムであって、
前記第１乃至第ｎの擬似ランダム信号生成部の機能のうちの少なくとも２つは、１つの擬似ランダム信号生成部の機能が時分割に動作することにより実現されることを特徴とするプログラム。
【０１４２】
（付記２３）
付記２１又は２２に記載のプログラムであって、
前記第１乃至第ｎのビット抽出部の機能のうちの少なくとも２つは、１つのビット抽出部の機能が時分割に動作することにより実現されることを特徴とするプログラム。
【０１４３】
（付記２４）
付記２１乃至２３の何れか１に記載のプログラムであって、
前記第１乃至第ｎの排他的論理和計算部の機能のうちの少なくとも２つは、１つの排他的論理和計算部の機能が時分割に動作することにより実現されることを特徴とするプログラム。
【０１４４】
（付記２５）
暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置としてコンピュータを機能させるためのプログラム。
【０１４５】
（付記２６）
付記２５に記載のプログラムであって、
前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とするプログラム。
【０１４６】
（付記２７）
付記２５又は２６に記載のプログラムであって、
第１乃至第ｎの擬似ランダム信号生成部と、
第１乃至第ｎのビット抽出部と、
第１乃至第ｎの排他的論理和計算部と、
としてコンピュータを機能させ、
第１の擬似ランダム信号生成部は、秘密鍵を基に、第１の擬似ランダム信号を生成し、
第ｉ（ｉ＝２、３、．．．、ｎ）の擬似ランダム信号生成部は、前記秘密鍵と第（ｉ−１）の擬似ランダム信号と暗号文に含まれる所定位置ｐｉ−１の所定数ｂｉ−１のビットを復号することにより得た平文の所定位置ｐｉ−１の所定数ｂｉ−１のビットであって第（ｉ−１）の排他的論理和計算部から出力されたビットとを基に、第ｉの擬似ランダム信号を生成し、
第ｉのビット抽出部は、第ｉの擬似ランダム信号に含まれるビットのうちの所定位置ｑｉの所定数ｂｉのビットを抽出し、
第ｉの排他的論理和計算部は、第ｉのビット抽出部により抽出された所定位置ｑｉの所定数ｂｉのビットの各々と、暗号文に含まれる所定位置ｐｉの所定数のビットｂｉの各々との排他的論理和を各々計算し、
第１乃至第ｎの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とするプログラム。
【０１４７】
（付記２８）
付記２７に記載のプログラムであって、
前記第１乃至第ｎの擬似ランダム信号生成部の機能のうちの少なくとも２つは、１つの擬似ランダム信号生成部の機能が時分割に動作することにより実現されることを特徴とするプログラム。
【０１４８】
（付記２９）
付記２７又は２８に記載のプログラムであって、
前記第１乃至第ｎのビット抽出部の機能のうちの少なくとも２つは、１つのビット抽出部の機能が時分割に動作することにより実現されることを特徴とするプログラム。
【０１４９】
（付記３０）
付記２７乃至２９の何れか１に記載のプログラムであって、
前記第１乃至第ｎの排他的論理和計算部の機能のうちの少なくとも２つは、１つの排他的論理和計算部の機能が時分割に動作することにより実現されることを特徴とするプログラム。
【産業上の利用可能性】
【０１５０】
平文の接頭一致性が保存される暗号を用いれば、データベースに登録されている暗号文に対し、範囲検索を行うことができる。
【０１５１】
本発明をデータベースの暗号化方法として用いれば、暗号化されるデータのデータ長が長い場合であっても効率的な暗号化処理が実行できるため、暗号化されたデータベースの範囲検索を効率的に実行することが可能となる。
【符号の説明】
【０１５２】
１０  処理装置
１１  ＣＰＵ
１２  主記憶装置
１３  記録媒体
１４  データ蓄積装置
１５  メモリ制御インターフェイス部
１６  Ｉ／Ｏインターフェイス部
２０  入力装置
３０  出力装置
１０１  擬似ランダム生成部
１０２  ビット抽出部
１００  暗号化装置
２００  復号装置
３００  暗号化装置
４００  復号装置
【図１−Ａ】
2012141554.tif 000003
【図１−Ｂ】
2012141554.tif 000004
【図２−Ａ】
2012141554.tif 000005
【図２−Ｂ】
2012141554.tif 000006
【図３】
2012141554.tif 000007
【図４】
2012141554.tif 000008
【図５】
2012141554.tif 000009
【図６】
2012141554.tif 000010
【図７】
2012141554.tif 000011