(57)【特許請求の範囲】
【請求項１】
通信相手と共通鍵k(x)を共有化するセキュリティ装置において、
第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定手段と、
通信相手と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成する第１の線形作用演算手段と、
生成された前記第１の演算結果を、前記通信相手に送信する演算結果開示手段と、
前記通信相手によって演算された第２の演算結果を受信する演算結果取得手段と、
前記演算結果取得手段によって受信された前記第２の演算結果をc(x)とし、前記第２の演算結果c(x)の次数をdeg c(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行い、その演算結果を前記共通鍵k(x)として出力する第２の線形作用演算手段と、
を有することを特徴とするセキュリティ装置。
【請求項２】
第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定手段と、
通信相手と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成する第１の線形作用演算手段と、
生成された前記第１の演算結果を、公開鍵として送信する公開鍵公開手段と、
前記通信相手によって演算された第２の演算結果と、暗号文とを、受信する暗号文取得手段と、
前記暗号文取得手段によって受信された前記第２の演算結果をc(x)とし、前記第２の演算結果の次数をdeg c(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行うことにより、第３の演算結果を生成する第２の線形作用演算手段と、
生成された前記第３の演算結果と、前記暗号文と、の排他的論理和を演算する排他的論理和演算手段と、
を有することを特徴とするセキュリティ装置。
【請求項３】
第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定手段と、
通信相手によって公開された第１の演算結果を、公開鍵として受信する公開鍵取得手段と、
前記公開鍵取得手段によって受信された前記第１の演算結果をb(x)とし、前記第１の演算結果の次数をdeg b(x)とし、前記第１の整数パラメータをumとし、前記第２の整数パラメータをvmとし、前記第１の個数をtとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行うことにより、第２の演算結果を生成する第１の線形作用演算手段と、
生成された前記第２の演算結果と、通信内容である平文との排他的論理和を、暗号文として演算する排他的論理和演算手段と、
通信相手と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第１の整数パラメータをumとし、前記第２の整数パラメータをvmとし、前記第１の個数をtとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第３の演算結果を生成する第２の線形作用演算手段と、
前記排他的論理和演算手段によって演算された前記暗号文と、前記第２の線形作用演算手段によって生成された前記第３の演算結果とを開示する暗号文開示手段と、
を有することを特徴とするセキュリティ装置。
【請求項４】
第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定手段と、
通信相手と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成する第１の線形作用演算手段と、
前記第１の線形作用演算手段によって生成された前記第１の演算結果を公開鍵として送信する公開鍵公開手段と、
第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定する第２のパラメータ設定手段と、
前記共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第２の演算結果を生成する第２の線形作用演算手段と、
前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、前記通信相手と共用される多項式に値を持つハッシュ関数をHとし、平文をMとし、前記第２の演算結果をc(x)とした場合におけるΣm=0tvmxum+Σm=0rqmxsmH(M,c(x))の演算を行い、該演算結果をd(x)とした場合における多項式対（c(x),d(x)）を生成する多項式対生成手段と、
前記多項式対生成手段において生成された前記多項式対を前記通信相手に送信する多項式対送信手段と、
を有することを特徴とするセキュリティ装置。
【請求項５】
デジタル署名の検証を行うセキュリティ装置において、
通信相手によって公開された公開鍵を受信する公開鍵取得手段と、
第１の多項式と第２の多項式から構成される多項式対を受信する多項式対取得手段と、
前記通信相手と共用される整数係数の共通多項式をa(x)とし、前記公開鍵をb(x)とし、前記第１の多項式をS1とし、前期第２の多項式をS2とし、前記通信相手と共用される多項式に値を持つハッシュ関数をHとし、平文をMとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、S2(1-δ)a(x)-H(M,S1(x))(1-δ)b(x)-S1(x)modIの演算を行い、該演算結果が０となった場合には、署名が有効である旨の出力を行い、該演算結果が０とならなかった場合には、署名は無効である旨の出力を行う署名検証手段と、
を有することを特徴とするセキュリティ装置。
【請求項６】
前記イデアル集合は、
整数係数の多項式がなす環のイデアルであって、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、degf(x)をf(x)の次数とした場合における、｛f(x), δf(x),δ2f(x),…,δdegf(x)f(x)｝によって生成される集合であること、
を特徴とする請求項１から５の何れかに記載のセキュリティ装置。
【請求項７】
前記第１の整数パラメータ、前記第２の整数パラメータ、前記第３の整数パラメータ及び前記第４の整数パラメータは、該整数パラメータを設定したセキュリティ装置側において秘密に保たれる秘密情報であることを特徴とする請求項１から６の何れかに記載のセキュリティ装置。
【請求項８】
暗号技術を利用して第１のセキュリティ装置と第２のセキュリティ装置とで共通鍵k(x)を共有化するセキュリティ方法において、
前記第１のセキュリティ装置の第１のパラメータ設定手段が、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定ステップと、
前記第１のセキュリティ装置の第１の線形作用演算が、第２のセキュリティ装置と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成する第１の線形作用演算ステップと、
前記第１のセキュリティ装置の第１の演算結果開示手段が、前記第１の線形作用演算ステップによって生成された前記第１の演算結果を、前記第２のセキュリティ装置に送信する第１の演算結果開示ステップと、
前記第１のセキュリティ装置の第１の演算結果取得手段が、前記第２のセキュリティ装置によって演算された第２の演算結果を受信する第１の演算結果取得ステップと、
前記第１のセキュリティ装置の第２の線形作用演算手段が、前記第１の演算結果取得ステップによって受信された前記第２の演算結果をc(x)とし、前記第２の演算結果c(x)の次数をdeg c(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行い、その演算結果を前記共通鍵k(x)として出力する第２の線形作用演算ステップと、
前記第２のセキュリティ装置の第２のパラメータ設定手段が、第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定する第２のパラメータ設定ステップと、
前記第２のセキュリティ装置の第３の線形作用演算手段が、前記共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、前記第２の演算結果を生成する第３の線形作用演算ステップと、
前記第２のセキュリティ装置の第２の演算結果開示手段が、生成された前記第２の演算結果を、前記第１のセキュリティ装置に送信する第２の演算結果開示ステップと、
前記第２のセキュリティ装置の第２の演算結果取得手段が、前記第１のセキュリティ装置によって演算された前記第１の演算結果を受信する第２の演算結果取得ステップと、
前記第２のセキュリティ装置の第４の線形作用演算手段が、前記第２の演算結果取得ステップによって受信された前記第１の演算結果をb(x)とし、前記第２の演算結果b(x)の次数をdeg b(x)とし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行い、その演算結果を前記共通鍵k(x)として出力する第４の線形作用演算ステップと、
を有することを特徴とするセキュリティ方法。
【請求項９】
暗号技術を利用したセキュリティ方法において、
第１のセキュリティ装置において、
第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定し、
第２のセキュリティ装置と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成し、
生成した前記第１の演算結果を公開鍵として送信し、
前記第２のセキュリティ装置において、
第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定し、
前記第１のセキュリティ装置によって送信された前記第１の演算結果を、公開鍵として受信し、
受信した前記第１の演算結果をb(x)とし、前記第１の演算結果の次数をdeg b(x)とし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行うことにより、第２の演算結果を生成し、
前記第２の演算結果と、通信内容である平文との排他的論理和を、暗号文として演算し、
前記第１のセキュリティ装置と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第３の演算結果を生成し、
演算された前記暗号文と、前記第３の演算結果とを送信し、
前記第１のセキュリティ装置において、
前記第１のセキュリティ装置によって演算された前記暗号文と、前記第３の演算結果とを受信し、
受信された前記第３の演算結果をc(x)とし、前記第２の演算結果の次数をdeg c(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行うことにより、第４の演算結果を生成し、
前記第４の演算結果と、前記暗号文と、の排他的論理和を演算すること、
を特徴とするセキュリティ方法。
【請求項１０】
デジタル署名の生成及び検証を行うセキュリティ方法において、
第１のセキュリティ装置において、
第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定し、
第２のセキュリティ装置と共用される整数係数の共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成し、
生成された前記第１の演算結果を公開鍵として送信し、
第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定し、
前記共通多項式をa(x)とし、前記共通多項式の次数をdeg a(x)とし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、∂を微分作用素とし、前記イデアル集合をIとした場合における、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第２の演算結果を生成し、
前記第１の整数パラメータをsmとし、前記第２の整数パラメータをqmとし、前記第１の個数をrとし、前記第３の整数パラメータをumとし、前記第４の整数パラメータをvmとし、前記第２の個数をtとし、前記第２のセキュリティ装置と共用される多項式に値を持つハッシュ関数をHとし、平文をMとし、前記第２の演算結果をc(x)とした場合におけるΣm=0tvmxum+Σm=0rqmxsmH(M,c(x))の演算を行い、該演算結果をd(x)とした場合における多項式対（c(x),d(x)）を生成し、
生成された前記多項式対を前記第２のセキュリティ装置に送信し、
前記第２のセキュリティ装置において、
前記第１のセキュリティ装置によって公開された前記公開鍵を受信し、
第１の多項式と第２の多項式から構成される多項式対を受信し、
前記第１のセキュリティ装置と共用される整数係数の共通多項式をa(x)とし、前記公開鍵をb(x)とし、前記第１の多項式をS1とし、前期第２の多項式をS2とし、前記通信相手と共用される多項式に値を持つハッシュ関数をHとし、平文をMとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、前記イデアル集合をIとした場合における、S2(1-δ)a(x)-H(M,S1(x))(1-δ)b(x)-S1(x)modIの演算を行い、該演算結果が０となった場合には、署名が有効である旨の出力を行い、該演算結果が０とならなかった場合には、署名は無効である旨の出力を行う、
ことを特徴とするデジタル署名検証装置。
【請求項１１】
前記イデアル集合は、
整数係数の多項式がなす環のイデアルであって、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、degf(x)をf(x)の次数とした場合における、｛f(x), δf(x),δ2f(x),…,δdegf(x)f(x)｝によって生成される集合であること、
を特徴とする請求項８から１０の何れかに記載のセキュリティ方法。
【請求項１２】
前記第１の個数、前記第１の整数パラメータ、前記第２の整数パラメータ、前記第２の個数、前記第３の整数パラメータ及び前記第４の整数パラメータは、該整数パラメータを設定したセキュリティ装置側において秘密に保たれる秘密情報であることを特徴とする請求項８から１１の何れかに記載のセキュリティ方法。
【請求項１３】
請求項１から７の何れかに記載されたセキュリティ装置としてコンピュータを機能させるためのセキュリティプログラム。
【請求項１４】
請求項１３記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号技術を利用したセキュリティ装置、セキュリティ方法、その機能をコンピュータに実行させるためのセキュリティプログラム及びそれを格納したコンピュータ読み取り可能な記録媒体に関し、特に、公開鍵暗号技術を利用したセキュリティ装置、セキュリティ方法、その機能をコンピュータに実行させるためのセキュリティプログラム及びそれを格納したコンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
従来より、離散対数問題を応用したDiffile-Hellman鍵配送方式（例えば、非特許文献１参照）及びその応用としての公開鍵暗号方式やデジタル署名方式が提案されている。
まず、この従来のDiffile-Hellman鍵配送方式による鍵配送手順について説明する。なお、甲乙間は、安全でない通信回線によって結ばれているものとする。
鍵の配送を行う場合、甲は、まず、擬似乱数生成装置を用いてあるN以下の整数aを定め、このaを通信回線を介して乙に送信する。次に、甲は、擬似乱数生成装置を用いてある整数sを定めた後、整数演算装置を用いてb=asmodNを計算し、整数sを秘密に保ったまま、計算したbを乙に送信する。
これに対し、乙は、擬似乱数生成装置を用いてある整数tを定めた後、整数演算装置を用いてc=atmodNを計算し、整数tを秘密に保ったまま、計算したcを甲に送信する。また、乙は、整数演算装置を用い、甲から送信されたbから、鍵k=btmodNを求める。
一方、甲は、整数演算装置を用い、乙から送信されたcから、鍵k=csmodNを求める。
ここで、乙が求めた鍵kは、k=btmodN=astmodNとなり、甲が求めた鍵k=csmodN=astmodNと一致することになる。これにより、甲乙間で、共通鍵kの配送が行われたことになる。
【０００３】
次に、この従来のDiffile-Hellman鍵配送方式を応用した公開鍵暗号方式について説明する。以下では、乙から甲へ暗号文を送信し、甲が送られた暗号文を復号するものとする。
この場合、甲は、まず、擬似乱数生成装置を用いてあるN以下の整数aを定め、このaを通信回線を介して乙に送信する。次に、甲は、擬似乱数生成装置を用いてある整数sを定めた後、整数演算装置を用いてb=asmodNを計算し、整数sを秘密に保ったまま、計算したbを乙に送信する。この整数sが秘密鍵として機能し、bが公開鍵として機能することになる。
これに対し、乙は、擬似乱数生成装置を用いてある整数tを定めた後、整数演算装置を用いてc=atmodNを計算し、整数tを秘密に保ったまま、計算したcを甲に送信する。また、乙は、整数演算装置を用い、甲から送信されたbからk=btmodNを求め、このkで平文Mを暗号化した後、この暗号文と計算したcとを、甲に送信する。
これを受け取った甲は、整数演算装置を用い、送られたcからk=csmodNを計算し、このkを用い、送られた暗号文を復号する。
【０００４】
次に、この従来の離散対数問題の困難性を応用したデジタル署名方式であるSchnorr署名方式について説明する。なお、以下では、甲乙間は、安全でない通信回線によって結ばれており、甲から乙へ送信するメッセージＭに対し、甲がデジタル署名を行い、メッセージＭを受け取った乙が、このメッセージＭに付されたデジタル署名の検証を行うものとする。また、甲と乙は共通のハッシュ関数Hを計算する装置を備えているものとする。
この場合、まず甲は、設定した素数p及び自然数aを公開し、擬似乱数発生装置を用いて定めた自然数tを秘密鍵として保持しておき、さらに、甲はb=atmodpによってbを設定し、設定したbを公開鍵として公開しておく。
【０００５】
そして、甲が実際に署名を生成する際、甲は、さらに擬似乱数発生装置を用いて自然数uを生成し、この自然数uを用いてc=aumodpを演算し、この演算結果を用いて、整数の対S=(c,u+tH(M,c))を生成し、生成した整数の対Sを、自然数uを秘密に保った状態で乙に送信する。
整数の対S=(S1,S2)を受け取った乙は、このS及び公開されているbによりV=as2bH(M,s1)c-1modpの演算を行う。ここで、例えば署名が有効であった場合、受け取った整数の対Sは、S1=c、S2=u+tH(M,c)となっているはずである。この場合、Vの値は、V=a(u+tH(M,c))bH(M,c)c-1modpとなり、さらにb及びcの定義（b=atmodp、c=aumodp）からV=１となる。一方、上述のように、u+tH(M,c)を構成するu及びtは甲の秘密情報となっているため、甲以外の者はこのu及びtを適切に選択できず、この場合、S1=c、S2=u+tH(M,c)とはならない。結果、V=1ともならない。これにより、乙は、V=１のときには署名が有効であると判断でき、V=１でないときには署名が無効であることが判断できる。なお、このSchnorr署名方式の安全性については、Hが理想的な乱数関数であり、かつ離散対数問題が解けないならば安全であることが知られている（例えば、非特許文献２参照）。
【０００６】
【非特許文献１】
産業図書「現代暗号」岡本龍明、山本博資著  Ｐ２００〜２０２。
【非特許文献２】
Pintcheval and Stern: Security Proofs for Signature Schemes, Proc. Of Eurocrypt'96, LNCS 1070, Springer-Verlag,pp.387-398(1996)
【０００７】
【発明が解決しようとする課題】
しかし、従来のDiffile-Hellman鍵配送方式、及びその応用としての公開鍵暗号方式やデジタル署名方式では、b及びcの計算に必要な四則演算の回数が、秘密パラメータであるs、tの大きさに依存して増大してしまう。そのため、安全性向上のために秘密パラメータs、tを大きくした場合、鍵配送時、暗号・復号時、署名生成・検証時における計算量が増大し、実用面での利便性に問題があるという課題がある。
本発明はこのような点に鑑みてなされたものであり、このような実用面での利便性を向上させることが可能なセキュリティ装置を提供することを目的とする。
また、本発明の他の目的は、このような実用面での利便性を向上させることが可能なセキュリティ方法を提供することである。
さらに、本発明の他の目的は、このような実用面での利便性を向上させたセキュリティ機能を、コンピュータに実行させるためのセキュリティプログラムを提供することである。
また、本発明の他の目的は、このような実用面での利便性を向上させたセキュリティ機能を、コンピュータに実行させるためのセキュリティプログラムを記録したコンピュータ読み取り可能な記録媒体を提供することである。
【０００８】
【課題を解決するための手段】
本発明では上記課題を解決するために、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定し、集合に対し、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とした場合における、Σm=0rqm(1-δ)smを作用させ、その演算結果を用いてセキュリティ機能を実現する。
この場合、この集合にΣm=0rqm(1-δ)smを作用させるための四則演算の回数が、第１の整数パラメータsm、第２の整数パラメータqmの大きさに伴って増大していくことはない。結果、利用時における利便性を保ちつつ、第三者からの攻撃に対する安全性の向上を図ることが可能となる。
【０００９】
【発明の実施の形態】
以下、本発明における第１の実施の形態を図面を参照して説明する。
ここでは、まず、本形態の概略について説明を行い、その後、本形態の詳細について説明を行っていく。
図１は、本形態におけるセキュリティシステム１の概略を説明するための図である。
図１に例示するように、セキュリティシステム１は、セキュリティ装置２、３によって構成されており、このセキュリティ装置２、３間において、共通鍵の配送を行う。
【００１０】
この例の場合、セキュリティ装置２は、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定手段２ａ、及び集合に対し、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とした場合における、Σm=0rqm(1-δ)smを作用させる線形作用演算手段２ｂ、２ｃを有しており、同じく、セキュリティ装置３は、第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定する第２のパラメータ設定手段３ａ、及び集合に対し、第３の整数パラメータをumとし、第４の整数パラメータをvmとし、第２の個数をtとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とした場合における、Σm=0tvm(1-δ)umを作用させる線形作用演算手段３ｂ、３ｃを有している。
【００１１】
また、その詳細については後述するが、この例の場合、線形作用演算手段２ｂは、所定の多項式をa(x)とし、該多項式の次数をdeg a(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う手段となっており、これにより、線形作用素Σm=0rqm(1-δ)smによる環の作用の逆問題が生成されることになる。この点、線形作用演算手段２ｃ、３ｂ、３ｃについても同様である。
【００１２】
なお、本形態及び以後の形態の説明において、δとは、任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素を意味し、この定義から(1-δ)sは、任意の多項式g(x)に対して多項式g(x-s)を対応させる作用素を意味する。
また、イデアル集合Iとは、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をいうものとする。なお、「イデアル」に関し、例えば、可換環Rの部分集合I1がイデアルであるとは、任意のx,y∈I1についてx+y∈I1が成り立ち、かつ任意のx∈Rとy∈I1についてxy∈I1が成り立つことを意味し、このようなイデアル集合の具体例としては、例えば、整数係数の多項式がなす環のイデアルであって、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、deg f(x)をf(x)の次数とした場合における、｛f(x), δf(x),δ2f(x),…,δdeg f(x)f(x)｝ によって生成される集合が挙げられる。
【００１３】
本形態におけるセキュリティシステム１において共通鍵k(x)の配送を行う場合、例えば、まず、セキュリティ装置２は、整数係数の多項式である共通多項式a(x)を生成し、生成した共通多項式a(x)をセキュリティ装置３に送信する。
そして、例えば次に、セキュリティ装置２は、パラメータ設定手段２ａにおいてr個の整数組(s,q)を定め、線形作用演算手段２ｂにおいて、共通多項式a(x)に対し、線形作用素Σm=0rqm(1-δ)smを作用させる。具体的には、例えば、パラメータ設定手段２ａにおいてs=(s1,s2,…,sr)及びq=(q1,q2,…,qr)を定め、線形作用演算手段２ｂにおいて、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う。なお、体K上のベクトル空間V,V'が与えられたとき、ある作用素A:V→V'が線形作用素であるとは、任意のx,y∈Vに対してA(x+y)=A(x)+A(y)が成り立ち、かつ任意のx∈Vとk∈Kに対してA(kx)=kA(x)が成り立つことである。
【００１４】
その後、共通多項式a(x)に線形作用素Σm=0rqm(1-δ)smを作用させた結果、すなわち、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算結果b(x)は、例えば、r、s、qが、これらの整数パラメータを設定したセキュリティ装置２側において秘密に保たれた状態でセキュリティ装置３に送信される。
一方、セキュリティ装置３は、パラメータ設定手段３ａにおいて、t個の整数組(u,v)を定め、線形作用演算手段３ｂにおいて、共通多項式a(x)に対し、線形作用素Σm=0tvm(1-δ)umを作用させる。具体的には、例えば、パラメータ設定手段３ａにおいてu=(u1,u2,…,ur)及びv=(v1,v2,…,vr)を定め、線形作用演算手段３ｂにおいて、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行う。
【００１５】
その後、共通多項式a(x)に線形作用素Σm=0tvm(1-δ)umを作用させた結果、すなわち、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算結果c(x)は、例えば、t、u、vが、これらの整数パラメータを設定したセキュリティ装置３側において秘密に保たれた状態でセキュリティ装置２に送信される。
セキュリティ装置３から多項式c(x)が送信されたセキュリティ装置２は、例えば、線形作用演算手段２ｃにおいて、多項式c(x)に線形作用素Σm=0rqm(1-δ)smを作用させ共通鍵を生成する。具体的には、例えば、線形作用演算手段２ｂにおいて、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行い、その演算結果を共通鍵K(x)とする。
【００１６】
一方、セキュリティ装置２から多項式b(x)が送信されたセキュリティ装置３は、例えば、線形作用演算手段３ｃにおいて、多項式b(x)に線形作用素Σm=0tvm(1-δ)umを作用させ共通鍵を生成する。具体的には、例えば、線形作用演算手段３ｂにおいて、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行い、その演算結果を共通鍵K(x)とする。
ここで、以上説明した線形作用演算手段２ｂ、２ｃ、３ｂ、３ｃにおいて行われる多項式演算に必要な四則演算の回数は、上述した演算式が示す通り、秘密パラメータ（r,s,k,t,u,v）の大きさに依存しない。したがって、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、鍵配送時にセキュリティ装置２、３によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式に比べ、大幅に利便性が向上する。
【００１７】
次に、本形態の詳細について説明を行う。
図２は、本形態におけるセキュリティシステム１０の全体構成を例示した図である。
図２に例示するように、セキュリティシステム１０は、例えば、相互に共通鍵の配送を行うセキュリティ装置２０、３０、及びセキュリティ装置２０、３０相互を通信可能なように接続するネットワーク４０を有しており、このセキュリティ装置２０、３０は、ネットワーク４０を介し、相互に情報のやり取りが可能なように、有線又は無線によって電気的に接続され、或いは接続可能な状態となっている。
【００１８】
セキュリティ装置２０、３０は、例えば、モデム、ＤＳＵ(Digital Service Unit)、ＮＣＵ(Network Control Unit)、ＴＡ（Terminal Adapter）等のデータ回線終端装置を具備し、或いは接続されたコンピュータによって構成されている。そして、このセキュリティ装置２０、３０には、所定のメールソフトウェアやＷＷＷブラウザがインストールされており、このメールソフトウェアやＷＷＷブラウザを用いることにより、図示していないメールサーバやＷＷＷサーバを介し、セキュリティ装置２０、３０相互間の通信が可能な構成となっている。
【００１９】
ネットワーク４０は、例えば、インターネット、イントラネット、エクストラネット、ＬＡＮ(Local Area Network)、ＷＡＮ(Wide Area Network)、ＶＡＮ(Value Added Network)等であり、その形態について特に制限はない。また、その通信回線も、専用回線、交換回線等、どのようなものでもよく、ネットワーク接続形態もリング型、メッシュ型、スター型、バス型、ツリー型等、特に制限はない。さらに、その回線接続方式も、ポイントツーポイント方式、マルチポイント方式、集線方式等、特に制限はなく、どのようなものであってもよい。
【００２０】
また、ネットワーク４０は、例えば、ＯＳＩ(Open Systems Interconnection)、ＴＣＰ／ＩＰ(Transmission Control Protocol/Internet Protocol)、ＩＥＥＥ８０２．３、ＩＥＥＥ８０２．４、ＩＥＥＥ８０２．５等の所定のプロトコルに基づいて構成されており、セキュリティ装置２０、３０は、このプロトコルに従い、ネットワーク４０を介した情報の受け渡しを行う。
なお、図２では、２つのセキュリティ装置２０、３０によってセキュリティシステム１０を構成しているが、セキュリティ装置２０、３０を、これより多く設け、それらのセキュリティ装置相互間で共通鍵の配送を行う構成としてもよい。
【００２１】
図３は、セキュリティ装置２０のハードウェア構成を例示したブロック図である。
図３に例示するように、セキュリティ装置２０は、例えば、ＣＰＵ（Central processing Unit：中央処理装置）２０ａ、主記憶装置２０ｂ、外部記憶装置２０ｃ、入力装置２０ｄ、記録媒体読書き装置２０ｅ、出力装置２０ｆ、通信制御装置２０ｇ及びバス２０ｈを有しており、通信制御装置２０ｇを介し、ネットワーク４０と通信可能なように接続され、或いは接続可能なように構成されている。
【００２２】
ＣＰＵ２０ａは、例えば、制御装置と演算装置を有するＣＩＳＣ(Complex Instruction Set Computer)方式、或いはＲＩＳＣ(Reduced Instruction Set Computer)方式の中央処理装置であり、図示していない発信器から供給されるクロック信号に同期し、主記憶装置２０ｂに格納されたオペレーティングシステム、アプリケーションプログラム等の各種プログラムの実行を行い、周辺機器の制御、必要データの呼び出し、呼び出したデータの演算・加工、演算・加工後のデータのメモリへの格納、周辺機器への出力等の各種処理を行う。
【００２３】
主記憶装置２０ｂは、例えば、ＣＰＵ２０ａが直接データを読み書きできる記憶装置である。主記憶装置２０ｂには、例えば、オペレーティングシステム、アプリケーションプログラム、データ、周辺機器を制御するドライバ等が読み込まれ、ＣＰＵ２０ａは、この主記憶装置１２に読み込まれたオペレーティングシステム等を実行することにより、一連の処理を行う。主記憶装置２０ｂには、例えば、半導体メモリ等の高速処理可能な記憶素子を用い、この主記憶装置２０ｂ内の物理アドレスは、ページング方式、セグメンテーション方式等の方法により、外部記憶装置２０ｃの仮想アドレス空間に対応付けられる。
【００２４】
外部記憶装置２０ｃは、例えば、磁性体が蒸着された薄い円盤を高速回転させ、この磁性体を磁気ヘッドによって磁化することでデータの記録を行うハードディスク装置等である。
入力装置２０ｄは、例えば、キーボードやマウス等の入出力デバイスである。記録媒体読書き装置２０ｅは、例えば、フレキシブルディスク等への情報の読書き、コンパクト・ディスク等からの情報の読み出し等を行う装置である。
出力装置２０ｆは、例えば、画面表面の蛍光素材に電子ビームを当てることによって映像の表示を行うＣＲＴ(Cathode-ray Tube)ディスプレイ、或いは、電圧を加えた際に分子配列が変化する液晶の性質を利用した液晶ディスプレイ等であり、供給されたアナログ信号をもとに、所定の映像の表示を行う。
【００２５】
通信制御装置２０ｇは、例えば、例えば、ＵＳＡＲＴ(Universal Synchronous and Asynchronous Receiver-Transmitter)等の汎用同期・非同期送受信回路であり、ネットワーク４０を介したデータ送受信時にデータの直列変換等を行う。バス２０ｄは、例えば、データバス、アドレスバス、コントロールバス等によって構成され、ＣＰＵ２０ａ、主記憶装置２０ｂ、外部記憶装置２０ｃ、入力装置２０ｄ、記録媒体読書き装置２０ｅ、出力装置２０ｆ、通信制御装置２０ｇ間のデータ、アドレス情報、制御情報の受け渡しを行う。
【００２６】
なお、ここでは説明を省略するが、セキュリティ装置３０も、例えばこのセキュリティ装置２０と同様なハードウェア構成をとるものとする。
図４は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置２０の処理機能を例示した機能ブロック図である。
図４に例示するように、この例のセキュリティ装置２０は、通信相手と共用される整数係数の共通多項式を生成する共通多項式生成手段２１、共通多項式生成手段２１で生成した共通多項式を通信相手に開示する共通多項式開示手段２２、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定するパラメータ設定手段２３、通信相手と共用される整数係数の共通多項式をa(x)とし、共通多項式の次数をdeg a(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成する線形作用演算手段２４、生成された第１の演算結果を、通信相手に開示する演算結果開示手段２５、通信相手によって演算された第２の演算結果を取得する演算結果取得手段２６、演算結果取得手段２６によって取得された第２の演算結果をc(x)とし、第２の演算結果c(x)の次数をdeg c(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアル集合をIとした場合における、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行う線形作用演算手段２７、セキュリティ装置２０全体を制御する制御手段２８、及び各種の情報を記憶する記憶手段２９を処理機能として有している。
【００２７】
また、この例では、共通多項式生成手段２１は、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段２１ａ、及び擬似乱数発生手段２１ａによって発生させた擬似乱数を用いて所定の整数値を生成し、生成した整数値を係数とする共通多項式を生成する多項式生成手段２１ｂを有しており、パラメータ設定手段２３は、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段２３ａ、及び擬似乱数発生手段２３ａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段２３ｂを有している。さらに、この例では、線形作用演算手段２４は、整数演算を行う整数演算手段２４ａ、多項式の加算演算を行う多項式加算手段２４ｂ及び多項式の微分演算を行う多項式微分手段２４ｃを、線形作用演算手段２７は、整数演算を行う整数演算手段２７ａ、多項式の加算演算を行う多項式加算手段２７ｂ及び多項式の微分演算を行う多項式微分手段２７ｃを、それぞれ有している。
【００２８】
また、図４に例示するように、共通多項式生成手段２１、共通多項式開示手段２２、パラメータ設定手段２３、線形作用演算手段２４、演算結果開示手段２５、演算結果取得手段２６、線形作用演算手段２７、及び記憶手段２９は、制御手段２８への情報の提供及び制御手段２８からの情報の取得の少なくとも一方が可能なように構成されており、共通多項式開示手段２２及び演算結果開示手段２５は、ネットワーク４０への情報の提供が、演算結果取得手段２６は、ネットワーク４０からの情報の取得がそれぞれ可能なように構成されている。
【００２９】
図５は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置３０の処理機能を例示した機能ブロック図である。
図５に例示するように、この例のセキュリティ装置３０は、通信相手と共用される整数係数の共通多項式を受信する共通多項式取得手段３２、パラメータ設定手段３３、線形作用演算手段３４、演算結果開示手段３５、演算結果取得手段３６、線形作用演算手段３７、セキュリティ装置３０全体を制御する制御手段３８、及び記憶手段２９を処理機能として有している。
【００３０】
また、この例では、パラメータ設定手段３３は、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段３３ａ、及び擬似乱数発生手段３３ａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段３３ｂを有している。さらに、この例では、線形作用演算手段３４は、整数演算を行う整数演算手段３４ａ、多項式の加算演算を行う多項式加算手段３４ｂ及び多項式の微分演算を行う多項式微分手段３４ｃを、線形作用演算手段３７は、整数演算を行う整数演算手段３７ａ、多項式の加算演算を行う多項式加算手段３７ｂ及び多項式の微分演算を行う多項式微分手段３７ｃを、それぞれ有している。
【００３１】
また、図５に例示するように、共通多項式取得手段３２、パラメータ設定手段３３、線形作用演算手段３４、演算結果開示手段３５、演算結果取得手段３６、線形作用演算手段３７及び記憶手段３９は、制御手段３８への情報の提供及び制御手段３８からの情報の取得の少なくとも一方が可能なように構成されており、演算結果開示手段３５は、ネットワーク４０への情報の提供が、共通多項式取得手段３２及び演算結果取得手段３６は、ネットワーク４０からの情報の取得がそれぞれ可能なように構成されている。
【００３２】
次に、本形態におけるセキュリティシステム１０、セキュリティ装置２０、３０の処理動作について説明する。
図６は、本形態におけるセキュリティシステム１０、セキュリティ装置２０、３０の処理動作の一例を説明するためのフローチャートである。このフローチャートにおける実線の矢印は、セキュリティシステム１０全体における一連の処理の流れを例示したものであり、破線の矢印は、セキュリティシステム１０全体における一連の処理の流れと、セキュリティ装置２０、３０それぞれ単体での処理の流れが異なる部分について、セキュリティ装置２０、３０単体での処理の流れを例示したものである。なお、ここでは、説明を容易にするため、便宜的に図６のような処理の流れにそって処理動作の説明を行うが、セキュリティ装置２０、３０それぞれが、このフローチャートの流れと異なる順序で処理を行うこととしてもよく、また、セキュリティ装置２０、３０が、平行して、同時にそれぞれの処理を行うこととしてもよい。
【００３３】
以下、このフローチャートに沿って説明を行う。
ステップＳ１：
本ステップでは、セキュリティ装置２０において、整数係数の共通多項式a(x)の設定を行う。
この共通多項式a(x)の設定は、例えば、セキュリティ装置２０の共通多項式生成手段２１において行われる。具体的には、例えば、まず、擬似乱数発生手段２１ａにおいて、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、多項式生成手段２１ｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、多項式の整数係数を設定し、この整数係数を用いて共通多項式a(x)の設定を行う。
このように設定された共通多項式a(x)を特定するための情報は、例えば、制御手段２８に送られ、制御手段２８は、送られた共通多項式a(x)を特定するための情報を、共通多項式開示手段２２及び記憶手段２９に送る。記憶手段２９に送られた共通多項式a(x)を特定するための情報は、例えば、記憶手段２９に記録され、共通多項式開示手段２２に送られた共通多項式a(x)を特定するための情報は、次のステップＳ２の処理に使用される。
【００３４】
ステップＳ２：
本ステップでは、セキュリティ装置２０において、共通多項式a(x)の送信を行う。
共通多項式a(x)の送信は、例えば、セキュリティ装置２０の共通多項式開示手段２２によって行われる。具体的には、例えば、セキュリティ装置２０からセキュリティ装置３０宛の電子メールに、この共通多項式a(x)を特定するための情報を提示し、或いは、セキュリティ装置３０が閲覧可能なインターネット上のホームページに、この共通多項式a(x)を特定するための情報をアップロードすることによって行われる。
このように共通多項式a(x)の送信が行われると、次に、ステップＳ３の処理に移る。
【００３５】
ステップＳ３：
本ステップでは、セキュリティ装置３０において、共通多項式a(x)の受信を行う。
共通多項式a(x)の受信は、例えば、セキュリティ装置３０の共通多項式取得手段３２において行われる。具体的には、例えば、セキュリティ装置３０が、インターネット上のメールサーバにアクセスし、セキュリティ装置２０から送られたセキュリティ装置３０宛の電子メールを受け取ることにより、または、共通多項式a(x)を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された共通多項式a(x)を特定するための情報は、例えば、制御手段３８に送られ、制御手段３８は、送られた共通多項式a(x)を特定するための情報を記憶手段３９に送る。記憶手段３９に送られた共通多項式a(x)を特定するための情報は、例えば、記憶手段３９に記憶され、次のステップＳ４の処理に移る。
【００３６】
ステップＳ４：
本ステップでは、セキュリティ装置２０において、r個の整数組(s,q)の設定を行う。
r個の整数組(s,q)の設定は、例えば、セキュリティ装置２０のパラメータ設定手段２３によって行われる。具体的には、例えば、まず、擬似乱数発生手段２３ａにおいて、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、整数値演算手段２３ｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定のr個の整数組(s,q)、すなわち、s=(s1,s2,…,sr)とq=(q1,q2,…,qr)とを設定する。
設定されたr個の整数組(s,q)を特定するための情報は、例えば、制御手段２８に送られ、制御手段２８は、送られたr個の整数組(s,q)を特定するための情報を、線形作用演算手段２４及び記憶手段２９に送る。記憶手段２９に送られたr個の整数組(s,q)を特定するための情報は、例えば、記憶手段２９に記憶され、線形作用演算手段２４に送られたr個の整数組(s,q)を特定するための情報は、ステップＳ５の処理に使用される。
【００３７】
ステップＳ５：
本ステップでは、セキュリティ装置２０において、多項式の演算を行う。
本ステップにおける多項式の演算は、例えば、セキュリティ装置２０の線形作用演算手段２４において行われる。この多項式の演算を行う場合、例えば、まず、制御手段２８は、ステップＳ１において記憶手段２９に記憶された共通多項式a(x)を特定するための情報を読み込み、その情報を線形作用演算手段２４に送る。この情報が送られた線形作用演算手段２４は、この情報とステップＳ４の処理で送られた情報とを用いた演算により、共通多項式a(x)にΣm=0rqm(1-δ)smを作用させる処理を行う。この例の場合、この共通多項式a(x)にΣm=0rqm(1-δ)smを作用させる具体的な演算方法として、線形作用演算手段２４が有する整数演算手段２４ａ、多項式加算手段２４ｂ及び多項式微分手段２４ｃを用い、b(x)=Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う。なお、ここで、このようなイデアル集合Iによって剰余演算を行う理由については後述する。
このような演算の結果を示す多項式b(x)を特定するための情報は、例えば、制御手段２８に送られ、制御手段２８は、送られた多項式b(x)を特定するための情報を、演算結果開示手段２５に送る。演算結果開示手段２５にこの情報が送られると、次に、ステップＳ６の処理に移る。
【００３８】
ステップＳ６：
本ステップでは、セキュリティ装置２０において、多項式b(x)を送信する。
多項式b(x)の送信は、例えば、セキュリティ装置２０の演算結果開示手段２５によって行われるが、この際、r個の整数組(s,q)は開示されず、このr個の整数組(s,q)をセキュリティ装置２０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置２０からセキュリティ装置３０宛の電子メールに、この多項式b(x)を特定するための情報を、r個の整数組(s,q)を特定するための情報を開示することなく提示し、或いは、セキュリティ装置３０が閲覧可能なインターネット上のホームページに、この多項式b(x)を特定するための情報を、r個の整数組(s,q)を特定するための情報を開示することなくアップロードすることによって行われる。
このように多項式b(x)の送信が行われると、次に、ステップＳ７の処理に移る。
【００３９】
ステップＳ７：
本ステップでは、セキュリティ装置３０において、多項式b(x)を受信する。
多項式b(x)の受信は、例えば、セキュリティ装置３０の演算結果取得手段３６において行われる。具体的には、例えば、セキュリティ装置３０が、インターネット上のメールサーバにアクセスし、セキュリティ装置２０から送られたセキュリティ装置３０宛の電子メールを受け取ることにより、または、多項式b(x)を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多項式b(x)を特定するための情報は、例えば、制御手段３８に送られ、制御手段３８は、送られた多項式b(x)を特定するための情報を記憶手段３９に送る。記憶手段３９に送られた多項式b(x)を特定するための情報は、例えば、記憶手段３９に記憶され、次のステップＳ８の処理に移る。
【００４０】
ステップＳ８：
本ステップでは、セキュリティ装置３０において、t個の整数組(u,v)の設定を行う。
t個の整数組(u,v)の設定は、例えば、セキュリティ装置３０のパラメータ設定手段３３によって行われる。具体的には、例えば、まず、擬似乱数発生手段３３ａにおいて、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、整数値演算手段３３ｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定のt個の整数組(u,v)、すなわち、u=(u1,u2,…,ut)とv=(v1,v2,…,vt)とを設定する。
設定されたt個の整数組(u,v)を特定するための情報は、例えば、制御手段３８に送られ、制御手段３８は、送られたt個の整数組(u,v)を特定するための情報を、線形作用演算手段３４及び記憶手段３９に送る。記憶手段３９に送られたt個の整数組(u,v)を特定するための情報は、例えば、記憶手段３９に記憶され、線形作用演算手段３４に送られたt個の整数組(u,v)を特定するための情報は、ステップＳ９の処理に使用される。
【００４１】
ステップＳ９：
本ステップでは、セキュリティ装置３０において、多項式の演算を行う。
本ステップにおける多項式の演算は、例えば、セキュリティ装置３０の線形作用演算手段３４において行われる。この多項式の演算を行う場合、例えば、まず、制御手段３８は、ステップＳ３において記憶手段３９に記憶された共通多項式a(x)を特定するための情報を読み込み、その情報を線形作用演算手段３４に送る。この情報が送られた線形作用演算手段３４は、この情報とステップＳ８の処理で送られた情報とを用いた演算により、共通多項式a(x)にΣm=0tvm(1-δ)umを作用させる処理を行う。この例の場合、この共通多項式a(x)にΣm=0rvm(1-δ)umを作用させる具体的な演算方法として、線形作用演算手段３４が有する整数演算手段３４ａ、多項式加算手段３４ｂ及び多項式微分手段３４ｃを用い、c(x)=Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行う。なお、ここで、このようなイデアル集合Iによって剰余演算を行う理由については後述する。
このような演算の結果を示す多項式c(x)を特定するための情報は、例えば、制御手段３８に送られ、制御手段３８は、送られた多項式c(x)を特定するための情報を、演算結果開示手段３５に送る。演算結果開示手段３５にこの情報が送られると、次に、ステップＳ１０の処理に移る。
【００４２】
ステップＳ１０：
本ステップでは、セキュリティ装置３０において、多項式c(x)を送信する。
多項式c(x)の送信は、例えば、セキュリティ装置３０の演算結果開示手段３５によって行われるが、この際、t個の整数組(u,v)は開示されず、このt個の整数組(u,v)をセキュリティ装置３０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置３０からセキュリティ装置２０宛の電子メールに、この多項式c(x)を特定するための情報を、t個の整数組(u,v)を特定するための情報を開示することなく提示し、或いは、セキュリティ装置２０が閲覧可能なインターネット上のホームページに、この多項式c(x)を特定するための情報を、t個の整数組(u,v)を特定するための情報を開示することなくアップロードすることによって行われる。
このように多項式c(x)の送信が行われると、次に、ステップＳ１１の処理に移る。
【００４３】
ステップＳ１１：
本ステップでは、セキュリティ装置２０において、多項式c(x)を受信する。
多項式c(x)の受信は、例えば、セキュリティ装置２０の演算結果取得手段２６において行われる。具体的には、例えば、セキュリティ装置２０が、インターネット上のメールサーバにアクセスし、セキュリティ装置３０から送られたセキュリティ装置２０宛の電子メールを受け取ることにより、または、多項式c(x)を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多項式c(x)を特定するための情報は、例えば、制御手段２８に送られ、制御手段２８は、送られた多項式c(x)を特定するための情報を記憶手段２９に送る。記憶手段２９に送られた多項式c(x)を特定するための情報は、例えば、記憶手段２９に記憶され、次のステップＳ１２の処理に移る。
【００４４】
ステップＳ１２：
本ステップでは、セキュリティ装置２０において、共通鍵k(x)の算出を行う。本ステップにおける共通鍵k(x)の算出は、例えば、セキュリティ装置２０の線形作用演算手段２７において行われる。共通鍵k(x)の算出を行う場合、例えば、まず、制御手段２８は、ステップＳ４において記憶手段２９に記憶されたr個の整数組(s,q)と、ステップＳ１１において記憶手段２９に記憶された多項式c(x)を特定するための情報とを読み込み、それらの情報を線形作用演算手段２７に送る。この情報が線形作用演算手段２７に送られると、例えば、この線形作用演算手段２７は、多項式c(x)にΣm=0rqm(1-δ)smを作用させる処理を行う。この例の場合、線形作用演算手段２７が有する整数演算手段２７ａ、多項式加算手段２７ｂ及び多項式微分手段２７ｃを用い、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行い、その結果を、共通鍵k(x)として出力する。なお、ここで、このようなイデアル集合Iによって剰余演算を行う理由については後述する。
【００４５】
ステップＳ１３：
本ステップでは、セキュリティ装置３０において、共通鍵k(x)の算出を行う。本ステップにおける共通鍵k(x)の算出は、例えば、セキュリティ装置３０の線形作用演算手段３７において行われる。共通鍵k(x)の算出を行う場合、例えば、まず、制御手段３８は、ステップＳ８において記憶手段３９に記憶されたt個の整数組(u,v)と、ステップＳ７において記憶手段３９に記憶された多項式b(x)を特定するための情報とを読み込み、それらの情報を線形作用演算手段３７に送る。この情報が線形作用演算手段３７に送られると、例えば、この線形作用演算手段３７は、多項式b(x)にΣm=0tvm(1-δ)umを作用させる処理を行う。この例の場合、線形作用演算手段３７が有する整数演算手段３７ａ、多項式加算手段３７ｂ及び多項式微分手段３７ｃを用い、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行い、その結果を、共通鍵k(x)として出力する。
【００４６】
以上の処理により、セキュリティ装置２０、３０間において共通鍵k(x)の配送が行われたことになるが、次に、このセキュリティ装置２０、３０それぞれで算出された共通鍵k(x)の同一性、及び上述のステップＳ５、Ｓ９、Ｓ１２、Ｓ１３の処理において、前述のイデアル集合Iによって剰余演算を行った理由について説明する。
前述のように、イデアル集合Iは、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合である。この場合、この整数係数の多項式をg(x)、任意の整数値をkとすると、このイデアル集合I に対し、g(x)∈Iならばg(x+k)∈Iであるという関係が満たされることとなる。
【００４７】
ここで、w(x)≡r(x)modIとする。つまり、g(x)∈Iとp(x)∈Z[x]が存在して、w(x)=p(x)・g(x)+r(x)と書けるとする。なお、ここで、Z[x]は、整数係数の多項式全体の集合を表す。この式の両辺について、xをx＋kで置き換えると、w(x+k)=p(x+k)・g(x+k)+r(x+k)となるが、上述のように、g(x+k)∈Iが満たされるため、w(x+k)≡r(x+k)modIという関係も成立することになる。すなわち、前述のようなイデアル集合Iである限り、w(x)≡r(x)modIという関係が成立すれば、必ず、w(x+k)≡r(x+k)modIという関係も成立することになる。これは、このイデアル集合Iの代わりに、このイデアル集合Iでない集合で剰余演算を行った場合には、必ずしも成立しない関係である。
【００４８】
さらに、このように、w(x)≡r(x)modIという関係が成立すれば、必ず、w(x+k)≡r(x+k)modIという関係も成立するということが言える場合、任意の整数kと任意の多項式w(x)について、Iでの剰余演算を行った後に、xをx+kに置き換えた多項式と、xをx+kに置き換えた後に、Iでの剰余演算を行った多項式とは同一となることが言える。
そして、前述のように、(1-δ)sは、任意の多項式g(x)に対して多項式g(x-s)を対応させる作用素を意味するため、任意の整数kと任意の多項式w(x)について、Iでの剰余演算を行った後に、xをx+kに置き換えた多項式と、xをx+kに置き換えた後に、Iでの剰余演算を行った多項式とは同一となることが言える場合、例えば、セキュリティ装置２０において、b(x)を算出するためにIでの剰余演算を行った後に、セキュリティ装置３０において、k(x)を算出するためにb(x)に(1-δ)uを作用させた演算結果、すなわちb(x)に対してb(x-u)を対応させた演算結果と、セキュリティ装置３０において、c(x)を算出するためにa(x)に(1-δ)uを作用させた後、すなわちa(x)に対してa(x-u)を対応させた後に、セキュリティ装置２０において、k(x)を算出するためにIでの剰余演算を行った結果とは等しくなることが言える。これは、sについても同様である。結果、前述したようなイデアル集合Iによって剰余演算が行われる場合、セキュリティ装置２０、３０それぞれで算出される共通鍵k(x)は同一となる。
【００４９】
このように本形態の例では、パラメータ設定手段２３、３３において、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータ（r個の整数組(s,q)、t個の整数組(u,v)）を設定し、線形作用演算手段２４、２７、３４、３７において、集合（a(x)、b(x)、c(x)）に対し、Σm=0rqm(1-δ)sm或いはΣm=0tvm(1-δ)um作用させることとしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、鍵配送時にセキュリティ装置２０、３０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式に比べ、大幅に利便性が向上する。
【００５０】
また、本形態の例では、多くの秘密パラメータ（r,s,k,t,u,v）を有する線形作用素を作用させた演算結果を用いて共通鍵の配送を行う構成としたため、第三者による共通鍵の解読が大幅に困難となり、結果、共通鍵に対する安全性が十分確保できる。
さらに、本形態の例では、線形作用演算手段２４、２７、３４、３７において、b(x)=Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modI、c(x)=Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modI、k(x)=Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modI、k(x)=Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行うこととしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、鍵配送時にセキュリティ装置２０、３０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式に比べ、大幅に利便性が向上する。
【００５１】
また、線形作用演算手段２４、３４において、b(x)=Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modI、c(x)=Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行い、これらの演算結果を、演算結果開示手段２５、３５において通信相手に開示し、演算結果取得手段２６、３６において、通信相手によって演算された演算結果を取得し、線形作用演算手段２７、３７において、k(x)=Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modI、k(x)=Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行うこととしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、鍵配送時にセキュリティ装置２０、３０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式に比べ、大幅に利便性が向上する。
【００５２】
さらに、本形態の例において、イデアル集合として、整数係数の多項式がなす環のイデアルであって、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、degf(x)をf(x)の次数とした場合における、｛f(x), δf(x),δ2f(x),…,δdegf(x)f(x)｝によって生成される集合であるものを用いることにより、前述のように、セキュリティ装置２０、３０それぞれで算出された共通鍵k(x)が同一となり、本形態における鍵配送が実質的に可能となる。
また、本形態の例では、r個の整数組(s,q)をセキュリティ装置２０側で秘密に保ち、t個の整数組(u,v)をセキュリティ装置３０側で秘密に保つこととしたため、共通鍵k(x)の内容を第三者に知られることなく、セキュリティ装置２０、３０相互間での鍵配送が可能となる。
【００５３】
さらに、本形態の例では、セキュリティ装置２０の擬似乱数発生手段２３ａによって発生させた乱数を用いてr個の整数組(s,q)を生成し、セキュリティ装置３０の擬似乱数発生手段３３ａによって発生させた乱数を用いてt個の整数組(u,v)を生成することとしたため、r個の整数組(s,q)及びt個の整数組(u,v)の保守性が向上し、結果、共通鍵k(x)に対する安全性が向上する。
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、コンピュータ上で所定のプログラムを実行させることにより、本形態におけるセキュリティ装置２０、３０を構成することとしたが、これらの処理内容の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
【００５４】
また、本形態では、線形作用演算手段２４、２７、３４、３７において、a(x)、b(x)或いはc(x)に対し、線形作用素Σm=0rqm(1-δ)sm或いはΣm=0tvm(1-δ)umを作用させることとしたが、線形作用素を演算するために必要な整数の四則演算の回数が、多項式の次数の対数の多項式のオーダー以下となる線形作用素であれば、他の線形作用素を作用させることとしてもよい。
次に、本発明における第２の実施の形態について説明する。
ここでも、まず、本形態の概略について説明を行い、その後、本形態の詳細について説明を行っていく。
【００５５】
図７は、本形態におけるセキュリティシステム５０の概略を説明するための図である。
図７に例示するように、セキュリティシステム５０は、セキュリティ装置５１、５２によって構成されており、セキュリティ装置５１によって公開された公開鍵を用いてセキュリティ装置５２において暗号文を生成し、この暗号文をセキュリティ装置５１において復号する。
この例の場合、セキュリティ装置５１は、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定手段５１ａ、及び集合に対し、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とした場合における、Σm=0rqm(1-δ)smを作用させる線形作用演算手段５１ｂ、５１ｃを有しており、同じく、セキュリティ装置５２は、第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定する第２のパラメータ設定手段５２ａ、及び集合に対し、第３の整数パラメータをumとし、第４の整数パラメータをvmとし、第２の個数をtとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とした場合における、Σm=0tvm(1-δ)umを作用させる線形作用演算手段５２ｂ、５２ｃを有している。
【００５６】
また、第１の実施の形態と同様、この例の場合、線形作用演算手段５１ｂは、所定の多項式をa(x)とし、該多項式の次数をdeg a(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う手段となっている。この点、線形作用演算手段５１ｃ、５２ｂ、５２ｃについても同様である。
【００５７】
本形態におけるセキュリティシステム５０において、セキュリティ装置５１において公開鍵暗号方式による暗号化を行い、セキュリティ装置５２においてその復号を行う場合、例えば、まず、セキュリティ装置５１は、整数係数の多項式である共通多項式a(x)を生成し、生成した共通多項式a(x)をセキュリティ装置５２に送信する。
そして、例えば次に、セキュリティ装置５１は、パラメータ設定手段５１ａにおいてr個の整数組(s,q)を定め、線形作用演算手段５１ｂにおいて、共通多項式a(x)に対し、線形作用素Σm=0rqm(1-δ)smを作用させる。具体的には、例えば、パラメータ設定手段５１ａにおいてs=(s1,s2,…,sr)及びq=(q1,q2,…,qr)を定め、線形作用演算手段５１ｂにおいて、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う。
【００５８】
その後、共通多項式a(x)に線形作用素Σm=0rqm(1-δ)smを作用させた結果、すなわち、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算結果b(x)は、例えば、r、s、q（秘密鍵）が、これらの整数パラメータを設定したセキュリティ装置２側において秘密に保たれた状態でセキュリティ装置５２に公開鍵として送信される。
一方、暗号化する平文Mが、M∈{0,1}lとなる場合、セキュリティ装置５２は、パラメータ設定手段５２ａにおいてt個の整数組(u,v)を定め、セキュリティ装置５１から送信されたb(x)に線形作用素Σm=0tvm(1-δ)umを作用させる。具体的には、例えば、パラメータ設定手段５２ａにおいてu=(u1,u2,…,ur)及びv=(v1,v2,…,vr)を定め、線形作用演算手段５２ｂにおいて、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行い、共通鍵k(x)を生成する。その後、この共通鍵k(x)に対し、多項式に値を持つハッシュ関数H（演算結果の値域が十分大きい集合となることが好ましく、この値域が、例えば、280項以上程度の元からなる集合であるものがより好ましい）を作用させ、H(k(x))∈{0,1}lを得る。そして、このH(k(x))と平文Ｍとの排他的論理和（H(k(x))(+)M）を暗号文として演算する。なお、図７及び本形態の説明において、「a(+)b」はaとbとの排他的論理和を意味するものとする。
【００５９】
また、セキュリティ装置５２は、線形作用演算手段５２ｂにおいて、共通多項式a(x)に対し、線形作用素Σm=0tvm(1-δ)umを作用させる。具体的には、例えば、線形作用演算手段５２ｂにおいて、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行い、その演算結果c(x)を生成する。そして、このように生成された（H(k(x))(+)M）とc(x)とは、暗号文C=(c(x),H(k(x))(+)M)として、セキュリティ装置５１に送信される。
暗号文C=(c(x),H(k(x))(+)M)が送信されたセキュリティ装置５１は、線形作用演算手段５１ｃにおいて、送信されたc(x)に対し、線形作用素Σm=0rqm(1-δ)smを作用させる。具体的には、例えば、線形作用演算手段５１ｃにおいて、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行い、k(x)を生成する。そして、この演算結果k(x)に対し、セキュリティ装置５２で用いたものと同じハッシュ関数Hを作用させ、H(k(x))∈{0,1}lを得た後、このように得られたH(k(x))と、暗号文CのH(k(x))(+)Mとの排他的論理和を演算する
（H(k(x))(+)(H(k(x))(+)M)）。ここで、前述した第１の実施の形態の場合と同様、セキュリティ装置５１で生成されたk(x)と、セキュリティ装置５２で生成されたk(x)とは同一となっている。そのため、このH(k(x))(+)(H(k(x))(+)M)の演算結果はMとなり、これにより、平文Mが復号されたことになる。
【００６０】
ここで、以上説明した線形作用演算手段５１ｂ、５１ｃ、５２ｂ、５２ｃにおいて行われる多項式演算に必要な四則演算の回数は、上述した演算式が示す通り、秘密パラメータ（r,s,k,t,u,v）の大きさに依存しない。したがって、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、暗号化或いは復号の際、セキュリティ装置５１、５２によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００６１】
次に、本形態の詳細について説明を行う。
図８は、本形態におけるセキュリティシステム６０の全体構成を例示した図である。
図８に例示するように、セキュリティシステム６０は、例えば、公開鍵暗号方式によって、平文の暗号化及び復号を行うセキュリティ装置７０、８０、及びセキュリティ装置７０、８０相互を通信可能なように接続するネットワーク９０を有しており、このセキュリティ装置７０、８０は、ネットワーク９０を介し、相互に情報のやり取りが可能なように、有線又は無線によって電気的に接続され、或いは接続可能な状態となっている。なお、この全体構成についての詳細は、例えば、第１の実施の形態で説明したものと同様であり、また、セキュリティ装置７０、８０のハードウェア構成は、例えば、第１の実施の形態におけるセキュリティ装置２０、３０のハードウェア構成（図３）と同様のものとする。
【００６２】
図９は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置７０の処理機能を例示した機能ブロック図である。
図９に例示するように、この例のセキュリティ装置７０は、通信相手と共用される整数係数の共通多項式を生成する共通多項式生成手段７１、共通多項式生成手段７１で生成した共通多項式を通信相手に開示する共通多項式開示手段７２、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定するパラメータ設定手段７３、通信相手と共用される整数係数の共通多項式をa(x)とし、共通多項式の次数をdeg a(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成する線形作用演算手段７４、生成された第１の演算結果を、公開鍵として公開する公開鍵公開手段７５、通信相手によって演算された第２の演算結果と、暗号文とを、取得する暗号文取得手段７６、復号を行う復号手段７７、セキュリティ装置７０全体を制御する制御手段７８、及び各種の情報を記憶する記憶手段７９を処理機能として有している。
【００６３】
また、この例では、共通多項式生成手段７１は、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段７１ａ、及び擬似乱数発生手段７１ａによって発生させた擬似乱数を用いて所定の整数値を生成し、生成した整数値を係数とする共通多項式を生成する多項式生成手段７１ｂを有しており、パラメータ設定手段７３は、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段７３ａ、及び擬似乱数発生手段７３ａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段７３ｂを有している。また、この例では、線形作用演算手段７４は、整数演算を行う整数演算手段７４ａ、多項式の加算演算を行う多項式加算手段７４ｂ及び多項式の微分演算を行う多項式微分手段７４ｃを有しており、復号手段７７は、暗号文取得手段７６によって取得された第２の演算結果をc(x)とし、第２の演算結果の次数をdeg c(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアル集合をIとした場合における、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行うことにより、第３の演算結果を生成する線形作用演算手段７７ａ、セキュリティ装置８０と共通のハッシュ関数Hの演算を行うハッシュ関数演算手段７７ｂ、及び生成された第３の演算結果と、暗号文と、の排他的論理和を演算する排他的論理和演算手段７７ｃを有している。さらに、この例における線形作用演算手段７７ａは、整数演算を行う整数演算手段７７ａａ、多項式の加算演算を行う多項式加算手段７７ａｂ及び多項式の微分演算を行う多項式微分手段７７ａｃを有している。
【００６４】
なお、第２の実施の形態における例では、多項式に値を持つハッシュ関数Hは、例えば、Z(x)/I1→{0,1}lの演算を行う関数である。ここで、Z(x)/I1とは、整数係数の多項式環Z(x)とそのイデアルI1とが与えられ、p,q∈Z(x)についてp-q∈I1を満たす場合に、このpとqとを同一の類とみなしてZ(x)の元を類別し、その類別された類ひとつひとつを新たに元とみなした場合に作られる集合（Z(x)のIによる剰余環）を意味する。また、前述のように、ハッシュ関数Hは、その演算結果の値域が十分大きい集合となることが望ましいが、このようなハッシュ関数Hの構成は、例えば、ブックバーガーのアルゴリズム等を用い、Z(x)のイデアルI1についてグレブナー基底を１つ定め、このグレブナー基底により、Z(x)/I1のそれぞれの類において、その類を代表する多項式を定めることによって行う。なお、ここでZ[x]のイデアルI1のグレブナー基底は、I1を生成する有限集合G=｛f1(x), f2(x),…,fn(x)｝であって、任意のf(x)∈Z(x)について、f(x)をf1(x)で割った余りをとり、次に、その余りをf2(x)で割った余りをとり、以下同様に繰り返した後、最後にfn(x)で割った余りをとった結果が、f1(x), f2(x),…,fn(x)の順序に依存しない性質をもつ。
【００６５】
また、図９に例示するように、共通多項式生成手段７１、共通多項式開示手段７２、パラメータ設定手段７３、線形作用演算手段７４、公開鍵公開手段７５、暗号文取得手段７６、復号手段７７、及び記憶手段７９は、制御手段７８への情報の提供及び制御手段７８からの情報の取得の少なくとも一方が可能なように構成されており、共通多項式開示手段７２及び公開鍵公開手段７５は、ネットワーク９０への情報の提供が、暗号文取得手段７６は、ネットワーク９０からの情報の取得がそれぞれ可能なように構成されている。
【００６６】
図１０は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置８０の処理機能を例示した機能ブロック図である。
図１０に例示するように、この例のセキュリティ装置８０は、通信相手と共用される整数係数の共通多項式を受信する共通多項式取得手段８２、第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定するパラメータ設定手段８３、通信相手によって公開された第１の演算結果を、公開鍵として取得する公開鍵取得手段８４、暗号文の生成を行う暗号文生成手段８５、通信相手と共用される整数係数の共通多項式をa(x)とし、共通多項式の次数をdeg a(x)とし、第１の整数パラメータをumとし、第２の整数パラメータをvmとし、第１の個数をtとし、∂を微分作用素とし、イデアル集合をIとした場合における、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第３の演算結果を生成する線形作用演算手段８６、以下に述べる排他的論理和演算手段８５ｃによって演算された暗号文と、線形作用演算手段８５ａによって生成された第３の演算結果とを開示する暗号文開示手段８７、セキュリティ装置８０全体を制御する制御手段８８、及び各種の情報を記憶する記憶手段８９を処理機能として有している。
【００６７】
また、この例では、パラメータ設定手段８３は、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段８３ａ、及び擬似乱数発生手段８３ａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段８３ｂを有している。また、この例では、暗号文生成手段８５は、公開鍵取得手段８４によって取得された第１の演算結果をb(x)とし、第１の演算結果の次数をdeg b(x)とし、第１の整数パラメータをumとし、第２の整数パラメータをvmとし、第１の個数をtとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行うことにより、第２の演算結果を生成する線形作用演算手段８５ａ、セキュリティ装置７０と共通のハッシュ関数Hの演算を行うハッシュ関数演算手段８５ｂ、及び生成された第２の演算結果と、通信内容である平文との排他的論理和を、暗号文として演算する排他的論理和演算手段８５ｃを有しており、さらに線形作用演算手段８５ａは、整数演算を行う整数演算手段８５ａａ、多項式の加算演算を行う多項式加算手段８５ａｂ及び多項式の微分演算を行う多項式微分手段８５ａｃを、線形作用演算手段８６は、整数演算手段８６ａ、多項式加算手段８６ｂ及び多項式微分手段８６ｃをそれぞれ有している。
【００６８】
また、図１０に例示するように、共通多項式取得手段８２、パラメータ設定手段８３、公開鍵取得手段８４、暗号文生成手段８５、線形作用演算手段８６、暗号文開示手段８７、及び記憶手段８９は、制御手段８８への情報の提供及び制御手段８８からの情報の取得の少なくとも一方が可能なように構成されており、暗号文開示手段８７は、ネットワーク９０への情報の提供が、共通多項式取得手段８２及び公開鍵取得手段８４は、ネットワーク９０からの情報の取得がそれぞれ可能なように構成されている。
【００６９】
次に、本形態におけるセキュリティシステム６０、セキュリティ装置７０、８０の処理動作について説明する。
図１１は、本形態におけるセキュリティシステム６０、セキュリティ装置７０、８０の処理動作の一例を説明するためのフローチャートである。このフローチャートにおける実線の矢印は、セキュリティシステム６０全体における一連の処理の流れを例示したものであり、破線の矢印は、セキュリティシステム６０全体における一連の処理の流れと、セキュリティ装置７０、８０それぞれ単体での処理の流れが異なる部分について、セキュリティ装置７０、８０単体での処理の流れを例示したものである。なお、ここでは、説明を容易にするため、便宜的に図１１のような処理の流れにそって処理動作の説明を行うが、セキュリティ装置７０、８０それぞれが、このフローチャートの流れと異なる順序で処理を行うこととしてもよく、また、セキュリティ装置７０、８０が、平行して、同時にそれぞれの処理を行うこととしてもよい。
【００７０】
以下、このフローチャートに沿って説明を行う。
ステップＳ２０：
本ステップでは、セキュリティ装置７０において、共通多項式a(x)の設定を行う。
この共通多項式a(x)の設定は、例えば、セキュリティ装置７０の共通多項式生成手段７１において行われる。具体的には、例えば、まず、擬似乱数発生手段７１ａにおいて、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、多項式生成手段７１ｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、多項式の整数係数を設定し、この整数係数を用いて共通多項式a(x)の設定を行う。
このように設定された共通多項式a(x)を特定するための情報は、例えば、制御手段７８に送られ、制御手段７８は、送られた共通多項式a(x)を特定するための情報を、共通多項式開示手段７２及び記憶手段７９に送る。記憶手段７９に送られた共通多項式a(x)を特定するための情報は、例えば、記憶手段７９に記録され、共通多項式開示手段７２に送られた共通多項式a(x)を特定するための情報は、次のステップＳ２１の処理に使用される。
【００７１】
ステップＳ２１：
本ステップでは、セキュリティ装置７０において、共通多項式a(x)の送信を行う。
共通多項式a(x)の送信は、例えば、セキュリティ装置７０の共通多項式開示手段７２によって行われる。具体的には、例えば、セキュリティ装置７０からセキュリティ装置８０宛の電子メールに、この共通多項式a(x)を特定するための情報を提示し、或いは、セキュリティ装置８０が閲覧可能なインターネット上のホームページに、この共通多項式a(x)を特定するための情報をアップロードすることによって行われる。
このように共通多項式a(x)の送信が行われると、次に、ステップＳ２２の処理に移る。
【００７２】
ステップＳ２２：
本ステップでは、セキュリティ装置８０において、共通多項式a(x)の受信を行う。
共通多項式a(x)の受信は、例えば、セキュリティ装置８０の共通多項式取得手段８２において行われる。具体的には、例えば、セキュリティ装置８０が、インターネット上のメールサーバにアクセスし、セキュリティ装置７０から送られたセキュリティ装置８０宛の電子メールを受け取ることにより、または、共通多項式a(x)を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された共通多項式a(x)を特定するための情報は、例えば、制御手段８８に送られ、制御手段８８は、送られた共通多項式a(x)を特定するための情報を記憶手段８９に送る。記憶手段８９に送られた共通多項式a(x)を特定するための情報は、例えば、記憶手段８９に記憶され、次のステップＳ２３の処理に移る。
【００７３】
ステップＳ２３：
本ステップでは、セキュリティ装置７０において、r個の整数組(s,q)の設定を行う。
r個の整数組(s,q)の設定は、例えば、セキュリティ装置７０のパラメータ設定手段７３によって行われる。具体的には、例えば、まず、擬似乱数発生手段７３ａにおいて、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、整数値演算手段７３ｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定のr個の整数組(s,q)、すなわち、s=(s1,s2,…,sr)とq=(q1,q2,…,qr)とを設定する。
設定されたr個の整数組(s,q)を特定するための情報は、例えば、制御手段７８に送られ、制御手段７８は、送られたr個の整数組(s,q)を特定するための情報を、線形作用演算手段７４及び記憶手段７９に送る。記憶手段７９に送られたr個の整数組(s,q)を特定するための情報は、例えば、記憶手段７９に記憶され、線形作用演算手段７４に送られたr個の整数組(s,q)を特定するための情報は、ステップＳ２４の処理に使用される。
【００７４】
ステップＳ２４：
本ステップでは、セキュリティ装置７０において、多項式の演算を行う。
本ステップにおける多項式の演算は、例えば、セキュリティ装置７０の線形作用演算手段７４において行われる。この多項式の演算を行う場合、例えば、まず、制御手段７８は、ステップＳ２０において記憶手段７９に記憶された共通多項式a(x)を特定するための情報を読み込み、その情報を線形作用演算手段７４に送る。この情報が送られた線形作用演算手段７４は、この情報とステップＳ２３の処理で送られた情報とを用いた演算により、共通多項式a(x)にΣm=0rqm(1-δ)smを作用させる処理を行う。この例の場合、この共通多項式a(x)にΣm=0rqm(1-δ)smを作用させる具体的な演算方法として、線形作用演算手段７４が有する整数演算手段７４ａ、多項式加算手段７４ｂ及び多項式微分手段７４ｃを用い、b(x)=Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う。
このような演算の結果を示す多項式b(x)を特定するための情報は、例えば、制御手段７８に送られ、制御手段７８は、送られた多項式b(x)を特定するための情報を、公開鍵公開手段７５に送る。公開鍵公開手段７５にこの情報が送られると、次に、ステップＳ２５の処理に移る。
【００７５】
ステップＳ２５：
本ステップでは、セキュリティ装置７０において、多項式b(x)を公開鍵として送信する。
多項式b(x)の送信は、例えば、セキュリティ装置７０の公開鍵公開手段７５によって行われるが、この際、r個の整数組(s,q)は開示されず、このr個の整数組(s,q)をセキュリティ装置７０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置７０からセキュリティ装置８０宛の電子メールに、この多項式b(x)を特定するための情報を、r個の整数組(s,q)を特定するための情報を開示することなく提示し、或いは、セキュリティ装置８０が閲覧可能なインターネット上のホームページに、この多項式b(x)を特定するための情報を、r個の整数組(s,q)を特定するための情報を開示することなくアップロードすることによって行われる。
このように多項式b(x)の送信が行われると、次に、ステップＳ２６の処理に移る。
【００７６】
ステップＳ２６：
本ステップでは、セキュリティ装置８０において、多項式b(x)を受信する。
多項式b(x)の受信は、例えば、セキュリティ装置８０の演算結果取得手段８６において行われる。具体的には、例えば、セキュリティ装置８０が、インターネット上のメールサーバにアクセスし、セキュリティ装置７０から送られたセキュリティ装置８０宛の電子メールを受け取ることにより、または、多項式b(x)の演算結果を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多項式b(x)を特定するための情報は、例えば、制御手段８８に送られ、制御手段８８は、送られた多項式b(x)を特定するための情報を記憶手段８９に送る。記憶手段８９に送られた多項式b(x)を特定するための情報は、例えば、記憶手段８９に記憶され、次のステップＳ２７の処理に移る。
【００７７】
ステップＳ２７：
本ステップでは、セキュリティ装置８０において、t個の整数組(u,v)の設定を行う。
t個の整数組(u,v)の設定は、例えば、セキュリティ装置８０のパラメータ設定手段８３によって行われる。具体的には、例えば、まず、擬似乱数発生手段８３ａにおいて、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、整数値演算手段８３ｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定のt個の整数組(u,v)、すなわち、u=(u1,u2,…,ut)とv=(v1,v2,…,vt)とを設定する。
設定されたt個の整数組(u,v)を特定するための情報は、例えば、制御手段８８に送られ、制御手段８８は、送られたt個の整数組(u,v)を特定するための情報を、線形作用演算手段８４及び記憶手段８９に送る。記憶手段８９に送られたt個の整数組(u,v)を特定するための情報は、例えば、記憶手段８９に記憶され、線形作用演算手段８４に送られたt個の整数組(u,v)を特定するための情報は、ステップＳ２８の処理に使用される。
【００７８】
ステップＳ２８：
本ステップでは、セキュリティ装置８０において、多項式の演算を行う。
本ステップにおける多項式の演算は、例えば、セキュリティ装置８０の線形作用演算手段８６において行われる。この多項式の演算を行う場合、例えば、まず、制御手段８８は、ステップＳ３において記憶手段８９に記憶された共通多項式a(x)を特定するための情報を読み込み、その情報を線形作用演算手段８６に送る。この情報が送られた線形作用演算手段８６は、この情報とステップＳ２７の処理で送られた情報とを用いた演算により、共通多項式a(x)にΣm=0tvm(1-δ)umを作用させる処理を行う。この例の場合、この共通多項式a(x)にΣm=0rvm(1-δ)umを作用させる具体的な演算方法として、線形作用演算手段８６が有する整数演算手段８６ａ、多項式加算手段８６ｂ及び多項式微分手段８６ｃを用い、c(x)=Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行う。
このような演算の結果を示す多項式c(x)を特定するための情報は、例えば、制御手段８８に送られ、制御手段８８は、送られた多項式c(x)を特定するための情報を、記憶手段８９に送る。記憶手段８９に送られた多項式c(x)を特定するための情報は、例えば、記憶手段８９に記憶され、次のステップＳ２９の処理に移る。
【００７９】
ステップＳ２９：
本ステップでは、セキュリティ装置８０において、演算によって暗号文Ｃを生成する。
暗号文Ｃの演算は、例えば、セキュリティ装置８０の暗号文生成手段８５において行われる。なお、ここでは、平文M∈{0,1}lを暗号化する場合を例にとって説明する。
暗号文Ｃの演算を行う場合、まず、セキュリティ装置８０は、例えば、制御手段８８によって、ステップＳ２６において記憶手段８９に記憶された多項式b(x)を特定するための情報、及びステップＳ２６において記憶手段８９に記憶されたt個の整数組(u,v)を特定するための情報を読み込み、これらの情報を暗号文生成手段８５に送る。これらの情報が送られた暗号文生成手段８５は、例えば、線形作用演算手段８５ａにおいて、多項式b(x)にΣm=0tvm(1-δ)umを作用させる処理を行う。この例の場合、この多項式b(x)にΣm=0rvm(1-δ)umを作用させる具体的な演算方法として、線形作用演算手段８５ａが有する整数演算手段８５ａａ、多項式加算手段８５ａｂ及び多項式微分手段８５ａｃを用い、ｋ(x)=Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行う。
【００８０】
次に、例えば、ハッシュ関数演算手段８５ｂによって、この演算結果ｋ(x)に対し、ハッシュ関数Hを作用させ（H(k(x))∈{0,1}l）、排他的論理和演算手段８５ｃによって、この演算結果H(k(x))と平文Ｍとの排他的論理和（H(k(x))(+)M)を暗号文として演算する。その後、暗号文生成手段８５は、このように演算された（H(k(x))(+)M)と、ステップＳ２８において演算されたc(x)とを用い、暗号文C=(c(x),H(k(x))(+)M)を生成する。生成された暗号文Cは、例えば、制御手段８８に送られ、制御手段８８は、送られた暗号文Cを暗号文開示手段８７に送る。暗号文Cが暗号文開示手段８７に送られると、次に、ステップＳ３０の処理に移る。
【００８１】
ステップＳ３０：
本ステップでは、セキュリティ装置８０において、暗号文Ｃを送信する。
暗号文Ｃの送信は、例えば、セキュリティ装置８０の暗号文開示手段８７によって行われるが、この際、t個の整数組(u,v)は開示されず、このt個の整数組(u,v)をセキュリティ装置８０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置８０からセキュリティ装置７０宛の電子メールに、この暗号文Cを特定するための情報を、t個の整数組(u,v)を特定するための情報を開示することなく提示し、或いは、セキュリティ装置７０が閲覧可能なインターネット上のホームページに、この暗号文Cを特定するための情報を、t個の整数組(u,v)を特定するための情報を開示することなくアップロードすることによって行われる。
このように暗号文Cの送信が行われると、次に、ステップＳ３１の処理に移る。
【００８２】
ステップＳ３１：
本ステップでは、セキュリティ装置７０において、暗号文Ｃを受信する。
暗号文Cの受信は、例えば、セキュリティ装置７０の暗号文取得手段７６において行われる。具体的には、例えば、セキュリティ装置７０が、インターネット上のメールサーバにアクセスし、セキュリティ装置８０から送られたセキュリティ装置７０宛の電子メールを受け取ることにより、または、暗号文Cを特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された暗号文Cを特定するための情報は、例えば、制御手段７８に送られ、制御手段７８は、送られた暗号文Cを特定するための情報を復号手段７７に送り、次のステップＳ３２の処理に移る。
【００８３】
ステップＳ３２：
本ステップでは、セキュリティ装置７０において、暗号文Ｃの復号を行う。
暗号文Cの復号は、例えば、セキュリティ装置７０の復号手段７７において行われる。具体的には、例えばまず、復号手段７７の線形作用演算手段７７ａにおいて、ステップＳ３１で受信した暗号文C=(c(x),H(k(x))(+)M)を構成する多項式c(x)にΣm=0rqm(1-δ)smを作用させる処理を行う。この例の場合、この多項式c(x)にΣm=0rqm(1-δ)smを作用させる具体的な演算方法として、線形作用演算手段７７ａが有する整数演算手段７７ａａ、多項式加算手段７７ａｂ及び多項式微分手段７７ａｃを用い、k(x)=Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行う。
この演算が行われると、例えば次に、この演算結果k(x)に対し、ハッシュ関数演算手段７７ｂによって、セキュリティ装置８０で用いたものと同じハッシュ関数Hを作用させ、H(k(x))∈{0,1}lを得る。その後、例えば、排他的論理和演算手段７７ｃにおいて、このように得られたH(k(x))とステップＳ３１で受信した暗号文C=(c(x),H(k(x))(+)M)を構成するH(k(x))(+)Mとの排他的論理和を演算する（H(k(x))(+)H(k(x))(+)M）。これにより、前述のように平文Mの復号が行われたことになる。
【００８４】
このように本形態の例では、パラメータ設定手段７３、８３において、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータ（r個の整数組(s,q)、t個の整数組(u,v)）を設定し、線形作用演算手段７４、７７ａ、８５ａ、８６において、集合（a(x)、b(x)、c(x)）に対し、Σm=0rqm(1-δ)sm或いはΣm=0tvm(1-δ)um作用させることとしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、平文の暗号化時及び暗号文の復号時において、セキュリティ装置７０、８０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００８５】
また、本形態の例では、多くの秘密パラメータ（r,s,k,t,u,v）を有する線形作用素を作用させることにより、公開鍵の生成、平文の暗号化及び暗号文の復号を行うこととしたため、第三者による暗号文Cの解読が非常に困難となり、結果、共通鍵に対する安全性が十分確保できる。
さらに、本形態の例では、線形作用演算手段７４、７７、８５ａ、８６において、b(x)=Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modI、c(x)=Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modI、k(x)=Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modI、k(x)=Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行うこととしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、平文の暗号化時及び暗号文の復号時にセキュリティ装置７０、８０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００８６】
また、本形態の例におけるセキュリティ装置７０では、線形作用演算手段７４において、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果である多項式b(x)を生成し、公開鍵公開手段７５において、多項式b(x)を公開鍵として公開し、暗号文取得手段７６において、セキュリティ装置８０によって演算された第２の演算結果である多項式c(x)と、暗号文（H(k(x))(+)M））とを取得し、線形作用演算手段７７ａにおいて、Σn=0deg c(x)Σm=0r(qmsmn∂nc(x)/n!)modIの演算を行うことにより、第３の演算結果である多項式k(x)を生成し、排他的論理和演算手段７７ｃにおいて、k(x)と、H(k(x))(+)M）と、の排他的論理和を演算することとしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、平文の暗号化時及び暗号文の復号時において、セキュリティ装置７０、８０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００８７】
さらに、本形態の例におけるセキュリティ装置８０では、公開鍵取得手段８４において、セキュリティ装置７０によって公開された第１の演算結果である多項式b(x)を公開鍵として取得し、線形作用演算手段８５ａにおいて、Σn=0deg b(x)Σm=0t(vmumn∂nb(x)/n!)modIの演算を行うことにより、第２の演算結果である多項式k(x)を生成し、排他的論理和演算手段８５ｃにおいて、多項式k(x)と通信内容である平文Mとの排他的論理和を暗号文として演算し（H(k(x))(+)M）、線形作用演算手段８６において、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第３の演算結果である多項式c(x)を生成し、暗号文開示手段８７において、排他的論理和演算手段８５ｃによって演算された暗号文（H(k(x))(+)M）と、線形作用演算手段８６によって生成された多項式c(x)とを開示することとしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、平文の暗号化時及び暗号文の復号時において、セキュリティ装置７０、８０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のDiffile-Hellman鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００８８】
また、本形態の例において、イデアル集合として、整数係数の多項式がなす環のイデアルであって、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、degf(x)をf(x)の次数とした場合における、｛f(x), δf(x),δ2f(x),…,δdegf(x)f(x)｝によって生成される集合であるものを用いることにより、前述した第１の実施の形態の場合と同様、セキュリティ装置７０、８０それぞれで演算した多項式k(x)は同一となり、これらに対して同一のハッシュ関数を作用させた結果であるH(k(x)) も同一となるため、本形態における復号が実質的に可能となる。
【００８９】
さらに、本形態の例では、r個の整数組(s,q)をセキュリティ装置７０側で秘密に保ち、t個の整数組(u,v)をセキュリティ装置８０側で秘密に保つこととしたため、復号のためのパラメータの内容を第三者に知られることなく、セキュリティ装置７０、８０相互間での復号が可能となる。
また、本形態の例では、セキュリティ装置７０の擬似乱数発生手段７３ａによって発生させた乱数を用いてr個の整数組(s,q)を生成し、セキュリティ装置８０の擬似乱数発生手段８３ａによって発生させた乱数を用いてt個の整数組(u,v)を生成することとしたため、r個の整数組(s,q)及びt個の整数組(u,v)の保守性が向上し、結果、暗号に対する安全性が向上する。
【００９０】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、コンピュータ上で所定のプログラムを実行させることにより、本形態におけるセキュリティ装置７０、８０を構成することとしたが、これらの処理内容の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
また、本形態では、線形作用素演算手段７４、７７ａ、８５ａ、８６において、a(x)、b(x)或いはc(x)に対し、線形作用素Σm=0rqm(1-δ)sm或いはΣm=0tvm(1-δ)umを作用させることとしたが、線形作用素を演算するために必要な整数の四則演算の回数が、多項式の次数の対数の多項式のオーダー以下となる線形作用素であれば、他の線形作用素を作用させることとしてもよい。
【００９１】
次に、本発明における第３の実施の形態について説明する。
ここでも、まず、本形態の概略について説明を行い、その後、本形態の詳細について説明を行っていく。
図１２は、本形態におけるセキュリティシステム１００の概略を説明するための図である。
図１２に例示するように、セキュリティシステム１００は、セキュリティ装置１０１、１０２によって構成されており、セキュリティ装置１０１において生成されたデジタル署名を、セキュリティ装置１０２において検証する。
【００９２】
この例の場合、セキュリティ装置１０１は、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定する第１のパラメータ設定手段１０１ａ、第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定する第２のパラメータ設定手段１０１ｂ、及び集合に対し、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とした場合における、Σm=0rqm(1-δ)smを作用させる線形作用演算手段１０１ｃ、１０１ｄを有している。
【００９３】
また、第１の実施の形態と同様、この例の場合、線形作用演算手段１０１ｃは、所定の多項式をa(x)とし、該多項式の次数をdeg a(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う手段となっている。この点、線形作用演算手段１０１ｄについても同様である。
【００９４】
本形態におけるセキュリティシステム１００において、デジタル署名とその検証を行う場合、例えばまず、セキュリティ装置１０１は、セキュリティ装置１０２と共通の整数係数の多項式である共通多項式a(x)、及びセキュリティ装置１０２と共通の多項式であるg(x)を生成し、パラメータ設定手段１０１ａにおいてr個の整数組(s,q)、具体的にはs=(s1,s2,…,sr)及びq=(q1,q2,…,qr)を設定する。
その後、例えば、線形作用演算手段１０１ｃにおいて、共通多項式a(x)に対し、線形作用素Σm=0rqm(1-δ)smを作用させ、具体的には、例えば、線形作用演算手段５１ｂにおいて、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う。この共通多項式a(x)に線形作用素Σm=0rqm(1-δ)smを作用させた結果、すなわち、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算結果b(x)は、例えば、r、s、q（秘密鍵）が、これらの整数パラメータを設定したセキュリティ装置１０１側において秘密に保たれた状態でセキュリティ装置１０２に公開鍵として送信される。
【００９５】
次に、例えば、セキュリティ装置１０１は、パラメータ設定手段１０１ｂにおいてt個の整数組(u,v)、具体的にはu=(u1,u2,…,ut)及びv=(v1,v2,…,vt)を設定し、線形作用演算手段１０１ｄにおいて、共通多項式a(x)に対して線形作用素Σm=0tvm(1-δ)umを作用させる。この例の場合、具体的には、例えば、線形作用演算手段１０１ｄにおいて、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行い、その演算結果c(x)を算出する。さらに、セキュリティ装置１０１は、設定したr個の整数組(s,q)、t個の整数組(u,v)及び多項式c(x)を用い、Σm=0tvmxum+Σm=0rqmxsmH(M,c(x))の演算を行い、その演算結果d(x)を算出する。なお、ここでMは署名が行われるメッセージを意味し、Hはセキュリティ装置１０１、１０２で共通に使用される多項式に値を持つハッシュ関数を意味する。このように生成された多項式c(x)、d(x)は、多項式対（c(x),d(x)）としてセキュリティ装置１０２に送信され、これが署名として機能することになる。なお、この際、r個の整数組(s,q)及びt個の整数組(u,v)はセキュリティ装置１０１側で秘密に保たれ、これらのパラメータr,s,q,u,vは一般には公開されない。
【００９６】
一方、署名としての多項式対(S1,S2)が送信されたセキュリティ装置１０２は、この署名が有効なものであるか否か、すなわち、S1=c(x)かつS2=d(x)を満たすか否かの検証を行う。この検証を行うため、セキュリティ装置１０２は、セキュリティ装置１０２と共通の整数係数の多項式である共通多項式a(x)、及びセキュリティ装置１０２と共通の多項式であるg(x)を生成し、V(x)= S2(1-δ)a(x)-H(M,S1(x))(1-δ)b(x)-S1(x)modIの演算を行う。ここで、この署名が有効なものである場合には、S1=c(x)かつS2=d(x)を満たすことになるため、V(x)=d(x)(1-δ)a(x)-H(M,c(x))(1-δ)b(x)- c(x)=(Σm=0tvmxum+Σm=0rqmxsmH(M,c(x)))(1-δ)a(x)-H(M,c(x))(1-δ)b(x)- c(x)=(Σm=0tvm(1-δ)um+Σm=0rqm(1-δ)smH(M,c(x))(1-δ))a(x)-H(M,c(x))(1-δ)b(x)-c(x)が成立し、さらに、多項式b(x)、c(x)の定義から、V(x)=Σm=0tvm(1-δ)uma(x)+Σm=0rqm(1-δ)smH(M,c(x))(1-δ)a(x)-H(M,c(x))(1-δ)Σm=0rqm(1-δ)sma(x)-Σm=0tvm(1-δ)uma(x)=0が成立する。そのため、このV(x)=0という演算結果より、この署名が有効であることが判断でき、この場合、セキュリティ装置１０２は署名が有効である旨の出力を行う。一方、前述のようにd(x)=Σm=0tvmxum+Σm=0rqmxsmH(M,c(x))を構成するパラメータr,s,q,u,vは、セキュリティ装置１０１側で秘密に保たれているため、セキュリティ装置１０１以外では、これらのパラメータr,s,q,u,vを適切に選択できず、結果、S2=d(x)とはならず、V(x)=0ともならない。よって、このV(x)=0とならないという演算結果より、セキュリティ装置１０２は、検証した署名が無効であることを判断することができ、この場合、セキュリティ装置１０２は署名が無効である旨の出力を行う。
【００９７】
ここで、以上説明した線形作用演算手段１０１ｃ、１０１ｄにおいて行われる多項式演算に必要な四則演算の回数は、上述した演算式が示す通り、秘密パラメータ（r,s,k,t,u,v）の大きさに依存しない。したがって、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時及び署名生成時において、セキュリティ装置１０１によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来の離散対数問題の困難性を応用したデジタル署名方式に比べ、大幅に利便性が向上する。
【００９８】
次に、本形態の詳細について説明を行う。
図１３は、本形態におけるセキュリティシステム１１０の全体構成を例示した図である。
図１３に例示するように、セキュリティシステム１１０は、例えば、デジタル署名を行うセキュリティ装置１２０、デジタル署名の検証を行うセキュリティ装置１３０、及びセキュリティ装置１２０、１３０相互を通信可能なように接続するネットワーク１４０を有しており、このセキュリティ装置１２０、１３０は、ネットワーク１４０を介し、相互に情報のやり取りが可能なように、有線又は無線によって電気的に接続され、或いは接続可能な状態となっている。なお、この全体構成についての詳細は、例えば、第１の実施の形態で説明したものと同様であり、また、セキュリティ装置１２０、１３０のハードウェア構成は、例えば、第１の実施の形態におけるセキュリティ装置２０、３０のハードウェア構成（図３）と同様のものとする。
【００９９】
図１４は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置１２０の処理機能を例示した機能ブロック図である。
図１４に例示するように、この例のセキュリティ装置１２０は、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定し、第３の整数パラメータと第４の整数パラメータとの組によって構成される、第２の個数組のパラメータを設定するパラメータ設定手段１２１、通信相手と共用される整数係数の共通多項式をa(x)とし、共通多項式の次数をdeg a(x)とし、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、∂を微分作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果を生成する線形作用演算手段１２２、線形作用演算手段１２２によって生成された第１の演算結果を公開鍵として公開する公開鍵公開手段１２３、署名を生成する署名生成手段１２４、生成された多項式対を通信相手に送信する多項式対送信手段１２５、セキュリティ装置１３０と共用される整数係数の共通多項式を生成する共通多項式生成手段１２６、各種の情報を記憶する情報記憶手段１２７、及びセキュリティ装置１２０全体を制御する制御手段１２８を処理機能として有している。
【０１００】
なお、この例では、パラメータ設定手段１２１は、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段１２１ａ、及び擬似乱数発生手段１２１ａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段１２１ｂを有しており、線形作用演算手段１２２は、整数演算を行う整数演算手段１２２ａ、多項式の加算演算を行う多項式加算手段１２２ｂ及び多項式の微分演算を行う多項式微分手段１２２ｃを有している。また、署名生成手段１２４は、共通多項式をa(x)とし、共通多項式の次数をdeg a(x)とし、第３の整数パラメータをumとし、第４の整数パラメータをvmとし、第２の個数をtとし、∂を微分作用素とし、イデアル集合をIとした場合における、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第２の演算結果を生成する線形作用演算手段１２４ａ、セキュリティ装置１３０と共通のハッシュ関数Hの演算を行うハッシュ関数演算手段１２４ｂ、及び第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、第３の整数パラメータをumとし、第４の整数パラメータをvmとし、第２の個数をtとし、通信相手と共用されるハッシュ関数をHとし、平文をMとし、第２の演算結果をc(x)とした場合におけるΣm=0tvmxum+Σm=0rqmxsmH(M,c(x))の演算を行い、該演算結果をd(x)とした場合における多項式対（c(x),d(x)）を生成する多項式対生成手段１２４ｃを有している。なお、第３の実施の形態における例では、ハッシュ関数演算手段１２４ｂによって演算されるハッシュ関数Hは、例えば、{0,1}*×Z(x)/I1→Z(x)の演算を行う関数である。さらに、線形作用演算手段１２４ａは、整数演算を行う整数演算手段１２４ａａ、多項式の加算演算を行う多項式加算手段１２４ａｂ及び多項式の微分演算を行う多項式微分手段１２４ａｃを有している。
【０１０１】
また、図１４に例示するように、パラメータ設定手段１２１、線形作用演算手段１２２、公開鍵公開手段１２３、署名生成手段１２４、多項式対送信手段１２５、共通多項式生成手段１２６、情報記憶手段１２７は、制御手段１２８への情報の提供及び制御手段１２８からの情報の取得の少なくとも一方が可能なように構成されており、公開鍵公開手段１２３及び多項式対送信手段１２５は、ネットワーク１４０への情報の提供が可能なように構成されている。
図１５は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置１３０の処理機能を例示した機能ブロック図である。
【０１０２】
図１５に例示するように、この例のセキュリティ装置１３０は、通信相手によって公開された公開鍵を受信する公開鍵取得手段１３１、第１の多項式と第２の多項式から構成される多項式対を受信する多項式対取得手段１３２、通信相手と共用される整数係数の共通多項式をa(x)とし、公開鍵をb(x)とし、第１の多項式をS1とし、前期第２の多項式をS2とし、通信相手と共用される多項式に値を持つハッシュ関数をHとし、平文をMとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とし、イデアルであって、該イデアルに対して行われた、整数係数の多項式の変数を任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合であるイデアル集合をIとした場合における、S2(1-δ)a(x)-H(M,S1(x))(1-δ)b(x)-S1(x)modIの演算を行い、該演算結果が０となった場合には、署名が有効である旨の出力を行い、該演算結果が０とならなかった場合には、署名は無効である旨の出力を行う署名検証手段１３３、セキュリティ装置１２０と共用される共通多項式を生成する共通多項式生成手段１３４、各種の情報を記憶する記憶手段１３５、及びセキュリティ装置１３０全体を制御する制御手段１３６を処理機能として有している。なお、この例では、署名検証手段１３３は、整数演算を行う整数演算手段１３３ａ、多項式の加算演算を行う多項式加算手段１３３ｂ及び多項式の微分演算を行う多項式微分手段１３３ｃ、セキュリティ装置１２０と共通のハッシュ関数Hの演算を行うハッシュ関数演算手段１３３ｄ、及び多項式の比較を行う多項式比較手段１３３ｅを有している。
【０１０３】
また、図１５に例示するように、公開鍵取得手段１３１、多項式対取得手段１３２、署名検証手段１３３、共通多項式生成手段１３４、及び記憶手段１３５は、制御手段１３６への情報の提供及び制御手段１３６からの情報の取得の少なくとも一方が可能なように構成されており、公開鍵取得手段１３１及び多項式対取得手段１３２は、ネットワーク１４０からの情報の取得が可能なように構成されている。
次に、本形態におけるセキュリティシステム１１０、セキュリティ装置１２０、１３０の処理動作について説明する。
【０１０４】
図１６は、本形態におけるセキュリティシステム１１０、セキュリティ装置１２０、１３０の処理動作の一例を説明するためのフローチャートである。このフローチャートにおける実線の矢印は、セキュリティシステム１１０全体における一連の処理の流れを例示したものであり、破線の矢印は、セキュリティシステム１１０全体における一連の処理の流れと、セキュリティ装置１２０、１３０それぞれ単体での処理の流れが異なる部分について、セキュリティ装置１２０、１３０単体での処理の流れを例示したものである。なお、ここでは、説明を容易にするため、便宜的に図１６のような処理の流れにそって処理動作の説明を行うが、セキュリティ装置１２０、１３０それぞれが、このフローチャートの流れと異なる順序で処理を行うこととしてもよく、また、セキュリティ装置１２０、１３０が、平行して、同時にそれぞれの処理を行うこととしてもよい。
【０１０５】
以下、このフローチャートに沿って説明を行う。
ステップＳ４０：
本ステップでは、セキュリティ装置１２０において、整数係数の共通多項式a(x)、g(x)の設定を行う。
この共通多項式a(x)、g(x)の設定は、例えば、セキュリティ装置１２０の共通多項式生成手段１２６において行われる。ここでの共通多項式a(x)、g(x)の設定は、設定された共通多項式a(x)、g(x)が、セキュリティ装置１３０で設定される共通多項式と同一となるように行われる。具体的には、例えば、セキュリティ装置１２０、１３０が共通して保有しているハッシュ関数を用いて所定のハッシュ操作を行うことにより、セキュリティ装置１２０、１３０で共有される共通多項式a(x)、g(x)の生成を行う。
このように設定された共通多項式a(x)、g(x)を特定するための情報は、例えば、制御手段１２８に送られ、制御手段１２８は、送られた共通多項式a(x)、g(x)を特定するための情報を記憶手段１２７に送る。記憶手段１２７に送られた共通多項式a(x) 、g(x)を特定するための情報は、例えば、記憶手段１２７に記録される。
【０１０６】
ステップＳ４１：
本ステップでは、セキュリティ装置１３０において、整数係数の共通多項式a(x)、g(x)の設定を行う。
この共通多項式a(x)、g(x)の設定は、例えば、セキュリティ装置１３０の共通多項式生成手段１３４において行われる。ここでの共通多項式a(x)、g(x)の設定は、設定された共通多項式a(x)、g(x)が、セキュリティ装置１２０で設定される共通多項式と同一となるように行われる。具体的には、例えば、セキュリティ装置１２０、１３０が共通して保有しているハッシュ関数を用いて所定のハッシュ操作を行うことにより、セキュリティ装置１２０、１３０で共有される共通多項式a(x)、g(x)の生成を行う。
このように設定された共通多項式a(x)、g(x)を特定するための情報は、例えば、制御手段１３６に送られ、制御手段１３６は、送られた共通多項式a(x)、g(x)を特定するための情報を記憶手段１３５に送る。記憶手段１３５に送られた共通多項式a(x) 、g(x)を特定するための情報は、例えば、記憶手段１３５に記録される。
【０１０７】
ステップＳ４２：
本ステップでは、セキュリティ装置1２０において、r個の整数組(s,q)の設定を行う。
r個の整数組(s,q)の設定は、例えば、セキュリティ装置１２０のパラメータ設定手段１２１によって行われる。具体的には、例えば、まず、擬似乱数発生手段１２１ａにおいて、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、整数値演算手段１２１ｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定のr個の整数組(s,q)、すなわち、s=(s1,s2,…,sr)とq=(q1,q2,…,qr)とを設定する。
設定されたr個の整数組(s,q)を特定するための情報は、例えば、制御手段１２８に送られ、制御手段１２８は、送られたr個の整数組(s,q)を特定するための情報を、線形作用演算手段１２２及び記憶手段１２７に送る。記憶手段１２７に送られたr個の整数組(s,q)を特定するための情報は、例えば、記憶手段１２７に記憶され、線形作用演算手段１２２に送られたr個の整数組(s,q)を特定するための情報は、ステップＳ４３の処理に使用される。
【０１０８】
ステップＳ４３：
本ステップでは、セキュリティ装置１２０において、多項式の演算を行う。
本ステップにおける多項式の演算は、例えば、セキュリティ装置１２０の線形作用演算手段１２２において行われる。この多項式の演算を行う場合、例えば、まず、制御手段１２８は、ステップＳ４０において記憶手段１２７に記憶された共通多項式a(x)、g(x)を特定するための情報を読み込み、その情報を線形作用演算手段１２２に送る。この情報が送られた線形作用演算手段１２２は、これらの情報とステップＳ４２の処理で送られた情報とを用いた演算により、共通多項式a(x)にΣm=0rqm(1-δ)smを作用させる処理を行う（なお、前述のように、δは任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素である。）。この例の場合、この共通多項式a(x)にΣm=0rqm(1-δ)smを作用させる具体的な演算方法として、線形作用演算手段１２２が有する整数演算手段１２２ａ、多項式加算手段１２２ｂ及び多項式微分手段１２２ｃを用い、b(x)=Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行う。このような演算の結果を示す多項式b(x)を特定するための情報は、例えば、制御手段１２８に送られ、制御手段１２８は、送られた多項式b(x)を特定するための情報を、公開鍵公開手段１２３に送る。公開鍵公開手段１２３にこの情報が送られると、次に、ステップＳ４４の処理に移る。
【０１０９】
ステップＳ４４：
本ステップでは、セキュリティ装置１２０において、演算結果である多項式b(x)を公開鍵として公開する。
多項式b(x)の公開は、例えば、セキュリティ装置１２０の公開鍵公開手段１２３によって行われるが、この際、r個の整数組(s,q)は開示されず、このr個の整数組(s,q)をセキュリティ装置１２０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置１２０からセキュリティ装置１３０宛の電子メールに、この多項式b(x)を特定するための情報を、r個の整数組(s,q)を特定するための情報を開示することなく提示し、或いは、セキュリティ装置１３０が閲覧可能なインターネット上のホームページに、この多項式b(x)を特定するための情報を、r個の整数組(s,q)を特定するための情報を開示することなくアップロードすることによって行われる。
このように多項式b(x)の公開が行われると、次に、ステップＳ４５の処理に移る。
【０１１０】
ステップＳ４５：
本ステップでは、セキュリティ装置１３０において、多項式b(x)を受信する。多項式b(x)の受信は、例えば、セキュリティ装置１３０の公開鍵取得手段１３１において行われる。具体的には、例えば、セキュリティ装置１３０が、インターネット上のメールサーバにアクセスし、セキュリティ装置１２０から送られたセキュリティ装置１３０宛の電子メールを受け取ることにより、または、多項式b(x)を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多項式b(x)を特定するための情報は、例えば、制御手段１３６に送られ、制御手段１３６は、送られた多項式b(x)を特定するための情報を記憶手段１３５に送る。記憶手段１３５に送られた多項式b(x)を特定するための情報は、例えば、記憶手段１３５に記憶される。
【０１１１】
ステップＳ４６：
本ステップでは、セキュリティ装置１２０において、t個の整数組(u,v)の設定を行う。
t個の整数組(u,v)の設定は、例えば、セキュリティ装置１２０のパラメータ設定手段１２１により、ステップＳ４２と同様な方法により行われ、これにより、所定のt個の整数組(u,v)、すなわち、u=(u1,u2,…,ut)とv=(v1,v2,…,vt)とを設定する。
設定されたt個の整数組(u,v)を特定するための情報は、例えば、制御手段１２８に送られ、制御手段１２８は、送られたt個の整数組(u,v)を特定するための情報を署名生成手段１２４及び記憶手段１２７に送る。記憶手段１２７に送られたt個の整数組(u,v)を特定するための情報は、例えば、記憶手段１２７に記憶され、署名生成手段１２４に送られたt個の整数組(u,v)を特定するための情報は、ステップＳ４７の処理に使用される。
【０１１２】
ステップＳ４７：
本ステップでは、セキュリティ装置１２０において、多項式の演算を行う。
本ステップにおける多項式の演算は、例えば、署名生成手段１２４の線形作用演算手段１２４ａにおいて行われる。この多項式の演算を行う場合、例えば、まず、制御手段１２８は、ステップＳ４０において記憶手段１２７に記憶された共通多項式a(x)、g(x)を特定するための情報を読み込み、その情報を署名生成手段１２４の線形作用演算手段１２４ａに送る。この情報が送られた線形作用演算手段１２４ａは、この情報とステップＳ４６の処理で送られた情報とを用いた演算により、共通多項式a(x)にΣm=0tvm(1-δ)umを作用させる処理を行う。この例の場合、この共通多項式a(x)にΣm=0rvm(1-δ)umを作用させる具体的な演算方法として、線形作用演算手段１２４ａが有する整数演算手段１２４ａａ、多項式加算手段１２４ａｂ及び多項式微分手段１２４ａｃを用い、c(x)=Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行う。
このような演算の結果を示す多項式c(x)を特定するための情報は、例えば、制御手段１２８に送られ、制御手段１２８は、送られた多項式c(x)を特定するための情報を、記憶手段１２７に記憶する。記憶手段１２７へのこの情報の記憶が行われると、次に、ステップＳ４８の処理に移る。
【０１１３】
ステップＳ４８：
本ステップでは、セキュリティ装置１２０において、多項式対の生成を行う。本ステップにおける多項式対の生成は、例えば、署名生成手段１２４のハッシュ関数演算手段１２４ｂ及び多項式対生成手段１２４ｃににおいて行われる。この多項式対の生成を行う場合、例えば、まず、制御手段１２８において記憶手段１２７から多項式c(x)を特定するための情報を抽出し、この抽出した情報を署名生成手段１２４に送る。署名生成手段１２４に多項式c(x)を特定するための情報が送られると、例えば次に、ハッシュ関数演算手段１２４ｂにおいて、署名を行うメッセージM及び多項式c(x)に対し多項式に値を持つハッシュ関数Hを作用させる（H(M,c(x))。その後、例えば、ステップＳ４２及びＳ４６の処理において記憶手段１２７に記憶されているr個の整数組(s,q)及びt個の整数組(u,v)を、制御手段１２８によって抽出し、それらを署名生成手段１２４の多項式対生成手段に送る。これらの情報が送られた多項式対生成手段１２４ｃは、これらの情報と、ハッシュ関数演算手段１２４ｂの演算結果（H(M,c(x))とを用い、Σm=0tvmxum+Σm=0rqmxsmH(M,c(x))の演算を行い、その演算結果d(x)を算出する。
以上のように生成された多項式c(x)、d(x)は、多項式対(c(x),d(x))として制御手段１２８に送られ、制御手段１２８は送られた多項式対(c(x),d(x))を多項式対送信手段１２５に送る。多項式対(c(x),d(x))が多項式対送信手段１２５に送られると、次に、ステップＳ４９の処理に移る。
【０１１４】
ステップＳ４９：
本ステップでは、セキュリティ装置１２０において、多項式対(c(x),d(x))を送信する。
本ステップにおける多項式対(c(x),d(x))の送信は、例えば、多項式対送信手段１２５において行われるが、この際、r個の整数組(s,q)及びt個の整数組(u,v)はセキュリティ装置１０１側で秘密に保たれ、これらのパラメータr,s,q,u,vは開示されない。具体的には、例えば、セキュリティ装置１２０からセキュリティ装置１３０宛の電子メールに、この多項式対(c(x),d(x))を特定するための情報を、パラメータr,s,q,u,vを特定するための情報を開示することなく提示し、或いは、セキュリティ装置１３０が閲覧可能なインターネット上のホームページに、この多項式対(c(x),d(x))を特定するための情報を、パラメータr,s,q,u,vを特定するための情報を開示することなくアップロードすることによって行われる。このように多項式対(c(x),d(x))の送信が行われると、次に、ステップＳ５０の処理に移る。
【０１１５】
ステップＳ５０：
本ステップでは、セキュリティ装置１３０において多項式対(c(x),d(x))の受信を行う。
多項式対(c(x),d(x))の受信は、例えば、セキュリティ装置１３０の多項式対取得手段１３２において行われる。具体的には、例えば、セキュリティ装置１３０が、インターネット上のメールサーバにアクセスし、セキュリティ装置１２０から送られたセキュリティ装置１３０宛の電子メールを受け取ることにより、または、多項式対(c(x),d(x))を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
多項式対取得手段１３２において受信された多項式対(c(x),d(x))は、例えば、署名検証手段１３３に送られ、次のステップＳ５１の処理に使用される。
【０１１６】
ステップＳ５１：
本ステップでは、セキュリティ装置１３０において署名の検証を行う。
本ステップにおける署名の検証は、例えば、署名検証装置１３３において行われる。例えば、署名として多項式対(S1,S2)がセキュリティ装置１３０に送信された場合、まず、制御手段１３６は、ステップＳ４１及びＳ４５の処理によって記憶手段１３５に記憶されている共通多項式a(x)、g(x)及び多項式b(x)を抽出し、抽出したこれらの情報を署名検証手段１３３に送る。これらの情報が送られた署名検証手段１３３は、例えば次に、整数演算手段１３３ａ、多項式加算手段１３３ｂ、多項式微分手段及びハッシュ関数演算手段１３３ｄを用い、V(x)= S2(1-δ)a(x)-H(M,S1(x))(1-δ)b(x)-S1(x)modIの演算を行い、その演算結果を多項式比較手段１３３ｅに送る。この演算結果が送られた多項式比較手段１３３ｅは、前述のように、その演算結果がV(x)=0である場合、その署名が有効であると判断して、その署名が有効である旨の出力を行い、演算結果がV(x)=0でない場合、その署名が無効であると判断して、その署名が無効である旨の出力を行う。
【０１１７】
このように本形態の例では、パラメータ設定手段１２１において、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータ（r個の整数組(s,q)、t個の整数組(u,v)）を設定し、線形作用演算手段１２２、１２４ａにおいて、集合（a(x)）に対し、Σm=0rqm(1-δ)sm或いはΣm=0tvm(1-δ)um作用させることとしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、署名生成時において、セキュリティ装置１２０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来の離散対数問題の困難性を応用したデジタル署名方式に比べ、大幅に利便性が向上する。
【０１１８】
また、本形態の例では、多くの秘密パラメータ（r,s,k,t,u,v）を有する線形作用素を作用させることにより、公開鍵の生成、署名の生成を行うこととしたため、第三者による署名に対する安全性が十分確保できる。
さらに、本形態の例では、線形作用演算手段１２２、１２４ａにおいて、b(x)=Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modI、c(x)=Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うこととしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、署名生成時において、セキュリティ装置１２０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来の離散対数問題の困難性を応用したデジタル署名方式に比べ、大幅に利便性が向上する。
【０１１９】
また、本形態の例におけるセキュリティ装置１２０では、線形作用演算手段１２２において、Σn=0deg a(x)Σm=0r(qmsmn∂na(x)/n!)modIの演算を行うことにより、第１の演算結果b(x)を生成し、公開鍵公開手段１２３において、線形作用演算手段１２２によって生成された演算結果b(x)を公開鍵として公開し、線形作用演算手段１２４ａにおいて、Σn=0deg a(x)Σm=0t(vmumn∂na(x)/n!)modIの演算を行うことにより、第２の演算結果c(x)を生成し、多項式対生成手段１２４ｃにおいて、Σm=0tvmxum+Σm=0rqmxsmH(M,c(x))の演算を行い、多項式対（c(x),d(x)）を生成し、多項式対送信手段１２５において、生成された多項式対をセキュリティ装置１３０に送信することとしたため、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、署名生成時において、セキュリティ装置１２０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来の離散対数問題の困難性を応用したデジタル署名方式に比べ、大幅に利便性が向上する。
【０１２０】
さらに、本形態におけるセキュリティ装置１３０では、公開鍵取得手段１３１において、セキュリティ装置１２０によって公開された公開鍵である多項式b(x)を受信し、多項式対取得手段１３２において、第１の多項式と第２の多項式から構成される多項式対(S1,S2)を受信し、署名検証手段１３３において、S2(1-δ)a(x)-H(M,S1(x))(1-δ)b(x)-S1(x)modIの演算を行い、該演算結果が０となった場合には、署名が有効である旨の出力を行い、該演算結果が０とならなかった場合には、署名は無効である旨の出力を行うこととしたため、セキュリティ装置１２０において、秘密パラメータ（r,s,k,t,u,v）の大きさを大きくした場合であっても、公開鍵生成時、署名生成時において、セキュリティ装置１２０によって行われる四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来の離散対数問題の困難性を応用したデジタル署名方式に比べ、大幅に利便性が向上する。
【０１２１】
また、本形態の例では、r個の整数組(s,q)及びt個の整数組(u,v)をセキュリティ装置１２０側で秘密に保つこととしたため、署名の安全性が確保される。
さらに、本形態の例では、セキュリティ装置１２０の擬似乱数発生手段１２１ａによって発生させた乱数を用いてr個の整数組(s,q)及びt個の整数組(u,v)を生成することとしたため、r個の整数組(s,q)及びt個の整数組(u,v)の保守性が向上し、結果、署名に対する安全性が向上する。
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、コンピュータ上で所定のプログラムを実行させることにより、本形態におけるセキュリティ装置１２０、１３０を構成することとしたが、これらの処理内容の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
【０１２２】
また、本形態では、線形作用素演算手段１２２、１２４ａにおいて、a(x)、b(x)或いはc(x)に対し、線形作用素Σm=0rqm(1-δ)sm或いはΣm=0tvm(1-δ)umを作用させることとしたが、線形作用素を演算するために必要な整数の四則演算の回数が、多項式の次数の対数の多項式のオーダー以下となる線形作用素であれば、他の線形作用素を作用させることとしてもよい。
さらに、上述のように、第１の実施の形態、第２の実施の形態及び第３の実施の形態における処理機能は、コンピュータによって実現することができる。この場合、セキュリティ装置１、２、２０、３０、５１、５２、７０、８０、１０１、１０２、１２０、１３０が有すべき機能の処理内容はプログラム（セキュリティプログラム）によって記述され、このプログラムをコンピュータで実行することにより、上記処理機能をコンピュータ上で実現することができる。
【０１２３】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を用いることができる。
【０１２４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１２５】
【発明の効果】
以上説明したように本発明では、第１の整数パラメータと第２の整数パラメータとの組によって構成される、第１の個数組のパラメータを設定し、集合に対し、第１の整数パラメータをsmとし、第２の整数パラメータをqmとし、第１の個数をrとし、δを任意の多項式g(x)に対して多項式g(x)-g(x-1)を対応させる作用素とした場合における、Σm=0rqm(1-δ)smを作用させることとしたため、秘密パラメータ値を大きくした場合であっても、例えば、鍵配送時、暗号・復号時、署名生成・検証時における計算量が増大することはなく、従来の離散対数問題の困難性を応用したデジタル署名方式に比べ、大幅に利便性が向上する。
【図面の簡単な説明】
【図１】セキュリティシステムの概略を説明するための図。
【図２】セキュリティシステムの全体構成を例示した図。
【図３】セキュリティ装置のハードウェア構成を例示したブロック図。
【図４】セキュリティ装置の処理機能を例示した機能ブロック図。
【図５】セキュリティ装置の処理機能を例示した機能ブロック図。
【図６】セキュリティシステム、セキュリティ装置の処理動作の一例を説明するためのフローチャート。
【図７】セキュリティシステムの概略を説明するための図。
【図８】セキュリティシステムの全体構成を例示した図。
【図９】セキュリティ装置の処理機能を例示した機能ブロック図。
【図１０】セキュリティ装置の処理機能を例示した機能ブロック図。
【図１１】セキュリティシステム、セキュリティ装置の処理動作の一例を説明するためのフローチャート。
【図１２】セキュリティシステムの概略を説明するための図。
【図１３】セキュリティシステムの全体構成を例示した図。
【図１４】セキュリティ装置の処理機能を例示した機能ブロック図。
【図１５】セキュリティ装置の処理機能を例示した機能ブロック図。
【図１６】セキュリティシステム、セキュリティ装置の処理動作の一例を説明するためのフローチャート。
【符号の説明】
１、１０、５０、６０、１００、１１０  セキュリティシステム
２、３、２０、３０、５１、５２、７０、８０、１０１、１０２、１２０、１３０  セキュリティ装置
【図１】
0003883942.tif 000002
【図２】
0003883942.tif 000003
【図３】
0003883942.tif 000004
【図４】
0003883942.tif 000005
【図５】
0003883942.tif 000006
【図６】
0003883942.tif 000007
【図７】
0003883942.tif 000008
【図８】
0003883942.tif 000009
【図９】
0003883942.tif 000010
【図１０】
0003883942.tif 000011
【図１１】
0003883942.tif 000012
【図１２】
0003883942.tif 000013
【図１３】
0003883942.tif 000014
【図１４】
0003883942.tif 000015
【図１５】
0003883942.tif 000016
【図１６】
0003883942.tif 000017