(57)【特許請求の範囲】
【請求項１】
領域Aに関するn (2≦n)個の変換関数Fi: A×A→A (1≦i≦n)と、その逆変換関数Gi: A×A→Aと、であって、任意のx∈A，y∈Aについて
Fi(Gi(x,y),y) = x；
Gi(Fi(x,y),y) = x
が成立するものと、
単項演算☆: An→Anと、その逆単項演算◎: An→Anと、であって、任意のz∈Anについて
☆(◎z) = z；
◎(☆z) = z
が成立するものと、
所定のパラメータa∈Aと、
を用いる変換装置であって、
生成部と、データ受付部と、繰返し制御部と、変換部と、を備え、
前記生成部は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力し、
前記データ受付部は、長さnのデータ入力k1，k2，…，kn∈Aを受け付けて、これを前記生成部に生成入力として与え、
前記繰返し制御部は、前記生成部からの生成出力を前記生成部への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとし、
前記変換部は、r1，r2，…，rn∈Aに単項演算☆を適用して変換
(e1，e2，…，en) =☆(r1，r2，…，rn)
を行い、長さnのデータ出力e1，e2，…，enを出力し、
変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるか、もしくは、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
である
ことを特徴とする変換装置。
【請求項２】
領域Aに関するn (2≦n)個の変換関数Fi: A×A→A (1≦i≦n)と、その逆変換関数Gi: A×A→Aと、であって、任意のx∈A，y∈Aについて
Fi(Gi(x,y),y) = x；
Gi(Fi(x,y),y) = x
が成立するものと、
単項演算☆: An→Anと、その逆単項演算◎: An→Anと、であって、任意のz∈Anについて
☆(◎z) = z；
◎(☆z) = z
が成立するものと、
所定のパラメータa∈Aと、
を用いる変換装置であって、
生成部と、データ受付部と、変換部と、繰返し制御部と、を備え、
前記生成部は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = G1(x1,a)；
yi+1 = Gi+1(xi+1,xi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力し、
前記データ受付部は、長さnのデータ入力h1，h2，…，hn∈Aを受け付け、
前記変換部は、h1，h2，…，hnに単項演算☆を適用して変換
(v1，v2，…，vn) = ☆(h1，h2，…，hn)
を行い、その結果v1，v2，…，vnを前記生成部に生成入力として与え、
前記繰返し制御部は、前記生成部からの生成出力を前記生成部への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnのデータ出力s1，s2，…，sn∈Aとし、
変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるか、もしくは、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
である
ことを特徴とする変換装置。
【請求項３】
請求項１または２に記載の変換装置であって、Aをtビット空間とし、
z∈Anを長さtnビットのビット列に対応させたときに、単項演算◎は、当該ビット列を所定ビット数所定の方向へ巡回シフトし、その結果をAnに対応させて単項演算結果とする
ことを特徴とする変換装置。
【請求項４】
請求項１に記載の変換装置を暗号化部として、請求項２に記載の変換装置を復号化部として、それぞれ備える暗号化復号化システムであって、前記暗号化部と前記復号化部が用いるFi，Gi，☆，◎，aは共通し、
（ａ）前記暗号化部は、
長さnの元データを、データ入力k1，k2，…，knとして受け付け、
長さnのデータ出力e1，e2，…，enを、暗号化済データとして出力し、
（ｂ）前記復号化部は、
長さnの暗号化済データを、データ入力h1，h2，…，hnとして受け付け、
長さnのデータ出力s1，s2，…,snを、復号化済データとして出力する
ことを特徴とする暗号化復号化システム。
【請求項５】
請求項２に記載の変換装置を暗号化部として、請求項１に記載の変換装置を復号化部として、それぞれ備える暗号化復号化システムであって、前記暗号化部と前記復号化部が用いるFi，Gi，☆，◎，aは共通し、
（ａ）前記暗号化部は、
長さnの元データを、データ入力h1，h2，…，hnとして受け付け、
長さnのデータ出力s1，s2，…,snを、暗号化済データとして出力し、
（ｂ）前記復号化部は、
長さnの暗号化済データを、データ入力k1，k2，…，knとして受け付け、
長さnのデータ出力e1，e2，…，enを、復号化済データとして出力する
ことを特徴とする暗号化復号化システム。
【請求項６】
u個の請求項１に記載の変換装置（j番目のものをMj (1≦j≦u)という。）と、
長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、当該変換装置Mjの所定のパラメータaとする多段鍵入力受付部と、
を備え、
当該変換装置M1は、データ入力として、長さnの多段変換入力k1，k2，…，knを受け付け、
当該変換装置Mi (1≦i≦u-1)が出力するデータ出力は、当該変換装置Mi+1にデータ入力として与えられ、  当該変換装置Muは、長さnのデータ出力e1，e2，…，enを多段変換出力として出力する
ことを特徴とする多段変換装置。
【請求項７】
u個の請求項２に記載の変換装置（j番目のものをMj (1≦j≦u)という。）と、
長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、当該変換装置Mjの所定のパラメータaとする多段鍵入力受付部と、
を備え、
当該変換装置Muは、データ入力として、長さnの多段変換入力h1，h2，…，hnを受け付け、
当該変換装置Mi+1 (1≦i≦u-1)が出力するデータ出力は、当該変換装置Miにデータ入力として与えられ、
当該変換装置M1は、長さnのデータ出力s1，s2，…，snを多段変換出力として出力する
ことを特徴とする多段変換装置。
【請求項８】
請求項６に記載の多段変換装置を暗号化部として、請求項７に記載の多段変換装置を復号化部として、それぞれ備える暗号化復号化システムであって、
前記暗号化部と前記復号化部が用いるFi，Gi，☆，◎は共通し、
前記暗号化部と前記復号化部が受け付けるパラメータ入力a1，a2，…，auは共通し、
（ａ）前記暗号化部は、
長さnの元データを、多段変換入力k1，k2，…，knとして受け付け、
長さnの多段変換出力e1，e2，…，enを、暗号化済データとして出力し、
（ｂ）前記復号化部は、
長さnの暗号化済データを、多段変換入力h1，h2，…，hnとして受け付け、
長さnの多段変換出力s1，s2，…，snを、復号化済データとして出力する
ことを特徴とする暗号化復号化システム。
【請求項９】
請求項７に記載の多段変換装置を暗号化部として、請求項６に記載の多段変換装置を復号化部として、それぞれ備える暗号化復号化システムであって、
前記暗号化部と前記復号化部が用いるFi，Gi，☆，◎は共通し、
前記暗号化部と前記復号化部が受け付けるパラメータ入力a1，a2，…，auは共通し、
（ａ）前記暗号化部は、
長さnの元データを、多段変換入力h1，h2，…，hnとして受け付け、
長さnの多段変換出力s1，s2，…，snを、暗号化済データとして出力し、
（ｂ）前記復号化部は、
長さnの暗号化済データを、多段変換入力k1，k2，…，knとして受け付け、
長さnの多段変換出力e1，e2，…，enを、復号化済データとして出力する
ことを特徴とする暗号化復号化システム。
【請求項１０】
コンピュータを、
請求項１から３のいずれか１項に記載の変換装置として機能させる
ことを特徴とするプログラム。
【請求項１１】
コンピュータを、
請求項６または７に記載の多段変換装置として機能させる
ことを特徴とするプログラム。
【請求項１２】
請求項１０または１１に記載のプログラムを記録した
ことを特徴とするコンピュータ読取可能な情報記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ベクターストリーム秘密鍵暗号システムに好適な変換装置、暗号化復号化システム、多段変換装置、変換方法、多段変換方法、プログラム、ならびに、情報記録媒体に関する。
【０００２】
【従来の技術】
従来から、秘密鍵暗号システムとして、ブロック暗号やストリーム暗号の手法が知られている。ブロック暗号としては、DES、RC5などが標準として採用されており、ストリーム暗号としては、RC4、SEAL 1.0などが知られている。
【０００３】
ストリーム暗号では、ランダムなビット列を生成し、暗号化すべきデータと当該ビット列との排他的論理和をとることにより、暗号化を行う。したがって、暗号化速度はランダムなビット列の生成速度に依存し、一般に高速な暗号化が実現できる。また、ビット誤りが無視できない状況（移動体通信等）に適しており、データフォーマットが柔軟に変更できる。
【０００４】
一方ブロック暗号では、Ｓ関数と呼ばれるデータの非線型撹拌を用いる。ブロック単位の処理が行われるため、様々なデータフォーマット（画像、音声、動画等）への適合性が高いという利点があるが、ビット誤りが生ずると、その誤りが拡散してしまうという問題がある。
【０００５】
【発明が解決しようとする課題】
しかしながら、このようなストリーム暗号の利点と、ブロック暗号の利点と、をできるだけ兼ね備えた秘密鍵暗号システムに対する要望は大きい。
【０００６】
特に大規模データベース、画像、音声、動画などの大容量データの暗号化に適した秘密鍵暗号システムが強く望まれている。
【０００７】
本発明は、以上のような問題を解決するためになされたもので、ベクターストリーム秘密鍵暗号システムに好適な変換装置、暗号化復号化システム、多段変換装置、変換方法、多段変換方法、プログラム、ならびに、情報記録媒体を提供することを目的とする。
【０００８】
【課題を解決するための手段】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００９】
本発明の第１の観点に係る変換装置は、領域Aに関するn (n≧1)個の変換関数Fi: A×A→A (1≦i≦n)と、２項演算☆: A×A→Aであって、その逆２項演算◎: A×A→Aが存在し、任意のx∈A，y∈Aについて
（x☆y）◎y = x；
（x◎y）☆y = x
が成立するものと、所定のパラメータa∈Aと、を用いる変換装置であって、生成部と、鍵受付部と、繰返し制御部と、データ受付部と、変換部と、を備え、以下のように構成する。
【００１０】
ここで、生成部は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを生成する。
【００１１】
一方、鍵受付部は、長さnの鍵入力k1，k2，…，kn∈Aを受け付けて、これを生成部に生成入力として与える。
【００１２】
さらに、繰返し制御部は、生成部からの生成出力を生成部への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【００１３】
そして、データ受付部は、長さnのデータ入力d1，d2，…，dn∈Aを受け付ける。
【００１４】
一方、変換部は、1以上n以下の整数iに対して
ei = di☆ri
によりデータを変換して、長さnのデータ出力e1，e2，…，en∈Aを出力する。
【００１５】
本発明の他の観点に係る変換装置は、領域Aに関するn (n≧1)個の変換関数Fi: A×A→A (1≦i≦n)と、２項演算☆: A×A→Aであって、その逆２項演算◎: A×A→Aが存在し、任意のx∈A，y∈Aについて
（x☆y）◎y = x；
（x◎y）☆y = x
が成立するものと、所定のパラメータa∈Aと、を用いる変換装置であって、生成部と、鍵受付部と、繰返し制御部と、データ受付部と、変換部と、を備え、以下のように構成する。
【００１６】
ここで、生成部は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,xi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを生成する。
【００１７】
一方、鍵受付部は、長さnの鍵入力k1，k2，…，kn∈Aを受け付けて、これを生成部に生成入力として与える。
【００１８】
さらに、繰返し制御部は、生成部からの生成出力を生成部への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【００１９】
そして、データ受付部は、長さnのデータ入力d1，d2，…，dn∈Aを受け付ける。
【００２０】
一方、変換部は、1以上n以下の整数iに対して
ei = di☆ri
によりデータを変換して、長さnのデータ出力e1，e2，…，en∈Aを出力する。
【００２１】
また、上記の変換装置において、２項演算◎，☆は、いずれも排他的論理和であるように構成することができる。
【００２２】
また、上記の変換装置において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるように構成することができる。
【００２３】
また、上記の変換装置において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
であるように構成することができる。
【００２４】
本発明の他の観点に係る暗号化復号化システムは、上記の変換装置を暗号化部として、これと同じ構成の他の変換装置を復号化部として、それぞれ備え、以下のように構成する。
【００２５】
すなわち、暗号化部と復号化部とが用いるFi，◎，aは共通する。
【００２６】
一方、任意のx∈A，y∈Aに対して
x☆y = x◎y
が成立する。
【００２７】
さらに、暗号化部と復号化部とは、共通の鍵入力k1，k2，…，knを受け付ける。
【００２８】
そして、暗号化部は、長さnの元データを、データ入力として受け付け、長さnのデータ出力を、暗号化済データとして出力する。
【００２９】
一方、復号化部は、長さnの暗号化済データを、データ入力として受け付け、長さnのデータ出力を、復号化済データとして出力する。
【００３０】
本発明の他の観点に係る変換装置は、領域Aに関するn (1≦n)個の変換関数Fi: A×A→A (1≦i≦n)と、その逆変換関数Gi: A×A→Aと、であって、任意のx∈A，y∈Aについて
Fi(Gi(x,y),y) = x；
Gi(Fi(x,y),y) = x
が成立するものと、単項演算☆: An→Anと、その逆単項演算◎: An→Anと、であって、任意のz∈Anについて
☆(◎z) = z；
◎(☆z) = z
が成立するものと、所定のパラメータa∈Aと、を用いる変換装置であって、生成部と、データ受付部と、繰返し制御部と、変換部と、を備え、以下のように構成する。
【００３１】
すなわち、生成部は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力する。
【００３２】
一方、データ受付部は、長さnのデータ入力k1，k2，…，kn∈Aを受け付けて、これを生成部に生成入力として与える。
【００３３】
さらに、繰返し制御部は、生成部からの生成出力を生成部への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【００３４】
そして、変換部は、r1，r2，…，rn∈Aに単項演算☆を適用して変換
(e1，e2，…，en) =☆(r1，r2，…，rn)
を行い、長さnのデータ出力e1，e2，…，enを出力する。
【００３５】
本発明の他の観点に係る変換装置は、領域Aに関するn (1≦n)個の変換関数Fi: A×A→A (1≦i≦n)と、その逆変換関数Gi: A×A→Aと、であって、任意のx∈A，y∈Aについて
Fi(Gi(x,y),y) = x；
Gi(Fi(x,y),y) = x
が成立するものと、単項演算☆: An→Anと、その逆単項演算◎: An→Anと、であって、任意のz∈Anについて
☆(◎z) = z；
◎(☆z) = z
が成立するものと、所定のパラメータa∈Aと、を用いる変換装置であって、生成部と、データ受付部と、変換部と、繰返し制御部と、を備え、以下のように構成する。
【００３６】
すなわち、生成部は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = G1(x1,a)；
yi+1 = Gi+1(xi+1,xi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力する。
【００３７】
一方、データ受付部は、長さnのデータ入力h1，h2，…，hn∈Aを受け付ける。
【００３８】
さらに、変換部は、h1，h2，…，hnに単項演算☆を適用して変換
(v1，v2，…，vn) = ☆(h1，h2，…，hn)
を行い、その結果v1，v2，…，vnを生成部に生成入力として与える。
【００３９】
そして、繰返し制御部は、生成部からの生成出力を生成部への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnのデータ出力s1，s2，…，sn∈Aとする。
【００４０】
また、上記の変換装置において、Aをtビット空間とし、z∈Anを長さtnビットのビット列に対応させたときに、単項演算◎は、当該ビット列を所定ビット数所定の方向へ巡回シフトし、その結果をAnに対応させて単項演算結果とするように構成することができる。
【００４１】
また、上記の変換装置において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるように構成することができる。
【００４２】
また、上記の変換装置において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
であるように構成することができる。
【００４３】
本発明の他の観点に係る暗号化復号化システムは、上記の変換装置の前者を暗号化部として、上記の変換装置の後者を復号化部として、それぞれ備える暗号化復号化システムであって、暗号化部と復号化部が用いるFi，Gi，☆，◎，aは共通し、以下のように構成する。
【００４４】
すなわち、暗号化部は、長さnの元データを、データ入力k1，k2，…，knとして受け付け、長さnのデータ出力e1，e2，…，enを、暗号化済データとして出力する。
【００４５】
一方、復号化部は、長さnの暗号化済データを、データ入力h1，h2，…，hnとして受け付け、長さnのデータ出力s1，s2，…,snを、復号化済データとして出力する。
【００４６】
本発明の他の観点に係る暗号化復号化システムは、上記の変換装置の後者を暗号化部として、上記の変換装置の前者を復号化部として、それぞれ備え、暗号化部と復号化部が用いるFi，Gi，☆，◎，aは共通し、以下のように構成する。
【００４７】
すなわち、暗号化部は、長さnの元データを、データ入力h1，h2，…，hnとして受け付け、長さnのデータ出力s1，s2，…,snを、暗号化済データとして出力する。
【００４８】
一方、復号化部は、長さnの暗号化済データを、データ入力k1，k2，…，knとして受け付け、長さnのデータ出力e1，e2，…，enを、復号化済データとして出力する。
【００４９】
本発明の他の観点に係る多段変換装置は、u個の上記の前者の変換装置（j番目のものをMj (1≦j≦u)という。）と、多段鍵入力受付部と、を備え、以下のように構成する。
【００５０】
すなわち、多段鍵入力受付部は、長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、当該変換装置Mjの所定のパラメータaとする。
【００５１】
一方、当該変換装置M1は、データ入力として、長さnの多段変換入力k1，k2，…，knを受け付ける。
【００５２】
さらに、当該変換装置Mi (1≦i≦u-1)が出力するデータ出力は、当該変換装置Mi+1にデータ入力として与えられる。
【００５３】
そして、当該変換装置Muは、長さnのデータ出力e1，e2，…，enを多段変換出力として出力する。
【００５４】
本発明の他の観点に係る多段変換装置は、u個の上記の後者の変換装置（j番目のものをMj (1≦j≦u)という。）と、多段鍵入力受付部と、を備え、以下のように構成する。
【００５５】
すなわち、多段鍵入力受付部は、長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、当該変換装置Mjの所定のパラメータaとする。
【００５６】
一方、当該変換装置Muは、データ入力として、長さnの多段変換入力h1，h2，…，hnを受け付ける。
【００５７】
さらに、当該変換装置Mi+1 (1≦i≦u-1)が出力するデータ出力は、当該変換装置Miにデータ入力として与えられる。
【００５８】
そして、当該変換装置M1は、長さnのデータ出力s1，s2，…，snを多段変換出力として出力する。
【００５９】
本発明の他の観点に係る暗号化復号化システムは、上記の前者の多段変換装置を暗号化部として、上記の後者の多段変換装置を復号化部として、それぞれ備え、以下のように構成する。
【００６０】
すなわち、暗号化部と復号化部が用いるFi，Gi，☆，◎は共通する。
【００６１】
一方、暗号化部と復号化部が受け付けるパラメータ入力a1，a2，…，auは共通する。
【００６２】
さらに、暗号化部は、長さnの元データを、多段変換入力k1，k2，…，knとして受け付け、長さnの多段変換出力e1，e2，…，enを、暗号化済データとして出力する。
【００６３】
そして、復号化部は、長さnの暗号化済データを、多段変換入力h1，h2，…，hnとして受け付け、長さnの多段変換出力s1，s2，…，snを、復号化済データとして出力する。
【００６４】
本発明の他の観点に係る暗号化復号化システムは、上記の後者の多段変換装置を暗号化部として、上記の前者の多段変換装置を復号化部として、それぞれ備え、以下のように構成する。
【００６５】
すなわち、暗号化部と復号化部が用いるFi，Gi，☆，◎は共通する。
【００６６】
一方、暗号化部と復号化部が受け付けるパラメータ入力a1，a2，…，auは共通する。
【００６７】
そして、暗号化部は、長さnの元データを、多段変換入力h1，h2，…，hnとして受け付け、長さnの多段変換出力s1，s2，…，snを、暗号化済データとして出力する。
【００６８】
さらに、復号化部は、長さnの暗号化済データを、多段変換入力k1，k2，…，knとして受け付け、長さnの多段変換出力e1，e2，…，enを、復号化済データとして出力する。
【００６９】
本発明の他の観点に係る変換方法は、領域Aに関するn (n≧1)個の変換関数Fi: A×A→A (1≦i≦n)と、２項演算☆: A×A→Aであって、その逆２項演算◎: A×A→Aが存在し、任意のx∈A，y∈Aについて
（x☆y）◎y = x；
（x◎y）☆y = x
が成立するものと、所定のパラメータa∈Aと、を用いる変換方法であって、生成工程と、鍵受付工程と、繰返し制御工程と、データ受付工程と、変換工程と、を備え、以下のように構成する。
【００７０】
すなわち、生成工程では、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを生成する。
【００７１】
一方、鍵受付工程では、長さnの鍵入力k1，k2，…，kn∈Aを受け付けて、これを生成工程に生成入力として与える。
【００７２】
さらに、繰返し制御工程では、生成工程からの生成出力を生成工程への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【００７３】
そして、データ受付工程では、長さnのデータ入力d1，d2，…，dn∈Aを受け付ける。
【００７４】
一方、変換工程では、1以上n以下の整数iに対して
ei = di☆ri
によりデータを変換して、長さnのデータ出力e1，e2，…，en∈Aを出力する。
【００７５】
本発明の他の観点に係る変換方法は、領域Aに関するn (n≧1)個の変換関数Fi: A×A→A (1≦i≦n)と、２項演算☆: A×A→Aであって、その逆２項演算◎: A×A→Aが存在し、任意のx∈A，y∈Aについて
（x☆y）◎y = x；
（x◎y）☆y = x
が成立するものと、所定のパラメータa∈Aと、を用いる変換方法であって、生成工程と、鍵受付工程と、繰返し制御工程と、データ受付工程と、変換工程と、を備え、以下のように構成する。
【００７６】
すなわち、生成工程では、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,xi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを生成する。
【００７７】
一方、鍵受付工程では、長さnの鍵入力k1，k2，…，kn∈Aを受け付けて、これを生成工程に生成入力として与える。
【００７８】
さらに、繰返し制御工程では、生成工程からの生成出力を生成工程への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【００７９】
そして、データ受付工程では、長さnのデータ入力d1，d2，…，dn∈Aを受け付ける。
【００８０】
一方、変換工程では、1以上n以下の整数iに対して
ei = di☆ri
によりデータを変換して、長さnのデータ出力e1，e2，…，en∈Aを出力する。
【００８１】
また、上記の変換方法において、２項演算◎，☆は、いずれも排他的論理和であるように構成することができる。
【００８２】
また、上記の変換方法において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるように構成することができる。
【００８３】
また、上記の変換方法において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
であるように構成することができる。
【００８４】
本発明の他の観点に係る変換方法は、領域Aに関するn (1≦n)個の変換関数Fi: A×A→A (1≦i≦n)と、その逆変換関数Gi: A×A→Aと、であって、任意のx∈A，y∈Aについて
Fi(Gi(x,y),y) = x；
Gi(Fi(x,y),y) = x
が成立するものと、単項演算☆: An→Anと、その逆単項演算◎: An→Anと、であって、任意のz∈Anについて
☆(◎z) = z；
◎(☆z) = z
が成立するものと、所定のパラメータa∈Aと、を用いる変換方法であって、生成工程と、データ受付工程と、繰返し制御工程と、変換工程と、を備え、以下のように構成する。
【００８５】
すなわち、生成工程では、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力する。
【００８６】
一方、データ受付工程では、長さnのデータ入力k1，k2，…，kn∈Aを受け付けて、これを生成工程に生成入力として与える。
【００８７】
さらに、繰返し制御工程では、生成工程からの生成出力を生成工程への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【００８８】
そして、変換工程では、r1，r2，…，rn∈Aに単項演算☆を適用して変換
(e1，e2，…，en) =☆(r1，r2，…，rn)
を行い、長さnのデータ出力e1，e2，…，enを出力する。
【００８９】
本発明の他の観点に係る変換方法は、領域Aに関するn (1≦n)個の変換関数Fi: A×A→A (1≦i≦n)と、その逆変換関数Gi: A×A→Aと、であって、任意のx∈A，y∈Aについて
Fi(Gi(x,y),y) = x；
Gi(Fi(x,y),y) = x
が成立するものと、単項演算☆: An→Anと、その逆単項演算◎: An→Anと、であって、任意のz∈Anについて
☆(◎z) = z；
◎(☆z) = z
が成立するものと、所定のパラメータa∈Aと、を用いる変換方法であって、生成工程と、データ受付工程と、変換工程と、繰返し制御工程と、を備え、以下のように構成する。
【００９０】
すなわち、生成工程では、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = G1(x1,a)；
yi+1 = Gi+1(xi+1,xi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力する。
【００９１】
一方、データ受付工程では、長さnのデータ入力h1，h2，…，hn∈Aを受け付ける。
【００９２】
さらに、変換工程では、h1，h2，…，hnに単項演算☆を適用して変換
(v1，v2，…，vn) = ☆(h1，h2，…，hn)
を行い、その結果v1，v2，…，vnを生成工程に生成入力として与える。
【００９３】
そして、繰返し制御工程では、生成工程からの生成出力を生成工程への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnのデータ出力s1，s2，…，sn∈Aとする。
【００９４】
また、上記の変換方法において、Aをtビット空間とし、z∈Anを長さtnビットのビット列に対応させたときに、単項演算◎は、当該ビット列を所定ビット数所定の方向へ巡回シフトし、その結果をAnに対応させて単項演算結果とするように構成することができる。
【００９５】
また、上記の変換方法において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるように構成することができる。
【００９６】
また、上記の変換方法において、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、
ceil(・)はM進法での小数点以下の切り上げ、
floor(・)はM進法での小数点以下の切り捨て
であるとしたときに、任意の整数パラメータb (1≦b≦Ms)に対して、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
であるように構成することができる。
【００９７】
本発明の他の観点に係る多段変換方法は、u個の変換工程（j番目のものをMj (1≦j≦u)という。）であって、そのそれぞれは上記の前者の変換方法を使用する工程と、多段鍵入力受付工程と、を備え、以下のように構成する。
【００９８】
すなわち、多段鍵入力受付工程では、長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、変換工程Mjの所定のパラメータaとする。
【００９９】
一方、変換工程M1では、データ入力として、長さnの多段変換入力k1，k2，…，knを受け付ける。
【０１００】
さらに、変換工程Mi (1≦i≦u-1)が出力するデータ出力は、変換工程Mi+1にデータ入力として与えられる。
【０１０１】
そして、変換工程Muでは、長さnのデータ出力e1，e2，…，enを多段変換出力として出力する。
【０１０２】
本発明の他の観点に係る多段変換方法は、u個の変換工程（j番目のものをMj (1≦j≦u)という。）であって、そのそれぞれは上記の後者の変換方法を使用する工程と、多段鍵入力受付工程と、を備え、以下のように構成する。
【０１０３】
すなわち、多段鍵入力受付工程では、長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、変換工程Mjの所定のパラメータaとする。
【０１０４】
そして、変換工程Muでは、データ入力として、長さnの多段変換入力h1，h2，…，hnを受け付ける。
【０１０５】
一方、変換工程Mi+1 (1≦i≦u-1)が出力するデータ出力は、変換工程Miにデータ入力として与えられる。
【０１０６】
そして、変換工程M1では、長さnのデータ出力s1，s2，…，snを多段変換出力として出力する。
【０１０７】
本発明の他の観点に係るプログラムは、コンピュータを、上記のいずれかの変換装置、もしくは、上記のいずれかの多段変換装置として機能させ、または、コンピュータに、上記のいずれかの変換方法、もしくは、上記のいずれかの多段変換方法を実行させるように構成する。
【０１０８】
本発明の他の観点に係る情報記録媒体は、上記のいずれかのプログラムを記録するように構成する。
【０１０９】
また、上記の情報記録媒体として、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを採用することができる。
【０１１０】
ここで、プログラムを実行させるべきコンピュータとは独立して、本発明のプログラムを、コンピュータ通信網を介して配布・販売することができる。また、プログラムを実行させるべきコンピュータとは独立して、本発明の情報記録媒体を、通常の商取引において配布・販売したりできる。
【０１１１】
【発明の実施の形態】
以下に本発明の一実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【０１１２】
以下の説明では、まず、ベクターストリーム秘密鍵暗号システムにおいて用いることができる変換装置の実施形態について述べ（第１の実施形態、第２の実施形態）、ついで、これらのいずれか一方を用いた暗号化復号化システムの実施形態について述べる（第３の実施形態）。
【０１１３】
以下の実施形態では、領域Aに関するn (n≧1)個の変換関数Fi: A×A→A (1≦i≦n)と、２項演算☆: A×A→Aであって、その逆２項演算◎: A×A→Aが存在し、任意のx∈A，y∈Aについて(x☆y)◎y = x，(x◎y)☆y = xが成立するものを用いる。
【０１１４】
特に、このような２項演算◎，☆として、以下の実施形態では、排他的論理和を採用する。
【０１１５】
また、以下の説明では、ceil(・)はM進法での小数点以下の切り上げ、floor(・)はM進法での小数点以下の切り捨てであるとする。
【０１１６】
以下の実施形態では、このような変換関数Fiのいずれか１つとして、正整数M，sを定め、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるようなものを採用する。これは増田−合原のパラメータ付写像である（電子情報通信学会論文誌１９９９年７月号、Vol.J82-A，No.7，pp.1042-1046）。なお、この写像はスキューテント写像と呼ばれることもある。
【０１１７】
また、以下の実施形態では、このような変換関数Fiのいずれか１つとして、上記のものにかえて、任意の整数パラメータb (1≦b≦Ms)に対して、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
であるようなものを採用することができる。これは、上記の増田−合原のパラメータ付写像の逆写像である。
【０１１８】
（第１の実施形態）
図１は、本発明の実施形態の一つに係る変換装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【０１１９】
変換装置１０１は、所定のパラメータa∈Aを用いる。また、生成部１０２と、鍵受付部１０３と、繰返し制御部１０４と、データ受付部１０５と、変換部１０６と、を備える。
【０１２０】
ここで、生成部１０２は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを生成する。
【０１２１】
一方、鍵受付部１０３は、長さnの鍵入力k1，k2，…，kn∈Aを受け付けて、これを生成部１０２に生成入力として与える。
【０１２２】
さらに、繰返し制御部１０４は、生成部１０２からの生成出力を生成部１０２への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【０１２３】
そして、データ受付部１０５は、長さnのデータ入力d1，d2，…，dn∈Aを受け付ける。
【０１２４】
一方、変換部１０６は、1以上n以下の整数iに対して
ei = di☆ri
によりデータを変換して、長さnのデータ出力e1，e2，…，en∈Aを出力する。
【０１２５】
この計算は、パイプライン処理機能を有する並列コンピュータにおいて高速に処理することができるが、以下では、一般に普及している逐次型コンピュータにおいて処理を行う場合の手法について述べる。図２は、逐次型コンピュータを変換装置１０１として機能させる場合の変換処理の手順を示すフローチャートである。以下、本図を参照して説明する。
【０１２６】
まず、鍵入力変数の値k1，k2，…，kn∈Aを受け付ける（ステップＳ２０１）。
【０１２７】
そして、これらを、それぞれ、変数x1，x2，…，xn∈Aに代入する（ステップＳ２０２）。
【０１２８】
ついで、カウンタ変数cに値mを代入する（ステップＳ２０３）。
【０１２９】
さらに、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により変数y1，y2，…，yn∈Aの値を計算する（ステップＳ２０４）。
【０１３０】
そして、カウンタ変数cの値が０であるか否かを調べる（ステップＳ２０５）。０でない場合（ステップＳ２０５；Ｎｏ）、変数y1，y2，…，ynの値を変数x1，x2，…，xnに代入し（ステップＳ２０６）、カウンタ変数cの値を１減らして（ステップＳ２０７）、ステップＳ２０４に戻る。
【０１３１】
一方、カウンタ変数cの値が０である場合（ステップＳ２０５；Ｙｅｓ）、変数y1，y2，…，ynの値を変数r1，r2，…，rn∈Aに代入する（ステップＳ２０８）。
【０１３２】
そして、暗号化すべきデータ入力d1，d2，…，dn∈Aを受け付ける（ステップＳ２０９）。
【０１３３】
ついで、1以上n以下の整数iに対して
ei = di☆ri
によりデータを変換する（ステップＳ２１０）。
【０１３４】
最後に、変数e1，e2，…，enの値を出力する（ステップＳ２１１）。
【０１３５】
これらの処理により、暗号化復号化システムにおいて用いられる変換処理が実現できる。
【０１３６】
（第２の実施形態）
本実施形態は、上記図３は、本発明の実施形態の他の一つに係る変換装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【０１３７】
ここで、変換装置３０１の構成は、変換装置１０１の構成とほぼ同じであり、変換装置３０１が備える生成部３０２は、生成部１０２に、鍵受付部３０３は、鍵受付部１０３に、繰返し制御部３０４は、繰返し制御部１０４に、データ受付部３０５は、データ受付部１０５に、変換部３０６は、変換部１０６に、それぞれ対応する。
【０１３８】
これらにおいては、生成部３０２が用いる漸化式と生成部１０２が用いる漸化式とが異なる。すなわち、生成部３０２は、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,xi)  (1≦i≦n-1)
を用いる。
【０１３９】
図４は、逐次型コンピュータを変換装置３０１として機能させる場合の変換処理の手順を示すフローチャートである。ここで、変換装置３０１用の処理手順と変換装置１０１用の処理手順とはほぼ同じであり、変換装置３０１用の処理手順のステップＳ４０１〜ステップＳ４１１は、それぞれ、変換装置１０１用の処理手順のステップＳ２０１〜ステップＳ２１１に対応する。
【０１４０】
これらの処理手順においては、ステップＳ４０４で用いる漸化式とステップＳ２０４で用いる漸化式とが異なる。すなわち、ステップＳ４０４では、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,xi)  (1≦i≦n-1)
を用いる。
【０１４１】
（第３実施例）
本実施形態は、変換装置１０１、変換装置３０１のいずれか一方を暗号化部として、これと同じものを復号化部として、それぞれ備える暗号化復号化システムである。図５は、変換装置１０１を暗号化部・復号化部として備える暗号化復号化システムの概要構成を示す模式図である。
【０１４２】
暗号化復号化システム５０１は、暗号化部５０２と復号化部５０３とを備える。暗号化部５０２と、復号化部５０３と、は、いずれも変換装置１０１によって構成される。
【０１４３】
暗号化部５０２と、復号化部５０３と、は、同じFi，aを用いる。また、本実施形態では、◎，☆として排他的論理和を採用しているため、任意のx∈A，y∈Aに対してx☆y = x◎yが成立する。
【０１４４】
暗号化部５０２と復号化部５０３とは、共通の鍵入力k1，k2，…，knを受け付ける。
【０１４５】
そして、暗号化部５０２は、長さnの元データを、データ入力として受け付け、長さnのデータ出力を、暗号化済データとして出力する。
【０１４６】
一方、復号化部５０３は、長さnの暗号化済データを、データ入力として受け付け、長さnのデータ出力を、復号化済データとして出力する。
【０１４７】
このようにして、ベクターストリーム秘密鍵暗号システムを実現することができる。
【０１４８】
図６は、変換装置３０１を暗号化部・復号化部として備える暗号化復号化システムの概要構成を示す模式図である。本実施形態でも、暗号化復号化システム５０１は、暗号化部５０２と復号化部５０３とを備え、暗号化部５０２と、復号化部５０３と、が、いずれも変換装置３０１によって構成される点以外は、上記実施形態と同様である。
【０１４９】
本実施形態によっても、ベクターストリーム秘密鍵暗号システムを実現することができる。
【０１５０】
さらに以下の説明では、ベクターストリーム秘密鍵暗号システムにおいて用いることができる他の変換装置の実施形態について述べ（第４の実施形態、第５の実施形態）、ついで、これらのいずれか一方を用いた暗号化復号化システムの実施形態について述べる（第６の実施形態）。
【０１５１】
以下の説明では、領域Aに関するn (1≦n)個の変換関数Fi: A×A→A (1≦i≦n)と、その逆変換関数Gi: A×A→Aと、を用いる。これらには、任意のx∈A，y∈Aについて
Fi(Gi(x,y),y) = x；
Gi(Fi(x,y),y) = x
が成立するものを採用する。
【０１５２】
また、単項演算☆: An→Anと、その逆単項演算◎: An→Anと、を用いる。これらについては、任意のz∈Anについて
☆(◎z) = z；
◎(☆z) = z
が成立するものを採用する。
【０１５３】
特に、以下の説明では、Aをtビット空間とし、z∈Anを長さtnビットのビット列に対応させたときに、単項演算◎は、当該ビット列を所定ビット数所定の方向へ巡回シフトし、その結果をAnに対応させて単項演算結果とするものを採用する。
【０１５４】
また、以下の説明でも、ceil(・)はM進法での小数点以下の切り上げ、floor(・)はM進法での小数点以下の切り捨てであるものとする。
【０１５５】
また、以下の説明における実施形態では、変換関数Fiのいずれか少なくとも１つは、正整数M，sを定め、任意の整数パラメータb (1≦b≦Ms)に対して
Fi(x,b) = ceil(xMs/b)  (1≦x≦b)；
Fi(x,b) = floor(Ms(x-b)/(Ms-b))+1  (b<x≦Ms)
であるように選択する。これは、上述の増田−合原のパラメータ付写像である。
【０１５６】
なお、以下の説明における実施形態においても、上記の変換関数Fiにかえて、正整数M，sを定め、任意の整数パラメータb (1≦b≦Ms)に対して、
Fi(y,b) = x1  (q<x1)；
Fi(y,b) = x2  (x1≦q)
ただし
x1 = floor(M-sby)；
x2 = ceil((M-sb-1)y + Ms)；
q = b(x2-Ms)/(b-Ms)
である関数（上述の増田−合原のパラメータ付写像の逆写像）を採用することができる。
【０１５７】
（第４の実施形態）
図７は、本発明の実施形態の一つに係る変換装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【０１５８】
変換装置７０１は、所定のパラメータa∈Aを用いる。変換装置７０１は、生成部７０２と、データ受付部７０３と、繰返し制御部７０４と、変換部７０５と、を備える。
【０１５９】
ここで、生成部７０２は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力する。
【０１６０】
一方、データ受付部７０３は、長さnのデータ入力k1，k2，…，kn∈Aを受け付けて、これを生成部７０２に生成入力として与える。
【０１６１】
さらに、繰返し制御部７０４は、生成部７０２からの生成出力を生成部７０２への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnの乱数列r1，r2，…，rn∈Aとする。
【０１６２】
そして、変換部７０５は、r1，r2，…，rn∈Aに単項演算☆を適用して変換
(e1，e2，…，en) =☆(r1，r2，…，rn)
を行い、長さnのデータ出力e1，e2，…，enを出力する。
【０１６３】
これらの計算はパイプライン並列機能等を備える並列計算機で高速に計算することができるが、一般的な逐次型計算機で計算することもできる。図８は、逐次型コンピュータを変換装置７０１として機能させる際の変換処理の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１６４】
まず、長さnのデータ入力k1，k2，…，kn∈Aを受け付ける（ステップＳ８０１）。
【０１６５】
そして、これらを、それぞれx1，x2，…，xn∈Aに代入する（ステップＳ８０２）。
【０１６６】
ついで、カウンタ変数cに値mを代入する（ステップＳ８０３）。
【０１６７】
さらに、漸化式
y1 = F1(x1,a)；
yi+1 = Fi+1(xi+1,yi)  (1≦i≦n-1)
により変数y1，y2，…，yn∈Aの値を計算する（ステップＳ８０４）。
【０１６８】
そして、カウンタ変数cの値が０であるか否かを調べる（ステップＳ８０５）。０でない場合（ステップＳ８０５；Ｎｏ）、変数y1，y2，…，ynの値を変数x1，x2，…，xnにそれぞれ代入し（ステップＳ８０６）、カウンタ変数cの値を１減らして（ステップＳ８０７）、ステップＳ８０４に戻る。
【０１６９】
一方、カウンタ変数cの値が０である場合（ステップＳ８０５；Ｙｅｓ）、変数y1，y2，…，ynの値を変数r1，r2，…，rn∈Aに代入する（ステップＳ８０８）。
【０１７０】
変数r1，r2，…，rn∈Aに単項演算☆を適用して変換
(e1，e2，…，en) =☆(r1，r2，…，rn)
を行う（ステップＳ８０９）。
【０１７１】
最後に変数e1，e2，…，enの値を出力する（ステップＳ８１０）。
【０１７２】
（第５の実施形態）
図９は、上記の変換装置７０１と対になる変換装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【０１７３】
変換装置９０１は、各種の演算や関数、パラメータ、段数Fi，Gi，◎，☆，a，mとして、対になる変換装置７０１と共通のものを用いる。
【０１７４】
変換装置９０１は、パラメータaを用いる。変換装置９０１は、生成部９０２と、データ受付部９０３と、変換部９０４と、繰返し制御部９０５と、を備える。
【０１７５】
ここで、生成部９０２は、長さnの生成入力x1，x2，…，xn∈Aを受け付けて、漸化式
y1 = G1(x1,a)；
yi+1 = Gi+1(xi+1,xi)  (1≦i≦n-1)
により長さnの生成出力y1，y2，…，yn∈Aを出力する。
【０１７６】
一方、データ受付部９０３は、長さnのデータ入力h1，h2，…，hn∈Aを受け付ける。
【０１７７】
さらに、変換部９０４は、h1，h2，…，hnに単項演算◎を適用して変換
(v1，v2，…，vn) = ◎(h1，h2，…，hn)
を行い、その結果v1，v2，…，vnを生成部９０２に生成入力として与える。
【０１７８】
そして、繰返し制御部９０５は、生成部７０２からの生成出力を生成部７０２への生成入力としてさらに与えることをm (m≧0)回繰り返して、最後の生成出力を長さnのデータ出力s1，s2，…，sn∈Aとする。
【０１７９】
これらの計算はパイプライン並列機能等を備える並列計算機で高速に計算することができるが、一般的な逐次計算機で計算することもできる。図１０は、逐次型コンピュータを変換装置９０１として機能させる際の変換処理の流れを示すフローチャートである。以下、本図を参照して説明する。
【０１８０】
まず、長さnのデータ入力h1，h2，…，hn∈Aを受け付ける（ステップＳ１００１）。
【０１８１】
そして、h1，h2，…，hnに単項演算◎を適用して変換
(v1，v2，…，vn) = ◎(h1，h2，…，hn)
を行う（ステップＳ１００２）。
【０１８２】
ついで、変数v1，v2，…，vnの値を、x1，x2，…，xn∈Aに代入する（ステップＳ１００３）。
【０１８３】
さらに、カウンタ変数cに値mを代入する（ステップＳ１００４）。
【０１８４】
さらに漸化式
y1 = G1(x1,a)；
yi+1 = Gi+1(xi+1,xi)  (1≦i≦n-1)
により変数y1，y2，…，yn∈Aの値を計算する（ステップＳ１００５）。
【０１８５】
そして、カウンタ変数cの値が０であるか否かを調べる（ステップＳ１００６）。０でない場合（ステップＳ１００６；Ｎｏ）、変数y1，y2，…，ynの値を変数x1，x2，…，xnにそれぞれ代入し（ステップＳ１００７）、カウンタ変数cの値を１減らして（ステップＳ１００８）、ステップＳ１００５に戻る。
【０１８６】
一方、カウンタ変数cの値が０である場合（ステップＳ１００６；Ｙｅｓ）、変数y1，y2，…，ynの値を変数s1，s2，…，sn∈Aに代入する（ステップＳ１００９）。
【０１８７】
最後に、変数s1，s2，…，snの値を出力する（ステップＳ１０１０）。
【０１８８】
（第６の実施形態）
本実施形態は、上記の対となる変換装置７０１と変換装置９０１とを組み合わせた暗号化復号化システムである。変換装置７０１と変換装置９０１の一方を暗号化部、他方を復号化部とすることができ、どの組合せを選ぶかによって、２通りのシステムが考えられることになる。
【０１８９】
図１１は、変換装置７０１を暗号化部とし、これと対となる変換装置９０１を復号化部とした暗号化復号化システムの概要構成である。以下、本図を参照して説明する。
【０１９０】
暗号化復号化システム１１０１は、暗号化部１１０２と復号化部１１０３とを備え、暗号化部１１０２は上記の変換装置７０１により、復号化部１１０３はこれと対になる変換装置９０１により、それぞれ構成される。
【０１９１】
ここで、暗号化部１１０３は、長さnの元データを、データ入力k1，k2，…，knとして受け付け、長さnのデータ出力e1，e2，…，enを、暗号化済データとして出力する。
【０１９２】
一方、復号化部１１０４は、長さnの暗号化済データを、データ入力h1，h2，…，hnとして受け付け、長さnのデータ出力s1，s2，…,snを、復号化済データとして出力する。
【０１９３】
これにより、ベクターストリーム秘密鍵暗号システムを実現することができる。
【０１９４】
図１２は、変換装置９０１を暗号化部とし、これと対となる変換装置７０１を復号化部とした暗号化復号化システムの概要構成である。以下、本図を参照して説明する。
【０１９５】
暗号化復号化システム１２０１は、暗号化部１２０２と復号化部１２０３とを備え、暗号化部１２０２は上記の変換装置９０１により、復号化部１２０３はこれと対になる変換装置７０１により、それぞれ構成される。
【０１９６】
ここで、暗号化部１２０２は、長さnの元データを、データ入力h1，h2，…，hnとして受け付け、長さnのデータ出力s1，s2，…,snを、暗号化済データとして出力する。
【０１９７】
一方、復号化部１２０３は、長さnの暗号化済データを、データ入力k1，k2，…，knとして受け付け、長さnのデータ出力e1，e2，…，enを、復号化済データとして出力する。
【０１９８】
本実施形態によっても、上記実施形態同様、ベクターストリーム秘密鍵暗号システムを実現することができる。
【０１９９】
以下では、第４〜第６の実施形態において用いる単項演算◎，☆について、例をあげて詳しく説明する。Aが１ビット空間であり、z∈Anを長さnビットのビット列に対応させたときに、単項演算◎としては、たとえば以下のようなものを採用することができる。
◎(z1，z2，…，za-1，za，…，zn) = (za，…，zn，z1，z2，…，za-1)
【０２００】
これはa-1ビットのビット回転（巡回シフト）演算である（n-a+1ビットのビット回転演算と見ることもできる）。この場合、演算☆としては、これと逆向きのビット回転演算を採用すればよい。この例を以下に示す。
☆(za，…，zn，z1，z2，…，za-1) = (z1，z2，…，za-1，za，…，zn)
【０２０１】
Aがt (t>1)の場合であっても、これらのビット回転演算を自然に拡張することができ、本発明に適用することができる。
【０２０２】
以下では、変換装置７０１と、これと対となる変換装置９０１とを多段に組み合わせた多段変換装置（第７の実施形態、第８の実施形態）と、これを用いた暗号化復号化システム（第９の実施形態、第１０の実施形態）について説明する。
【０２０３】
（第７の実施形態）
図１３は、本実施形態に係る多段変換装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【０２０４】
多段変換装置１３０１は、u個の変換装置７０１（j番目のものをMj (1≦j≦u)という。）と、多段鍵入力受付部１３０２と、を備える。
【０２０５】
多段鍵入力受付部１３０２は、長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、当該変換装置７０１  Mjの所定のパラメータaとする。
【０２０６】
一方、当該変換装置７０１  M1は、データ入力として、長さnの多段変換入力k1，k2，…，knを受け付ける。
【０２０７】
さらに、当該変換装置７０１  Mi (1≦i≦u-1)が出力するデータ出力は、当該変換装置７０１  Mi+1にデータ入力として与えられる。
【０２０８】
そして、当該変換装置７０１  Muは、長さnのデータ出力e1，e2，…，enを多段変換出力として出力する。
【０２０９】
（第８の実施形態）
図１４は、上記の多段変換装置１３０１と対になる多段変換装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【０２１０】
多段変換装置１４０１は、u個の変換装置９０１  （j番目のものをNj (1≦j≦u)という。）と、多段鍵入力受付部１４０２と、を備える。
【０２１１】
ここで、多段鍵入力受付部１４０２は、長さuのパラメータ入力a1，a2，…，au∈Aを受け付けて、当該パラメータ入力のそれぞれについて、j番目のパラメータ入力ajを、当該変換装置９０１  Njの所定のパラメータaとする。
【０２１２】
一方、当該変換装置９０１  Nuは、データ入力として、長さnの多段変換入力h1，h2，…，hnを受け付ける。
【０２１３】
さらに、当該変換装置９０１  Ni+1 (1≦i≦u-1)が出力するデータ出力は、当該変換装置９０１  Niにデータ入力として与えられる。
【０２１４】
そして、当該変換装置９０１  N1は、長さnのデータ出力s1，s2，…，snを多段変換出力として出力する。
【０２１５】
（第９の実施形態）
図１５は、上記の多段変換装置１３０１と、これと対となる多段変換装置１４０１と、を用いる暗号化復号化システムの概要構成を示す模式図である。以下、本図を参照して説明する。
【０２１６】
暗号化復号化システム１５０１は、上記の多段変換装置１３０１を暗号化部１５０２として、上記の多段変換装置１４０１を復号化部１５０３として、それぞれ備える。
【０２１７】
ここで、暗号化部１５０２と復号化部１５０３が用いるFi，Gi，☆，◎は共通する。
【０２１８】
また、暗号化部１５０２と復号化部１５０３が受け付けるパラメータ入力a1，a2，…，auは共通する。
【０２１９】
さらに、暗号化部１５０２は、長さnの元データを、多段変換入力k1，k2，…，knとして受け付け、長さnの多段変換出力e1，e2，…，enを、暗号化済データとして出力する。
【０２２０】
そして、復号化部１５０３は、長さnの暗号化済データを、多段変換入力h1，h2，…，hnとして受け付け、長さnの多段変換出力s1，s2，…，snを、復号化済データとして出力する。
【０２２１】
これにより、ベクターストリーム秘密鍵暗号システムを実現することができる。
【０２２２】
（第１０の実施形態）
図１６は、上記の多段変換装置１３０１と、これと対となる多段変換装置１４０１と、を用いる暗号化復号化システムの概要構成を示す模式図である。以下、本図を参照して説明する。
【０２２３】
暗号化復号化システム１６０１は、上記の多段変換装置１４０１を暗号化部１６０２として、上記の多段変換装置１３０１を復号化部１６０３として、それぞれ備える。
【０２２４】
ここで、暗号化部１６０２と復号化部１６０３が用いるFi，Gi，☆，◎は共通する。
【０２２５】
また、暗号化部１６０２と復号化部１６０３が受け付けるパラメータ入力a1，a2，…，auは共通する。
【０２２６】
そして、暗号化部１６０２は、長さnの元データを、多段変換入力h1，h2，…，hnとして受け付け、長さnの多段変換出力s1，s2，…，snを、暗号化済データとして出力する。
【０２２７】
さらに、復号化部１６０３は、長さnの暗号化済データを、多段変換入力k1，k2，…，knとして受け付け、長さnの多段変換出力e1，e2，…，enを、復号化済データとして出力する。
【０２２８】
これによっても、ベクターストリーム秘密鍵暗号システムを実現することができる。
【０２２９】
なお、ベクターストリーム秘密鍵暗号システムは、次元の数nを大きくすることによって並列度が増す。したがって、ＦＰＧＡ（Field Programmable Gate Array）等を利用し、あるいは、専用チップを用いて並列処理に適した実装を行うことで、更に処理の高速化を図ることができる。
【０２３０】
また、特許第３０３０３４１号ならびに特開２００１−１７５１６８号公報において開示するのと同様に、本発明で用いる基本変換が一様な分布を持つとき、本変換で用いる合成変換の多次元ベクトルの分布も一様となる。図１７は、３次元ベクターストリーム秘密鍵暗号システムで生成されたデータの分布を、立方体[0,1]3内に並べたものである。本図によれば、データが立方体内に一様の分布していることがわかる。
【０２３１】
暗号化処理では、等頻度特性という統計的安定性が必要とされる。図１７等を見れば明らかなように、本発明の手法では、等頻度特性を有することがわかる。
【０２３２】
【発明の効果】
以上説明したように、本発明によれば、ベクターストリーム秘密鍵暗号システムに好適な変換装置、暗号化復号化システム、多段変換装置、変換方法、多段変換方法、プログラム、ならびに、情報記録媒体を提供することができる。
【図面の簡単な説明】
【図１】  本発明の実施形態の一つに係る変換装置の概要構成を示す模式図である。
【図２】  逐次型コンピュータを変換装置として機能させる場合の変換処理の手順を示すフローチャートである。
【図３】  本発明の実施形態の一つに係る変換装置の概要構成を示す模式図である。
【図４】  逐次型コンピュータを変換装置として機能させる場合の変換処理の手順を示すフローチャートである。
【図５】  変換装置を暗号化部・復号化部として備える暗号化復号化システムの概要構成を示す模式図である。
【図６】  変換装置を暗号化部・復号化部として備える暗号化復号化システムの概要構成を示す模式図である。
【図７】  本発明の実施形態の一つに係る変換装置の概要構成を示す模式図である。
【図８】  逐次型コンピュータを変換装置として機能させる際の変換処理の流れを示すフローチャートである。
【図９】  本発明の実施形態の一つに係る変換装置の概要構成を示す模式図である。
【図１０】  逐次型コンピュータを変換装置として機能させる際の変換処理の流れを示すフローチャートである。
【図１１】  変換装置を暗号化部とし、これと対となる変換装置を復号化部とした暗号化復号化システムの概要構成である。
【図１２】  変換装置を暗号化部とし、これと対となる変換装置を復号化部とした暗号化復号化システムの概要構成である。
【図１３】  本発明の実施形態の一つに係る多段変換装置の概要構成を示す模式図である。
【図１４】  本発明の実施形態の一つに係る多段変換装置の概要構成を示す模式図である。
【図１５】  多段変換装置と、これと対となる多段変換装置と、を用いる暗号化復号化システムの概要構成を示す模式図である。
【図１６】  多段変換装置と、これと対となる多段変換装置と、を用いる暗号化復号化システムの概要構成を示す模式図である。
【図１７】  本発明の原理により生成されたデータの分布を示す分布図である。
【符号の説明】
１０１    変換装置
１０２    生成部
１０３    鍵受付部
１０４    繰返し制御部
１０５    データ受付部
１０６    変換部
３０１    変換装置
３０２    生成部
３０３    鍵受付部
３０４    繰返し制御部
３０５    データ受付部
３０６    変換部
５０１    暗号化復号化システム
５０２    暗号化部
５０３    復号化部
７０１    変換装置
７０２    生成部
７０３    データ受付部
７０４    繰返し制御部
７０５    変換部
９０１    変換装置
９０２    生成部
９０３    データ受付部
９０４    変換部
９０５    繰返し制御部
１１０１  暗号化復号化システム
１１０２  暗号化部
１１０３  復号化部
１２０１  暗号化復号化システム
１２０２  暗号化部
１２０３  復号化部
１３０１  多段変換装置
１３０２  多段鍵入力受付部
１４０１  多段変換装置
１４０２  多段鍵入力受付部
１５０１  暗号化復号化システム
１５０２  暗号化部
１５０３  復号化部
１６０１  暗号化復号化システム
１６０２  暗号化部
１６０３  復号化部
【図１】
0004191915.tif 000002
【図２】
0004191915.tif 000003
【図３】
0004191915.tif 000004
【図４】
0004191915.tif 000005
【図５】
0004191915.tif 000006
【図６】
0004191915.tif 000007
【図７】
0004191915.tif 000008
【図８】
0004191915.tif 000009
【図９】
0004191915.tif 000010
【図１０】
0004191915.tif 000011
【図１１】
0004191915.tif 000012
【図１２】
0004191915.tif 000013
【図１３】
0004191915.tif 000014
【図１４】
0004191915.tif 000015
【図１５】
0004191915.tif 000016
【図１６】
0004191915.tif 000017
【図１７】
0004191915.tif 000018