平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置。請求項1に記載の暗号化装置であって、前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とする暗号化装置。請求項1又は2に記載の暗号化装置であって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、を備え、第1の擬似ランダム信号生成部は、秘密鍵を基に、第1の擬似ランダム信号を生成し、第ii=2、3、...、nの擬似ランダム信号生成部は、前記秘密鍵と第i-1の擬似ランダム信号と平文に含まれる所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部に入力されたビットとを基に、第iの擬似ランダム信号を生成し、第iのビット抽出部は、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出し、第iの排他的論理和計算部は、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、平文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とする暗号化装置。暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置。請求項4に記載の復号装置であって、前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とする復号装置。請求項4又は5に記載の復号装置であって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、を備え、第1の擬似ランダム信号生成部は、秘密鍵を基に、第1の擬似ランダム信号を生成し、第ii=2、3、...、nの擬似ランダム信号生成部は、前記秘密鍵と第i-1の擬似ランダム信号と暗号文に含まれる所定位置pi-1の所定数bi-1のビットを復号することにより得た平文の所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部から出力されたビットとを基に、第iの擬似ランダム信号を生成し、第iのビット抽出部は、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出し、第iの排他的論理和計算部は、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、暗号文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とする復号装置。平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化するステップを有することを特徴とする接頭一致保存型の暗号化方法。暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号するステップを有することを特徴とする接頭一致保存型の復号方法。平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置としてコンピュータを機能させるためのプログラム。暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置としてコンピュータを機能させるためのプログラム。通常の接頭一致保存型暗号には、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるものは知られていなかった。また、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるような接頭一致保存型暗号は、平文に対して暗号文が長かった。そこで、本発明は、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるような接頭一致保存型暗号であって、平文に対する暗号文が従来ほど長くない暗号に対応した暗号化装置及び復号装置、暗号化方法及び復号方法並びに暗号化プログラム及び復号プログラムを提供することを目的とする。本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置が提供される。また、本発明によれば、暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置が提供される。更に、本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化するステップを有することを特徴とする接頭一致保存型の暗号化方法が提供される。更に、本発明によれば、暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号するステップを有することを特徴とする接頭一致保存型の復号方法が提供される。更に、本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置としてコンピュータを機能させるためのプログラムが提供される。更に、本発明によれば、暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置としてコンピュータを機能させるためのプログラムが提供される。本発明によれば、平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えるので、接頭の一致判定の単位が柔軟に設定可能で、処理単位毎の計算負荷が一定であるような接頭一致保存型暗号であって、平文に対する暗号文が従来ほど長くない暗号に対応することができる。以下、図面を参照して本発明を実施するための形態について詳細に説明する。本実施形態では、非特許文献2の方法と異なり、以下のような方法で、暗号化と復号を行う。二つのデータAとBについて、A||Bと書いて、データAとBのビット連結を表す。まず、以下のような関数giをRを用いて構成する。g0RgiR[暗号化方法]1i12nについて、cimiLを計算する。2c1cnを出力する。[復号方法]1i12nについて、miciLを計算する。2m1mnを出力する。以上のような構成においては、iビット目の暗号文はgi1の最下位ビットとiビット目の平文miの排他的論理和で求められる。また、g0は秘密鍵Kによって決まる。従って、giはgi1とmiと秘密鍵Kによって定まる。したがって、m1からmkまでが一致している場合、g0からgiまでが一致する。したがって、接頭がxビット一致している平文に対する暗号文は必ずxビット目までが等しくなる。mi1までが一致しており、miが異なっている場合、Rの性質により、gi以降の系列がまったく違った系列となる。この方法においては、giを計算するためには、gi1とmiと秘密鍵を要する。つまり、入力のビット長の長さにかかわらず、giの計算量は定まる。したがって、後半の暗号文の計算も前半と同様の演算量で実行可能である。このようにして、通常の方式の問題を解決する。本実施形態によるシステムは、暗号化装置300、復号装置400を含む。図2-Aは、暗号化装置300の実施の形態のブロック図である。暗号化装置300の構成について、図2-Aを参照して説明を行う。暗号化装置300は、第1乃至第nの擬似ランダム生成部301-1乃至301-nと、第1乃至第のビット抽出部302-1乃至302-nと、第1乃至第nの排他的論理和回路303-1乃至303-nと、第1乃至第n-1のビット記憶部304-1乃至304-n-1を含む。また、暗号化装置300は、nビットの平文を入力する。この平文をビット列m1m2mnで表す。更に、暗号化装置300は、秘密鍵Kを入力する。更に、暗号化装置300は、nビットの暗号文を出力する。この暗号文をビット列c1c2cnで表す。なお、第1乃至第nの擬似ランダム生成部101は、秘密鍵なしで、入力に対する出力が予測が困難な関数を実現するものであればよい。第1乃至第nのビット抽出部302-1乃至302-nはその入力から、一定のビット長の値を決定的に出力する関数を実現するものであればよい。図2-Aでは、暗号化装置300は、複数の擬似ランダム信号生成部301-1乃至301-nと、複数のビット抽出部302-1乃至302-nを含むとしている。しかし、複数の擬似ランダム信号生成部301-1乃至301-nのうちの2以上が、1つの擬似ランダム信号生成部を時分割で利用することによって実現されてもよい。また、複数のビット抽出部302-1乃至302-nのうちの2以上が、1つのビット抽出部を時分割で利用することによって実現されてもよい。図2-Bは復号装置400の実施の形態のブロック図である。復号装置400の構成について、図2-Bを参照して説明を行う。復号装置400は、第1乃至第nの擬似ランダム生成部401-1乃至401-nと、第1乃至第nのビット抽出部402-1乃至402-nと、第1乃至第nの排他的論理和回路403-1乃至403-nと第1乃至第n-1のビット記憶部404-1乃至404-n-1を含む。また、復号装置400は、nビットの暗号文を入力する。この暗号文をビット列c1c2cnで表す。更に、復号装置400は、秘密鍵Kを入力する。更に、復号装置400は、nビットの平文を出力する。この平文をビット列m1m2mnで表す。第1乃至第nのビット抽出部402-1乃至402-nはその入力から、一定のビット長の値を決定的に出力する関数を実現するものであればよい。つまり、第1乃至第nのビット抽出部402-1乃至402-nは、他の部分との整合がとれていて、且つ、決まった位置の決まった数のビットであれば、どの位置のいかなる数のビットを抽出してもよい。図2-Bでは、復号装置400は、複数の擬似ランダム信号生成部401-1乃至401-nと、複数のビット抽出部402-1乃至402-nを含むとしている。しかし、複数の擬似ランダム信号生成部401-1乃至401-nのうちの2以上が、1つの擬似ランダム信号生成部を時分割で利用することによって実現されてもよい。また、複数のビット抽出部402-1乃至402-nのうちの2以上が、1つのビット抽出部を時分割で利用することによって実現されてもよい。次に、暗号化装置300の動作を、図2-A及び図6を参照して説明する。暗号化装置300は、平文m1m2mnと秘密鍵Kを入力する。次に、第1の擬似ランダム信号生成部301-1は、秘密鍵Kを入力して、これを用いて第1の擬似ランダム信号を生成する。次に、第1のビット記憶部304-1は、第1の擬似ランダム信号を記憶するステップC3。次に、第1のビット抽出部302-1は、第1の擬似ランダム信号のうちの最下位ビットを抽出するステップC4。次に、第1の排他的論理和回路303-1は、第1のビット抽出部302-1の出力と平文の第1ビットm1との排他的論理和を計算し、その排他的論理和を暗号文の第1ビットc1として出力するステップC5。次に、ステップC6SからステップC6Eまでの間にあるステップを、i=2からi=nまで繰り返す。第iの擬似ランダム信号生成部301-iは、秘密鍵Kと第i-1のビット記憶部304-n-1が記憶している第i-1の擬似ランダム信号と平文の第i-1ビットであるmi1を入力し、これらを用いて第iの擬似ランダム信号を生成するステップC7。次に、第iのビット記憶部304-iは、第iの擬似ランダム信号を記憶するステップC8。次に、第iのビット抽出部302-iは、第iの擬似ランダム信号のうちの最下位ビットを抽出するステップC9。次に、第iの排他的論理和回路303-iは、第iのビット抽出部302-iの出力と平文の第iビットmiとの排他的論理和を計算し、その排他的論理和を暗号文の第iビットciとして出力するステップC10。次に、復号装置400の動作を、図2-B及び図6を参照して説明する。復号装置400は、暗号文c1c2cnと秘密鍵Kを入力する。次に、第1の擬似ランダム信号生成部401-1は、秘密鍵Kを入力して、これを用いて第1の擬似ランダム信号を生成するステップD2。次に、第1のビット記憶部404-1は、第1の擬似ランダム信号を記憶するステップD3。次に、第1のビット抽出部402-1は、第1の擬似ランダム信号のうちの最下位ビットを抽出するステップD4。次に、第1の排他的論理和回路403-1は、第1のビット抽出部402-1の出力と暗号文の第1ビットc1との排他的論理和を計算して、この計算により得た排他的論理和m1を平文の第1ビットとして出力するステップD5。次に、ステップD6SからステップD6Eまでの間にあるステップを、i=2からi=nまで繰り返す。第iの擬似ランダム信号生成部401-iは、秘密鍵Kと第i-1のビット記憶部404-i-1が記憶している第i-1の擬似ランダム信号と暗号文の第i-1ビットであるci1を入力し、これらを用いて第iの擬似ランダム信号を生成するステップD7。次に、第iのビット記憶部404-iは、第iの擬似ランダム信号を記憶するステップD8。次に、第iのビット抽出部402-iは、第iの擬似ランダム信号のうちの最下位ビットを抽出するステップD9。次に、第iの排他的論理和回路403-iは、第iのビット抽出部402-iの出力と暗号文の第iビットciとの排他的論理和を計算し、その排他的論理和を平文の第iビットmiとして出力するステップD10。なお、上記の説明では、第iのビット抽出部302-i、402-ii=1~nは、第iの擬似ランダム生成部301-i、401-iの出力から最下位ビットを抽出しているが、複数ビットを抽出し、平文情報を一度に暗号化してもよい。つまり、第1乃至第nのビット抽出部302-1乃至302-nは、他の部分との整合がとれていて、且つ、決まった位置の決まった数のビットであれば、どの位置のいかなる数のビットを抽出してもよい。そして、第1乃至第nの排他的論理和回路303-1乃至303-nのそれぞれ303-iに含まれる排他的論理和ゲートの数をそれぞれに対応するビット抽出部302-iが出力するビット数に合わせる。各論理和ゲートは、平文を構成する1以上のビットのうち1ビットとビット抽出部302-iから出力される1以上のビットのうちの1ビットとの排他的論理和を計算する。第i1の擬似ランダム信号生成部301-i1は、第iの擬似ランダム信号と秘密鍵kの他に、平文を構成する1以上のビットのうち第iの排他的論理和回路303-iに入力された全てのビットを入力し、これらに基づいて、第i1の擬似ランダム信号を生成する。同様に、第1乃至第nのビット抽出部402-1乃至402-nは、他の部分との整合がとれていて、且つ、決まった位置の決まった数のビットであれば、どの位置のいかなる数のビットを抽出してもよい。そして、第1乃至第nの排他的論理和回路403-1乃至403-nのそれぞれ403-iに含まれる排他的論理和ゲートの数をそれぞれに対応するビット抽出部402-iが出力するビット数に合わせる。各論理和ゲートは、暗号文を構成する1以上のビットのうち1ビットとビット抽出部402-iから出力される1以上のビットのうちの1ビットとの排他的論理和を計算する。第i1の擬似ランダム信号生成部401-i1は、第iの擬似ランダム信号と秘密鍵kの他に、平文を構成する1以上のビットのうち第iの排他的論理和回路403-iから出力された全てのビットを入力し、これらに基づいて、第i1の擬似ランダム信号を生成する。図7に示す処理装置10は、CPU11と、主記憶装置12と、記録媒体13と、データ蓄積部14と、第1乃至第3のメモリ制御インターフェイス部15-1乃至15-3、第1乃至第2のI/Oインターフェイス部16-1乃至16-2、バス18、入力装置20及び出力装置を含む。記録媒体13には、CPU11などを含む処理装置10を暗号化装置300又は復号装置400として機能させるためのプログラムが記録されている。プログラムは、主記憶装置12にロードされ、CPU11により読み込まれ、実行される。データ蓄積装置14には、平文、暗号文及び秘密鍵が格納される。処理装置10が暗号化装置300として機能する時には、平文及び秘密鍵がデータ蓄積装置14から読み出され、CPU11にロードされ、CPU11が生成した暗号文が、データ蓄積装置14に格納される。処理装置10が復号装置400として機能する時には、暗号文及び秘密鍵がデータ蓄積装置14から読み出され、CPU11にロードされ、CPU11が生成した平文が、データ蓄積装置14に格納される。但し、秘匿性を考慮すれば、平文はデータ蓄積装置14には蓄積されず、暗号化された通信路を介して入出力される。第iのビット記憶部304-i、404-ii=1~nは、プログラム制御されたCPU11内のレジスタに設けてもよいし、主記憶装置12に設けてもよいし、記録媒体13に設けてもよいし、データ蓄積部14に設けてもよい。第iの擬似ランダム生成部301-i、401-i、第iのビット抽出部302-i、402-i、第iの排他的論理和回路303-i、403-ii=1~nは、プログラム制御されたCPU11のALUとレジスタなどにより構成される。プログラム制御されたCPUとは、プログラムを読み込んで実行しているCPUを意味する。なお、データ蓄積装置14は、処理装置10内にある必要はなく、処理装置10から独立して備えていてもよい。記録媒体13は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。付記1平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置。付記2付記1に記載の暗号化装置であって、前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とする暗号化装置。付記3付記1又は2に記載の暗号化装置であって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、を備え、第1の擬似ランダム信号生成部は、秘密鍵を基に、第1の擬似ランダム信号を生成し、第ii=2、3、...、nの擬似ランダム信号生成部は、前記秘密鍵と第i-1の擬似ランダム信号と平文に含まれる所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部に入力されたビットとを基に、第iの擬似ランダム信号を生成し、第iのビット抽出部は、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出し、第iの排他的論理和計算部は、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、平文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とする暗号化装置。付記4付記3に記載の暗号化装置であって、前記第1乃至第nの擬似ランダム信号生成部のうちの少なくとも2つは、1つの擬似ランダム信号生成部が時分割に動作することにより実現されることを特徴とする暗号化装置。付記5付記3又は4に記載の暗号化装置であって、前記第1乃至第nのビット抽出部のうちの少なくとも2つは、1つのビット抽出部が時分割に動作することにより実現されることを特徴とする暗号化装置。付記6付記3乃至5の何れか1に記載の暗号化装置であって、前記第1乃至第nの排他的論理和計算部のうちの少なくとも2つは、1つの排他的論理和計算部が時分割に動作することにより実現されることを特徴とする暗号化装置。付記7暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置。付記8付記7に記載の復号装置であって、前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とする復号装置。付記9付記7又は8に記載の復号装置であって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、を備え、第1の擬似ランダム信号生成部は、秘密鍵を基に、第1の擬似ランダム信号を生成し、第ii=2、3、...、nの擬似ランダム信号生成部は、前記秘密鍵と第i-1の擬似ランダム信号と暗号文に含まれる所定位置pi-1の所定数bi-1のビットを復号することにより得た平文の所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部から出力されたビットとを基に、第iの擬似ランダム信号を生成し、第iのビット抽出部は、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出し、第iの排他的論理和計算部は、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、暗号文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とする復号装置。付記10付記9に記載の復号装置であって、前記第1乃至第nの擬似ランダム信号生成部のうちの少なくとも2つは、1つの擬似ランダム信号生成部が時分割に動作することにより実現されることを特徴とする復号装置。付記11付記9又は10に記載の復号装置であって、前記第1乃至第nのビット抽出部のうちの少なくとも2つは、1つのビット抽出部が時分割に動作することにより実現されることを特徴とする復号装置。付記12付記9乃至11の何れか1に記載の復号装置であって、前記第1乃至第nの排他的論理和計算部のうちの少なくとも2つは、1つの排他的論理和計算部が時分割に動作することにより実現されることを特徴とする復号装置。付記13平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化するステップを有することを特徴とする接頭一致保存型の暗号化方法。付記14付記13に記載の暗号化方法であって、前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とする暗号化方法。付記15付記13又は14に記載の暗号化方法であって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、を用い、第1の擬似ランダム信号生成部が、秘密鍵を基に、第1の擬似ランダム信号を生成するステップと、第ii=2、3、...、nの擬似ランダム信号生成部が、前記秘密鍵と第i-1の擬似ランダム信号と平文に含まれる所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部に入力されたビットとを基に、第iの擬似ランダム信号を生成するステップと、第iのビット抽出部が、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出するステップと、第iの排他的論理和計算部が、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、平文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算するステップと、を有し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とする暗号化方法。付記16暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号するステップを有することを特徴とする接頭一致保存型の復号方法。付記17付記16に記載の復号方法であって、前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とする復号方法。付記18付記16又は17に記載の復号方法であって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、を用い、第1の擬似ランダム信号生成部が、秘密鍵を基に、第1の擬似ランダム信号を生成するステップと、第ii=2、3、...、nの擬似ランダム信号生成部が、前記秘密鍵と第i-1の擬似ランダム信号と暗号文に含まれる所定位置pi-1の所定数bi-1のビットを復号することにより得た平文の所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部から出力されたビットとを基に、第iの擬似ランダム信号を生成するステップと、第iのビット抽出部が、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出するステップと、第iの排他的論理和計算部が、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、暗号文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算するステップと、を有し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とする復号方法。付記19平文の各部を、平文の他の部分のうちの一部と、平文の他の部分のうちの一部を暗号化するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により暗号化する手段を備えることを特徴とする接頭一致保存型の暗号化装置としてコンピュータを機能させるためのプログラム。付記20付記19に記載のプログラムであって、前記平文の他の部分のうちの一部とは、平文のそれまでに暗号化された部分のうちの直近に暗号化された部分であることを特徴とするプログラム。付記21付記19又は20に記載のプログラムであって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、としてコンピュータを機能させ、第1の擬似ランダム信号生成部は、秘密鍵を基に、第1の擬似ランダム信号を生成し、第ii=2、3、...、nの擬似ランダム信号生成部は、前記秘密鍵と第i-1の擬似ランダム信号と平文に含まれる所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部に入力されたビットとを基に、第iの擬似ランダム信号を生成し、第iのビット抽出部は、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出し、第iの排他的論理和計算部は、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、平文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、暗号文として得ることを特徴とするプログラム。付記22付記21に記載のプログラムであって、前記第1乃至第nの擬似ランダム信号生成部の機能のうちの少なくとも2つは、1つの擬似ランダム信号生成部の機能が時分割に動作することにより実現されることを特徴とするプログラム。付記23付記21又は22に記載のプログラムであって、前記第1乃至第nのビット抽出部の機能のうちの少なくとも2つは、1つのビット抽出部の機能が時分割に動作することにより実現されることを特徴とするプログラム。付記24付記21乃至23の何れか1に記載のプログラムであって、前記第1乃至第nの排他的論理和計算部の機能のうちの少なくとも2つは、1つの排他的論理和計算部の機能が時分割に動作することにより実現されることを特徴とするプログラム。付記25暗号文の各部を、暗号文の他の部分のうちの一部を復号することにより得た平文の一部と、暗号文の他の部分のうちの一部を復号するために利用された擬似ランダム信号と、秘密鍵とを基に生成される擬似ランダム信号により復号する手段を備えることを特徴とする接頭一致保存型の復号装置としてコンピュータを機能させるためのプログラム。付記26付記25に記載のプログラムであって、前記暗号文の他の部分のうちの一部とは、暗号文のそれまでに復号された部分のうちの直近に復号された部分であることを特徴とするプログラム。付記27付記25又は26に記載のプログラムであって、第1乃至第nの擬似ランダム信号生成部と、第1乃至第nのビット抽出部と、第1乃至第nの排他的論理和計算部と、としてコンピュータを機能させ、第1の擬似ランダム信号生成部は、秘密鍵を基に、第1の擬似ランダム信号を生成し、第ii=2、3、...、nの擬似ランダム信号生成部は、前記秘密鍵と第i-1の擬似ランダム信号と暗号文に含まれる所定位置pi-1の所定数bi-1のビットを復号することにより得た平文の所定位置pi-1の所定数bi-1のビットであって第i-1の排他的論理和計算部から出力されたビットとを基に、第iの擬似ランダム信号を生成し、第iのビット抽出部は、第iの擬似ランダム信号に含まれるビットのうちの所定位置qiの所定数biのビットを抽出し、第iの排他的論理和計算部は、第iのビット抽出部により抽出された所定位置qiの所定数biのビットの各々と、暗号文に含まれる所定位置piの所定数のビットbiの各々との排他的論理和を各々計算し、第1乃至第nの排他的論理和計算部の計算結果を合わせたものを、平文として得ることを特徴とするプログラム。付記28付記27に記載のプログラムであって、前記第1乃至第nの擬似ランダム信号生成部の機能のうちの少なくとも2つは、1つの擬似ランダム信号生成部の機能が時分割に動作することにより実現されることを特徴とするプログラム。付記29付記27又は28に記載のプログラムであって、前記第1乃至第nのビット抽出部の機能のうちの少なくとも2つは、1つのビット抽出部の機能が時分割に動作することにより実現されることを特徴とするプログラム。付記30付記27乃至29の何れか1に記載のプログラムであって、前記第1乃至第nの排他的論理和計算部の機能のうちの少なくとも2つは、1つの排他的論理和計算部の機能が時分割に動作することにより実現されることを特徴とするプログラム。