(57)【要約】【課題】  任意の２つの暗号文を加算、乗算した値が、それら暗号文に対応する平文を加算、乗算した値の暗号文となり、かつ安全で実用的な暗号アルゴリズムを提供する。【解決手段】  合成数Nと互いに素な０以上N未満の整数を秘密鍵ｒとし、自然数のパラメータｄを決定する。そして、平分ｍに対し、m=Σi=0d ai mod Nを満たすａｉ（ｉ＝０,…,ｄ）を選択し、C=fm,r(X)=Σi=1d airiXi mod ZN[X]に従って暗号文Ｃを算出する。  その後、この暗号文Ｃにｒ-1を代入して（fm,r(r-1)）復号を行う。【選択図】        図４
2005084568.tif 000002
【特許請求の範囲】
【請求項１】
暗号処理を行うセキュリティ方法であって、
第１のセキュリティ装置において、
合成数Nを抽出し、
Nと互いに素な０以上N未満の整数である第１の秘密鍵ｒを抽出し、
暗号化対象ｍを特定し、
自然数の第１のパラメータｄを決定し、
【数１】
2005084568.tif 000037
を満たす加算項ａｉ（ｉ＝０,…,ｄ）を選択し、
第１の暗号文Ｃを、
【数２】
2005084568.tif 000038
に従って算出する、
ことを特徴とするセキュリティ方法。
【請求項２】
請求項１記載のセキュリティ方法であって、
第２のセキュリティ装置において、
上記第１の暗号文Ｃ＝ｆｍ,ｒ(Ｘ)の入力を受け付け、
上記第１の秘密鍵ｒを抽出し、
上記第１の暗号文Ｃの復号結果fm,r(r-1) mod Nを算出する、
ことを特徴とするセキュリティ方法。
【請求項３】
請求項１記載のセキュリティ方法であって、
第２のセキュリティ装置において、
上記第１の暗号文Ｃ＝ｆｍ,ｒ(Ｘ)の入力を受け付け、
上記第１の暗号文Ｃを任意な多項式関数である代理演算関数に代入し、
その代入結果Ｇ(Ｘ)を上記第１のセキュリティ装置に対して出力し、
上記第１のセキュリティ装置において、
上記代入結果Ｇ(Ｘ)の入力を受け付け、
上記第１の秘密鍵ｒを抽出し、
上記代入結果Ｇ(Ｘ)の復号結果G(r-1)を算出する、
ことを特徴とするセキュリティ方法。
【請求項４】
請求項１記載のセキュリティ方法であって、
第２のセキュリティ装置において、
上記第１の暗号文Ｃ＝ｆｍ,ｒ(Ｘ)の入力を受け付け、
上記合成数Nを抽出し、
Nと互いに素な０以上N未満の整数である第２の秘密鍵ｔを抽出し、
自然数の第２のパラメータｄ’を決定し、
【数３】
2005084568.tif 000039
を満たす加算項ｂｉ(Ｘ)（ｉ＝０,…,ｄ’）を選択し、
第２の暗号文Ｃ’を、
【数４】
2005084568.tif 000040
に従って算出し、
上記第２の暗号文Ｃ’を上記第１のセキュリティ装置に対して出力し、
上記第１のセキュリティ装置において、
上記第２の暗号文Ｃ’の入力を受け付け、
上記秘密鍵ｒを抽出し、
上記第２の暗号文Ｃ’の復号結果fC,t(r-1,Y)を算出する、
ことを特徴とするセキュリティ方法。
【請求項５】
復号処理を行うセキュリティ方法であって、
第１のセキュリティ装置において、
合成数Nを抽出し、
Nと互いに素な０以上N未満の整数である第１の秘密鍵ｒを抽出し、
自然数のパラメータｄを決定し、
第１の暗号文Ｆ(Ｙ)を抽出し、
【数５】
2005084568.tif 000041
を満たす加算項ｂｉ(Ｙ)（ｉ＝０,…,ｄ）を選択し、
第２の暗号文Ｃを、
【数６】
2005084568.tif 000042
に従って算出し、
上記第２の暗号文Ｃを第２のセキュリティ装置に対して出力し、
上記第２のセキュリティ装置において、
上記第２の暗号文Ｃの入力を受け付け、
Nと互いに素な０以上N未満の整数である第２の秘密鍵ｔを抽出し、
第１の復号結果F’(Z)=fF(Y),r(t-1,Z)を算出し、
上記第１の復号結果F’(Z)を上記第１のセキュリティ装置に対して出力し、
上記第１のセキュリティ装置において、
上記第１の復号結果F’(Z)の入力を受け付け、
上記第１の秘密鍵ｒを抽出し、
第２の復号結果F’(r-1)を算出する、
ことを特徴とするセキュリティ方法。
【請求項６】
請求項４記載のセキュリティ方法であって、
上記第２のセキュリティ装置は複数であり、
上記第２の秘密鍵、上記第２のパラメータ、及び上記加算項は、上記第２のセキュリティ装置ごとに独立して設定され、
上記復号結果を、上記第１のセキュリティ装置の暗号化対象とし、
その暗号文の出力先となる上記第２のセキュリティ装置を変更しつつ、請求項４記載の処理を繰り返す、
ことを特徴とするセキュリティ方法。
【請求項７】
請求項５記載のセキュリティ方法であって、
上記第２のセキュリティ装置は複数であり、
上記第２の復号結果を、上記第１のセキュリティ装置の暗号化対象とし、
その暗号文の出力先となる上記第２のセキュリティ装置を変更しつつ、請求項５記載の処理を繰り返す、
ことを特徴とするセキュリティ方法。
【請求項８】
請求項１記載のセキュリティ方法であって、
複数の第２のセキュリティ装置において、
それぞれの提供値を上記第１のセキュリティ装置に対して出力し、
上記第１のセキュリティ装置において、
上記提供値の入力を受け付け、
入力された上記提供値を上記暗号化対象ｍとして特定し、
それぞれの上記暗号化対象ｍに対応する複数の上記暗号文Ｃを算出し、
算出した全ての上記暗号文Ｃを上記第２のセキュリティ装置に対して出力し、
上記第２のセキュリティ装置において、
全ての上記暗号文Ｃの入力を受け付け、
上記暗号文Ｃを、上記提供値の調和平均を算出するための関数に代入し、
その代入値を第３のセキュリティ装置に対して出力し、
上記第３のセキュリティ装置において、
上記代入値の入力を受け付け、
上記秘密鍵ｒを抽出し、
上記代入値にｒ−１を代入して調和平均を特定する値を算出し、
上記調和平均を特定する値を上記第２のセキュリティ装置に対して出力し、
上記第２のセキュリティ装置において、
上記調和平均を特定する値の入力を受け付け、
この調和平均を特定する値を用いて調和平均を算出する、
ことを特徴とするセキュリティ方法。
【請求項９】
請求項１記載のセキュリティ方法であって、
上記第１のセキュリティ装置において、
論理ゲートを特定する情報の入力を受け付け、
この論理ゲートを多項式表現した場合の各係数を上記暗号化対象ｍとして特定し、
これら各係数の上記暗号文Ｃを算出し、
各暗号文Ｃを係数とした多項式関数を生成し、
生成した上記多項式関数を第２のセキュリティ装置に対して出力し、
上記第２のセキュリティ装置において、
上記多項式関数の入力を受け付け、
上記多項式関数の演算を行い、
この演算結果を第３のセキュリティ装置に対して出力し、
上記第３のセキュリティ装置において、
この演算結果の入力を受け付け、
入力された演算結果にｒ−１を代入する、
ことを特徴とするセキュリティ方法。
【請求項１０】
請求項２記載のセキュリティ方法であって、
上記第１のセキュリティ装置或いは上記第２のセキュリティ装置の何れか一方において、
合成数Ｎ,Ｎ２を抽出し、
０以上Ｎ２未満であって位数がＮとなるｇ0を決定し、
上記自然数のパラメータｄを抽出し、
上記秘密鍵ｒを抽出し、
i=1,…,dについて、
【数７】
2005084568.tif 000043
に従って公開値giを算出し、
公開値gi(i=1,…,d)を検証装置に対して出力し、
上記秘密鍵ｒを知っていることのゼロ知識証明情報を出力し、
上記第１のセキュリティ装置において、
算出した上記暗号文Ｃを上記検証装置に対して出力し、
上記第２のセキュリティ装置において、
算出した上記暗号化対象mを上記検証装置に対して出力し、
上記検証装置において、
上記公開値gi(i=1,…,d)、上記暗号文Ｃ及び上記暗号化対象mの入力を受け付け、
上記暗号文Ｃの各係数をc0,…,cdとした場合における、
【数８】
2005084568.tif 000044
が成立しているか否かを判断し、成立していれば処理が正当であると判断する、
ことを特徴とするセキュリティ方法。
【請求項１１】
請求項１から１０の何れかに記載のセキュリティ方法であって、
上記自然数のパラメータは、
安全でない暗号通信を行うと予想される回数よりも大きな値である、
ことを特徴とするセキュリティ方法。
【請求項１２】
請求項１から１１の何れかに記載のセキュリティ方法であって、
上記自然数のパラメータは、
安全でない暗号通信を行った回数に自然数を加算した値である、
ことを特徴とするセキュリティ方法。
【請求項１３】
請求項１から１２の何れかに記載のセキュリティ方法であって、
上記合成数Ｎは、
上記セキュリティ装置以外の外部機関装置において生成される、
ことを特徴とするセキュリティ方法。
【請求項１４】
請求項１から１３の何れかに記載のセキュリティ方法であって、
上記合成数Ｎは、
複数の装置でそれぞれ生成された合成数の積である、
ことを特徴とするセキュリティ方法。
【請求項１５】
暗号化処理を行うセキュリティ装置であって、
合成数Nを抽出する合成数抽出手段と、
Nと互いに素な０以上N未満の整数である秘密鍵ｒを抽出する秘密鍵抽出手段と、
暗号化対象ｍを特定する暗号化対象特定手段と、
自然数のパラメータｄを決定するパラメータ決定手段と、
【数９】
2005084568.tif 000045
を満たす加算項ａｉ（ｉ＝０,…,ｄ）を選択する加算項選択手段と、
暗号文Ｃを、
【数１０】
2005084568.tif 000046
に従って算出する暗号化手段と、
を有することを特徴とするセキュリティ装置。
【請求項１６】
復号処理を行うセキュリティ装置であって、
暗号文の入力を受け付ける暗号文入力手段と、
秘密鍵ｒを抽出する秘密鍵抽出手段と、
上記暗号文にｒ-1を代入する復号手段と、
を有することを特徴とするセキュリティ装置。
【請求項１７】
コンピュータに、請求項１から１４の何れかに記載されたセキュリティ方法の手順を実行させるためのセキュリティプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術の基盤となる暗号アルゴリズム、及びそれを用いた暗号応用プロトコルに関する。
【背景技術】
【０００２】
現在、ＲＳＡ暗号（例えば、非特許文献１参照。）、Paillier暗号（例えば、非特許文献２参照。）、Domingo-Ferrer暗号（例えば、非特許文献３参照。）等のさまざまな暗号アルゴリズムが提唱されている。
ここでＲＳＡ暗号は、E(a)E(b)=E(ab)が成り立つ公開鍵暗号である。また、Paillier暗号は、E(a)E(b)=E(a+b)が成り立つ公開鍵暗号である。一方、Domingo-Ferrer暗号は、E(a)+E(b)=E(a+b)かつE(a)E(b)=E(ab)が成り立つ共通鍵暗号である。なおａ，ｂは任意の平文、Ｅは暗号関数である。即ちE(a),E(b)は、それぞれａ，ｂの暗号文を意味するものとする。
【非特許文献１】R. L. Rivest, A. Shamir, and L. Adleman, ”A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol. 21, No. 2, pp. 120--126, Feb. 1978.
【非特許文献２】P. Paillier, ‘’Public-key cryptosystems based on composite degree residuosity classes,” J. Stern (Ed.), EUROCRYPT '99, LNCS 1592, Springer-Verlag, pp. 223--238, 1999.
【非特許文献３】J. Domingo-Ferrer, “A provably secure additive and multiplicative privacy homomorphism,” A. H. Chan and V. Gligor (Eds.), 5th Information Security Conference 2002 (ISC2002), LNCS 2433, Springer-Verlag, pp. 471--483, 2002.
【非特許文献４】D. Wagner, “Cryptanalysis of an algebraic privacy homomorphism,” In Proc. of 6th Information Security Conference (ISC '03), Oct. 2003. (Available at http://www.cs.berkeley.edu/~daw/papers/)
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、従来、ａ，ｂを知る事無く、E(a),E(b)からE(a+b)とE(ab)を実用的な時間内に求めることができ、なおかつ安全性が高い暗号アルゴリズムは存在していなかった。
例えば、ＲＳＡ暗号に関し、E(a),E(b)からa,bを知る事無くE(a+b)を求める方法は知られていない。またPaillier暗号については、E(a),E(b)からａ，ｂを知る事無くE(ab)を求める方法は知られていない。ＲＳＡ或いはPaillier 暗号同様の性質を持つ公開鍵暗号方式は他にも幾つか知られているが、それらについてもやはりE(a),E(b)からａ，ｂを知る事無くE(a+b)とE(ab)の両方を求める方法は知られていない。
【０００４】
一方、共通鍵暗号であるDomingo-Ferrer 暗号は、E(a)+E(b)=E(a+b)かつE(a)E(b)=E(ab)が成り立つが、Wagnerによって、安全性に関する問題点が指摘される（例えば、非特許文献４参照。）等、安全性の面で十分でない。
本発明は、このような点に鑑みてなされたものであり、ａ，ｂを知る事無く、E(a),E(b)からE(a+b)とE(ab)を実用的な時間内に求めることができ、なおかつ安全性が高い暗号アルゴリズムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
この発明では上記課題を解決するために、第１のセキュリティ装置において、合成数Nを抽出し、Nと互いに素な０以上N未満の整数である秘密鍵ｒを抽出し、暗号化対象ｍを特定する。そして、自然数のパラメータｄを決定し、
【数１１】
2005084568.tif 000003
に従って算出する。
その後、暗号文Ｃを、
【数１２】
2005084568.tif 000004
に従って算出する。なお、ＺＮ［Ｘ］は、Ｎを法とした剰余類を係数とする変数Ｘの多項式を意味する。
【０００６】
また、第２のセキュリティ装置において、この暗号文Ｃにｒ-1を代入し（fm,r(r-1)）、その復号を行う。
ここで、例えば、平文ｍ１，ｍ２  から上述の暗号処理によって得られた暗号文をそれぞれC1=fm1,r(X) mod ZN[X]、C2=fm2,r(X) mod ZN[X]とすると、これらの暗号文の和はC1+C2=fm1,r(X)+fm2,r(X) mod ZN[X]となり、積はC1C2=fm1,r(X)fm2,r(X) mod ZN[X]となる。そして、後述のように、暗号文の和C1+C2、及び積C1C2の復号結果は、それぞれm1+m2 mod N、m1m2mod Nとなる。
また、上述のＮは合成数であり、本発明の安全性は、その素因数分解の困難性に基づいている（詳細は後述）。これは現在多くの暗号方式の安全性の根拠となっているものである。
【発明の効果】
【０００７】
本発明では、平文a、bの暗号文E(a)、E(b)の和E(a)+E(b)、及び積E(a)E(b)の復号結果が、それぞれa+b mod N、ab mod Nとなる。つまり、E(a)+E(b)=E(a+b)、E(a)E(b)=E(ab)が成立する。よって、a,bを知る事無く、E(a)、E(b)からE(a+b)とE(ab)の両方を求めることができる。
また、本発明の暗号アルゴリズムの安全性は、素因数分解問題に基づいており、十分な安全性を有しているといえる。
【発明を実施するための最良の形態】
【０００８】
以下、この発明の最良の実施の形態を説明する。
〔アルゴリズム〕
最初に、この形態の共通鍵暗号アルゴリズムについて説明する。なお、この説明では、暗号装置（「第１のセキュリティ装置」に相当）において平文ｍを暗号化し、その暗号文Ｃをインターネット等の安全でないネットワークを通じて復号装置に送信し、この復号装置（「第２のセキュリティ装置」に相当）で復号を行う場合を例にとる。
まず、ｐ，ｑを相異なる大きな素数、ＮをＮ＝ｐｑなる合成数とし、０以上Ｎ未満の整数の中から平文ｍを選ぶ。ここで、Ｎは公開として良く、少なくとも平文ｍの取得を目的とする復号装置はＮを知ることができるようにする。
【０００９】
そして、暗号装置は、０以上Ｎ未満でかつＮと互いに素な整数の中から秘密鍵ｒを選び、この秘密鍵ｒは、オフライン或いは公開鍵暗号を用いた方式等により、予め暗号装置、復号装置間で他に知られること無く安全に共有される。
そして、暗号装置は、平文ｍを復号装置だけが取得できるように、以下の操作によって
平文ｍの暗号文Ｃを作成する。
【００１０】
１. 自然数のパラメータｄを決定する。
２. ０以上Ｎ未満の整数の中からｄ個の適当な値ａｉ（i=1,…,d）を選ぶ（「加算項」に相当）。
３. 上述の式（１）を計算し、ａ0（「加算項」に相当）を求める。
４. 上述の式（２）を計算し、暗号文Ｃを求める。
【００１１】
そして、この多項式表現された平文ｍの暗号文Ｃを復号装置に送信する。なお、パラメータｄは自然数であり、ｄが大きい程処理量が増すが、その分安全性も向上していくため、ｄの大きさは用途に合わせて適切に選ぶ必要がある。
一方、復号装置は、受信した暗号文C=fm,r(X)に対し、秘密鍵ｒを用いて復号処理fm,r(r-1)modN=mを行う。これにより復号装置は平文ｍを取得でき、平文ｍは暗号装置から復号装置へと安全に送信されたことになる。
【００１２】
〔本アルゴリズムの特徴〕
次に、この形態の共通鍵暗号アルゴリズムが備える特徴について説明する。
今、２つの平文ｍ１，ｍ２から、この暗号処理により得られる２つの暗号文Ｃ１，Ｃ２を、C1=fm1,r(X)=a0,1+a1,1rX+a2,1r2X2mod ZN[X]、C2=fm2,r(X)=a0,2+a1,2rX+a2,2r2X2mod ZN[X]とする。即ち暗号文のパラメータｄは共にｄ＝２である。なお、添字の「ｍ１」「ｍ２」は、それぞれ「ｍ１」「ｍ２」を示す。
【００１３】
ここで、２つの暗号文Ｃ１，Ｃ２の和が、C1+C2=fm1,r(X)+fm2,r(X)=(a0,1+a0,2)+(a1,1+a1,2)rX+(a2,1+a2,2)r2X2mod ZN[X]=fm1+m2,r(X)となることは明らかである。これは、暗号文Ｃ１，Ｃ２から、平文ｍ１，ｍ２を知る事無く、その和m1+m2の暗号文fm1+m2,r(X)を求めることができることを意味している。
【００１４】
また、２つの暗号文Ｃ１，Ｃ２の積は、C1C2=fm1,r(X)fm2,r(X)=(a0,1+a1,1rX+a2,1r2X2)(a0,2+a1,2rX+a2,2r2X2) mod ZN[X]となり、復号結果の積は、fm1,r(r-1)fm2,r(r-1)=(a0,1+a1,1rr-1+a2,1r2r-2)(a0,2+a1,2rr-1+a2,2r2r-2) mod ZN[r-1]=(a0,1+a1,1+a2,1)(a0,2+a1,2+a2,2) mod Nとなる。ここで、この例のようにｄ＝２の場合、上述の式（１）から、m1=a0,1+a1,1+a2,1、m2= a0,2+a1,2+a2,2となり、fm1,r(r-1)fm2,r(r-1)=m1m2mod N=fm1m2,r(r-1)が成立していることが分かる。これにより、C1C2=fm1,r(X)fm2,r(X)=fm1m2,r(X)が成立していることも分かり、暗号文Ｃ１，Ｃ２から、平文ｍ１，ｍ２を知る事無く、その積m1m2の暗号文fm1m2,r(X)を求めることができることが分かる。
【００１５】
以上の特徴は、２つの暗号文Ｃ１，Ｃ２の次数が異なる場合についても同様である。例えば、C1=fm1,r(X)=a0,1+a1,1rX mod ZN[X]（d=1に相当）、C2=fm2,r(X)=a0,2+a1,2rX+a2,2r2X2mod ZN[X]（d=2に相当）の場合、C1+C2=fm1,r(X)+fm2,r(X)=(a0,1+a0,2)+(a1,1+a1,2)rX+a2,2r2X2mod ZN[X]=fm1+m2,r(X)となる。また、C1C2=fm1,r(X)fm2,r(X)=(a0,1+a1,1rX)(a0,2+a1,2rX+a2,2r2X2) mod ZN[X]となり、復号結果の積は、fm1,r(r-1)fm2,r(r-1)=(a0,1+a1,1rr-1)(a0,2+a1,2rr-1+a2,2r2r-2) mod ZN[r-1]=(a0,1+a1,1)(a0,2+a1,2+a2,2) mod Nとなる。ここで、上述の式（１）から、m1=a0,1+a1,1（d=1）、m2= a0,2+a1,2+a2,2（d=2）となり、fm1,r(r-1)fm2,r(r-1)=m1m2mod N=fm1m2,r(r-1)が成立していることが分かる。これにより、C1C2=fm1,r(X)fm2,r(X)=fm1m2,r(X)が成立していることが分かる。
【００１６】
さらに、暗号文Ｃから、平文ｍを知る事無く、任意のα∈ＺＮ（０以上Ｎ未満の整数の元）に対する平文α+ｍやαｍの暗号文を求めることもできる。即ち、例えば、C=fm,r(X)=a0+a1rX+a2r2X2mod ZN[X]とするとα+C=α+fm,r(X)=α+a0+a1rX+a2r2X2mod ZN[X]=fα+m,r(X)となり、αC=αfm,r(X)=αa0+αa1rX+αa2r2X2mod ZN[X]= fαm,r(X)となることは明らかである。
【００１７】
〔安全性〕
次に本形態の共通鍵暗号アルゴリズムの安全性について述べる。
まず、Ｎを素因数分解困難な合成数とする理由は以下による。
今、一組の平文・暗号文の組（ｍ，Ｃ）が与えられたとする。すると以下の関係を満たすｐｉ（i=0,1,…,d）が得られる。
【数１３】
2005084568.tif 000005
【００１８】
つまり、暗号文Ｃが与えられた場合、上述の式（２）より、暗号文Ｃの定数項ａ０を知ることができる。さらに平文ｍが与えられた場合、上述の式（１）に、この平文ｍと暗号文Ｃの定数項ａ０を代入することにより、上述の式（３）を得ることができる。また、暗号文Ｃが与えられた場合、上述の式（２）より、各係数を知ることができ、上述の式（４）を得ることができる。
【００１９】
ここで、上述の式（４）から、
ai=pi/ri mod N・・・(5)
が成り立つ。
また、上述の式（３）（５）から、
p0=p1/r + p2/r2 + … +pd/rdmod N
p0rd=p1rd-1 + p2rd-2 + … +pdmod N
【数１４】
2005084568.tif 000006
が得られる。
【００２０】
次に、ｄ−１組の平文・暗号文の組（ｍ，Ｃ）が与えられたとする。
この場合、ｐｉ（i=0,1,…,d）の組が異なる式（６）がｄ−１個得られる。そして、このｄ−１個の式（６）にガウスの消去法を適用すると、ｒについての２次式αr2+βr+γ mod N=0を得ることができる。ここで、もしＮが素数であれば、この２次式を容易に解くことができることが知られている。また、Ｎが合成数であっても、その素因数が分かれば中国人剰余定理より容易にｒを求めることができる。しかし、一般に合成数の素因数分解は困難であり、このような合成数Ｎであれば、ｒを求める方法は自明ではなく、効率的な解法は知られていない。そのため、秘密鍵ｒが攻撃者に知られないことを期待でき、この共通鍵暗号アルゴリズムの安全性も期待できる。
【００２１】
一方、ｄ組の平文・暗号文の組（ｍ，Ｃ）が攻撃者に知られた場合、この攻撃者は、ｐｉ（i=0,1,…,d）の組が異なるｄ個の式（６）を得ることができる。この場合、これらの式にガウスの消去法を適用すると、ｒについての１次式を求めることができ、攻撃者は、Ｎの素因数を知ることなく、容易にｒを求めることができる。よって、上述の自然数のパラメータｄは、安全でない暗号通信を行うと予想される回数よりも大きな値とすることが望ましい。これにより、ｄ組以上の平文・暗号文の組（ｍ，Ｃ）が攻撃者に知られ、安全性が低下してしまうことを防止できるからである。また、ｄが小さい程、暗号装置の計算処理量も小さく、処理の高速化等が期待できるため、ｄは安全でない暗号通信を行うと予想される回数＋１であることがより望ましく、現実的には、暗号装置が決定したパラメータｄに対し、暗号装置が秘密鍵ｒを用いて高々ｄ−１回の暗号通信しか行わないことが望ましい。この場合、この形態の暗号アルゴリズムの安全性は、素因数分解問題に基づいており、十分な安全性を有しているといえる。
【００２２】
また、別のパラメータｄの設定方法として、安全でない暗号通信を行った回数に、自然数を加算した値をパラメータｄとすることとしてもよい。この際、パラメータｄは、例えば、暗号通信ごとに再設定されるものとする。さらに、暗号装置の計算処理量等を考慮し、安全でない暗号通信を行った回数+１をパラメータｄとし、暗号通信ごとにパラメータｄを再設定することとしてもよい。
【００２３】
〔第１の実施の形態〕
次に、本発明における第１の実施の形態について説明する。
この形態は、暗号装置と復号装置が、インターネット等の安全でないネットワーク上で平文ｍを暗号通信する例である。
図１は、この形態のセキュリティシステム１の全体構成を例示した図である。また、図２は暗号装置２０の機能構成を、図３の（ａ）は外部機関装置１０の機能構成を、図３の（ｂ）は復号装置３０の機能構成を、それぞれ例示した図である。なお、外部機関装置１０、暗号装置２０及び復号装置３０は、ＣＰＵ(Central Processing Unit)、メモリ、バス等からなる公知のコンピュータに、所定のプログラムを実行させることによって構成されるものである。また、暗号装置２０、復号装置３０は、それぞれ、第１のセキュリティ装置、第２のセキュリティ装置に相当する。また、図４は、この形態におけるセキュリティ方法の処理手順を説明するためのフローチャートである。
【００２４】
以下、これらの図を用いて、この形態の構成及び処理の説明を行う。
外部機関装置１０はまず以下の処理を行う。
＜ステップＳ１＞
素数生成部１１で、フェルマーテスト等を用いて相異なる大きな素数ｐ，ｑを生成し、合成数生成部１２に送る。
＜ステップＳ２＞
合成数生成部１２で、合成数N=pqを計算し、合成数記憶部１３に送り、そこに記憶させる。
【００２５】
なお、３つの相異なる素数ｐ１，ｐ２，ｐ３の積Ｎ＝ｐ１ｐ２ｐ３等によって、合成数Ｎを生成することとしてもよく、適当に選んだＮ’が容易に素因数分解できず、かつ素数判定テストにより合成数であることが分かった場合に、このＮ’を合成数Ｎとすることとしてもよい。要は、合成数Ｎは、想定される攻撃者が素因数分解困難となるような値であれば良い（以下同様）。
【００２６】
＜ステップＳ３＞
合成数Nを公開する。ここで合成数Nを公開情報とするために、例えば外部機関装置１０が管理する誰でも閲覧可能なＷｅｂページにＮをアップロードしておけば良い。具体的には、例えば、合成数記憶部１３に記憶した合成数Nを、通信部１４からネットワーク４０を通じて送信できるようにしておく。
なお、合成数Ｎを暗号装置２０や復号装置３０以外の外部機関装置１０において生成することにより、暗号装置２０或いは復号装置３０が素因数分解容易な合成数Ｎを故意に作成するという不正を防止することができる。
【００２７】
次に、暗号装置２０は鍵生成処理として以下の処理を行う。
＜ステップＳ４＞
外部機関装置１０から公開された合成数Nを取得（抽出）する。具体的には、例えば、通信部２１（「合成数抽出手段」に相当）及びネットワーク４０を通じ、外部機関装置１０の通信部１４から出力された合成数Ｎを受信する。
＜ステップＳ５＞
秘密鍵生成部２２（「秘密鍵抽出手段」に相当）において、通信部２１から合成数Ｎを受け取り、０以上Ｎ未満でかつＮと互いに素な整数の中から、秘密鍵としてｒを適当に選ぶ（抽出する）。生成された秘密鍵ｒは秘密鍵記憶部２３に安全に記憶される。
【００２８】
なお、合成数Nと互いに素な整数ｒを選ぶという操作は、基本的には０以上Ｎ未満の整数を適当に選べば良い。その理由は、暗号装置２０は、Ｎの素因数ｐ，ｑを知らないため、意図的にＮと互いに素な整数を選ぶことができず、また、０以上Ｎ未満の整数の中から適当に選んだｒがＮの約数となる確率は、ｐ，ｑが非常に大きいため、無視できる程小さいからである。
【００２９】
＜ステップＳ６＞
秘密鍵ｒを復号装置３０と共有する。つまり、暗号装置２０が生成した秘密鍵ｒは、他に漏れる事無く、復号装置３０内の秘密鍵記憶部３１にも安全に格納される。これは、暗
号装置２０から復号装置３０へ秘密鍵ｒをオフラインで受け渡す、あるいは公開鍵暗号を利用してネットワーク上で送信する（産業図書「現代暗号」岡本龍明、山本博資著  Ｐ２００〜２０２記載のDiffile-Hellman鍵配送方式等）等で実現できる。
【００３０】
続いて、平文ｍの暗号処理として、暗号装置２０は以下の処理を行う。
＜ステップＳ７＞
平文選択部２４（「暗号化対象特定手段」に相当）において、通信部２１から合成数Ｎを受け取り、０以上Ｎ未満の整数の中から平文ｍ（「暗号化対象」に相当）を選ぶ。
なお、平文のビットサイズがＮ以上である場合は、例えば合成数Ｎから１を引いたものを１ブロックサイズとして、複数の平文ｍにブロック分割すれば良い。
＜ステップＳ８＞
パラメータ決定部２５において、自然数のパラメータｄを決定する。
【００３１】
なお、パラメータｄの決定は、例えば、同一の秘密鍵ｒを用い、盗聴者や第三者に対して平文を無視出来ない確率で推定されてしまう（例えばｍは０か１のどちらかである等）ような暗号通信を行った回数ｄｍａｘに依存し、ｄ＞ｄｍａｘとなるようなｄが選ばれる。
但しｄを大きくする程、暗号処理量、復号処理量、通信量が増大していくことは明らかなので、ｒを用いて暗号通信を行う回数を予め想定しておき、その上で適切なｄを選ぶのが好ましい。例えば、ｄｍａｘを予め想定してd=dmax+1とする。
【００３２】
＜ステップＳ９＞
整数選択部２６（「加算項選択手段」に相当）において、パラメータ決定部２５からパラメータｄを受け取り、通信部２１から合成数Ｎを受け取り、０以上Ｎ未満の整数の中からｄ個の適当な値（「加算項」に相当）ａi（i=1,…,d）を選ぶ。
＜ステップＳ１０＞
加減算部２７（「加算項選択手段」に相当）において、平文選択部２４から平文ｍを、通信部２１から合成数Ｎを、パラメータ決定部２５からパラメータｄを、整数選択部２６から加算項ａiを、それぞれ受け取り、上述の式（１）に従い加算項ａ０を算出する。
【００３３】
＜ステップＳ１１＞
暗号化部２８において、秘密鍵記憶部２３から秘密鍵ｒを抽出し、加減算部２７から加算項ａ０を受け取り、整数選択部２６から加算項ａiを受け取り、パラメータ決定部２５からパラメータｄを受け取り、通信部２１から合成数Ｎを受け取り、上述の式（２）に従い、暗号文Ｃを算出する。
＜ステップＳ１２＞
上記で得られた暗号文Ｃは通信部２１に送られ、そこからネットワーク４０を介し、復号装置３０に送信（出力）される。
【００３４】
続いて、暗号文Ｃの復号処理として、暗号装置３０は以下の処理を行う。
＜ステップＳ１３＞
送信された暗号文C=fm,r(X)は、復号装置３０の通信部３２（「暗号文入力手段」に相当）で受信され（入力を受け付け）、復号部３３に送られる。
＜ステップＳ１４＞
また、通信部３２（「合成数抽出手段」に相当）は、ネットワーク４０を介し、外部機関装置１０の通信部１４から送信された合成数Ｎも受信（抽出）し、復号部３３に送る。復号部３３（「秘密鍵抽出手段」に相当）は、さらに秘密鍵記憶部３１から秘密鍵ｒを抽出し、fm,r(r-1) mod N=mを計算する（暗号文にｒ-1を代入する）ことで、暗号文Ｃの復号結果ｍを得る。これにより、復号装置３０は平文ｍを取得することができた。
【００３５】
〔第２の実施の形態〕
次に、本発明における第２の実施の形態について説明する。
この形態は、秘密の値を保有する依頼装置が、代理演算装置にその秘密の値を知られること無く代理演算させ、更にその演算結果も代理演算装置に知られないような秘匿性の高い依頼計算方法を実現するものである。
【００３６】
図５は、この形態のセキュリティシステム１００の全体構成を例示した図である。また
、図６は、公知のコンピュータ上で、所定のプログラムを実行させることによって構成される依頼装置１１０（「第１のセキュリティ装置」に相当）の機能構成を、図７は代理演算装置１３０（「第２のセキュリティ装置」に相当）の機能構成を、それぞれ例示した図である。また、図８は、この形態におけるセキュリティ方法の処理手順を説明するためのフローチャートである。
【００３７】
以下、これらの図を用いて、この形態の構成及び処理の説明を行う。
この形態では、任意な多項式関数（「代理演算関数」に相当）ｇを保有する代理演算装置１３０と、ｋ個の秘密の値ｍｉ(i=1,…,k)を持ち、g(m1,…,mk)の取得を目的とする依頼装置１１０が存在し、依頼装置１１０は、ｋ個の値ｍｉとそれを入力とした演算結果g(m1,…,mk)を代理演算装置１３０に知られたくないものとする。
なお、ｇは依頼装置１１０に知られたくないような秘密の多項式関数、又は依頼装置１１０の計算資源等の理由から依頼装置１１０が外部の装置に演算を依頼する必要のある多項式関数であるとする。ここで例えばｇが署名関数であれば、これはブラインド署名と呼ばれる技術に他ならない（例えば、産業図書「現代暗号」岡本龍明、山本博資著  Ｐ１８４〜１８６参照。）。
【００３８】
依頼装置１１０は、ｍｉ(i=1,…,k)を暗号化するため、まず以下の処理を行う。
＜ステップＳ２０＞
素数生成部１１１において、相異なる大きな素数ｐ，ｑを生成し、合成数生成部１１２に送る。
＜ステップＳ２１＞
合成数生成部１１２において、合成数Ｎ＝ｐｑを計算する。
＜ステップＳ２２＞
秘密鍵生成部１１３（「秘密鍵抽出手段」に相当）において、合成数生成部１１２から合成数Ｎを抽出し、０以上Ｎ未満でかつＮと互いに素な整数の中から、秘密鍵としてｒを適当に選ぶ（抽出する）。秘密鍵ｒは秘密鍵記憶部１１４に送られ、そこで記憶される。
【００３９】
＜ステップＳ２３＞
平文選択部１１５（「暗号化対象特定手段」に相当）において、合成数生成部１１２から合成数Ｎを抽出し、０以上Ｎ未満の整数の中から平文ｍｉ(i=1,…,k)（「暗号化対象」に相当）を選ぶ。
＜ステップＳ２４＞
パラメータ決定部１１６において、自然数のパラメータｄを決定する。
ここで、代理演算装置１３０がｋ個の値ｍｉのうちｋ’個までの値を無視出来ない確率で推定可能である場合、秘密鍵ｒを秘匿するため、第１の実施の形態で説明した通り、パラメータｄをd=k'+1とすることが望ましい。なお、以下ではk'=k、即ち代理演算装置１３０が、ｋ次ベクトル(m1,…,mk)の値を無視出来ない確率で推定可能であるとする（d=k+1）。
【００４０】
＜ステップＳ２５＞
制御部１２２において、ｉに１を代入する。  
＜ステップＳ２６＞
整数選択部１１７において、パラメータ決定部１１６からパラメータｄを受け取り、合成数生成部１１２から合成数Ｎを抽出し、０以上Ｎ未満の整数の中からｄ個の適当な値ａｉ，ｊ（j=1,…,d）を選ぶ。
＜ステップＳ２７＞
加減算部１１８において、平文選択部１１５から平文ｍｉを、合成数生成部１１２から合成数Ｎを、パラメータ決定部１１６からパラメータｄを、整数選択部１１７から加算項ａｉ，ｊを、それぞれ受け取り、
【数１５】
2005084568.tif 000007
に従い加算項ａｉ，０を算出する。
【００４１】
＜ステップＳ２８＞
暗号化部１１９において、秘密鍵記憶部１１４から秘密鍵ｒを抽出し、加減算部１１８から加算項ａｉ，０を受け取り、整数選択部１１７から加算項ａｉ、ｊを受け取り、パラメータ決定部１１６からパラメータｄを受け取り、合成数生成部１１２から合成数Ｎを受け取り、
【数１６】
2005084568.tif 000008
に従い、暗号文Ｃｉを算出する。
＜ステップＳ２９＞
制御部１２２において、ｉ＝ｋであるか否かを判断し、ｉ＝ｋであればステップＳ３１に進み、ｉ＝ｋでなければステップＳ３０に進む。
【００４２】
＜ステップＳ３０＞
制御部１２２において、ｉにｉ＋１を代入し、ステップＳ２６に戻る。
＜ステップＳ３１＞
上記で得られたｍｉの暗号文Ｃｉ=fmi,r(X)（i=1,…,k）は通信部１２０に送られ、そこからネットワーク１４０を介し、代理演算装置１３０に送信される（添え字の「mi」は「ｍｉ」を意味する。）。
【００４３】
続いて、代理演算処理として、代理演算装置１３０は以下の処理を行う。
＜ステップＳ３２＞
通信部１３１において、暗号文Ｃｉ=fmi,r(X)（i=1,…,k）を受信し（入力を受け付け）、受信した暗号文Ｃｉを関数演算部１３２に送る。
＜ステップＳ３３＞
関数演算部１３２において、代入結果G(X)=g(C1,…,Ck)を計算（暗号文Ｃｉを代理演算関数に代入）し、通信部１３１に送る。ここで、代理演算装置１３０は、平文ｍｉの暗号文Ｃｉしか受け取っていないため、暗号文Ｃｉを復号出来なければ、平文ｍｉは代理演算装置１３０に知られないことになる。
【００４４】
＜ステップＳ３４＞
通信部１３１において、ネットワーク１４０を通じ、代入結果G(X)を依頼装置１１０に返信（出力）する。
＜ステップＳ３５＞
続いて、復号処理として、依頼装置１１０は、通信部１２０において、代入結果Ｇ（Ｘ）を受信し（入力を受け付け）、復号部１２１に送る。そして復号部１２１において、秘密鍵記憶部１１４から秘密鍵ｒを抽出し、代入結果Ｇ（Ｘ）の復号結果G(r-1)=g(m1,…,mk)を算出する。
ここで、G(r-1)=g(m1,…,mk)が成り立つことは、前述の〔本アルゴリズムの特徴〕で示した本形態の暗号アルゴリズムの性質から明らかである。
【００４５】
また、多項式関数ｇは、ｈ次ｋ変数多項式
【数１７】
2005084568.tif 000009
として一般化できる。この場合、多項式関数ｇには、最大で(h+k)!/(h!k!)個の係数αｑ１,…,ｑｋが存在することになる。
これに対し、d=k+1の場合、代入結果Ｇ（Ｘ）は高々ｈ(k+1)次の多項式となり、高々ｈ(k+1)+1個の係数しか持たない。従って、ｋ，ｈが大きければ、代入結果Ｇ（Ｘ）のデータサイズは、元々の多項式関数g(Y1,…,Yk)のデータサイズよりも非常に小さくなる。つまり、本形態で示した方法は、依頼装置１１０のメモリが非常に限られている場合等に特に有効であるといえる。
【００４６】
次に、上記の例に対し更にデータサイズを抑える方法を述べる。
代入結果Ｇ（Ｘ）は、
【数１８】
2005084568.tif 000010
と書ける。
そして、G(r-1)=g(m1,…,mk) mod Nであるから、
【数１９】
2005084568.tif 000011
が成り立つ。
【００４７】
このことから、代理演算装置１３０はＧ（Ｘ）を計算後、まずＧ（Ｘ）の定数項ｂ０を依頼装置１１０に送信し、それを受信した依頼装置１１０は、A←ｂ０としてＡを保存する。次に、代理演算装置１３０はＧ（Ｘ）の１次の項の係数ｂ１ｒを依頼装置１１０に送信し、それを受信した依頼装置１１０は、b1r/r=b1を計算し、A←A+b1modNとしてAを保存する。この操作を繰り返していき、最終的に代理演算装置１３０は、Ｇ（Ｘ）のｕ次の項の係数ｂｕｒｕを依頼装置１１０に送信し、それを受信した依頼装置１１０は、buru/ru=buを計算し、A←A+bumodNとすれば、
【数２０】
2005084568.tif 000012
を得ることができる。この手法により、明らかに依頼装置１１０の必要とするメモリを削減することができる。
【００４８】
〔第３の実施の形態〕
次に、本発明における第３の実施の形態について説明する。
この形態は、ある秘密の平文を保有する依頼装置が、その平文の暗号処理を代理暗号装置に依頼し、この平文を代理暗号装置に知られること無く、暗号文を取得するものである。
前述の〔本アルゴリズムの特徴〕で述べたように、ａ，ｂを任意の平文、Ｅを本形態の暗号関数とした場合、E(a)+E(b)=E(a+b),E(a)E(b)=E(ab)となるためにはａ，ｂの暗号処理に用いる秘密鍵（すなわちｒ）が同一でなければならない。例えば、ａ，ｂ，ｃがそれぞれ依頼装置Ａ，依頼装置Ｂ，依頼装置Ｃの保有する平文であり、自身の平文は知られたくないがabc+a+b+cは全依頼装置が知りたいとしたとき、本形態の暗号アルゴリズムを用いれば、E(a),E(b),E(c)からE(a)E(b)E(c)+E(a)+E(b)+E(c)=E(abc+a+b+c)を計算することができる。しかし、この場合、暗号処理するための秘密鍵は同一でなければならず、少なくとも秘密鍵を保有する装置に対してはａ，ｂ，ｃを秘匿とすることはできない。
【００４９】
この問題を解決するために、本実施の形態では、依頼装置が代理暗号装置に平文を与え
る事無く暗号処理を依頼する。この場合、各依頼装置が取得する暗号文は、全て代理暗号装置の秘密鍵で暗号化したものとなる。これにより、依頼装置Ａ，依頼装置Ｂ，依頼装置Ｃは、秘密鍵の内容を知ることなく、それぞれE(a),E(b),E(c)を取得でき、それらE(a),E(b),E(c)からE(a)E(b)E(c)+E(a)+E(b)+E(c)=E(abc+a+b+c)を計算することが可能となる。
【００５０】
この単純な方法として、（ａ）依頼装置が自身の平文ｍを選択し、０以上Ｎ未満の整数の中から適当な値αを選び、α+m mod Nを計算してそれを代理暗号装置に送信し、（ｂ）代理暗号装置が、この平文α+mに対して、秘密鍵ｒを用いて上述の式（１）により暗号文fα+m,r(X)を計算し、それを依頼装置に返信し、（ｃ）依頼装置が、fα+m,r(X)-αを計算してｍの暗号文fm,r(X)を得る、という方法も採れる。
【００５１】
しかし、fα+m,r(X)とfm,r(X)は定数項を除き等しい。そのため、代理暗号装置は、これら２つの暗号文が対応しており、定数項の差がαであることが高い確率で分かる。そして、代理暗号装置は、α+mとfα+m,r(X)が対応していることを知ってしまえば、fα+m,r(X)-αにより容易にｍを求めることができる。
【００５２】
また、（ａ）依頼装置が自身の平文ｍを選択し、０以上Ｎ未満の整数の中から適当な値αを選び、αm mod Nを計算してそれを代理暗号装置に送信し、（ｂ）代理暗号装置が、この平文αmに対して、秘密鍵ｒを用いて上述の式（１）により暗号文fαm,r(X)を計算し、それを依頼装置に返信し、（ｃ）依頼装置が、fαm,r(X)×α-1を計算してｍの暗号文fm,r(X)を得る、という方法も採れる。
【００５３】
しかしこの場合は、fαm,r(X)とfm,r(X)が定数倍の関係を持っている。そのため、代理暗号装置は、これら２つの暗号文が対応しており、これらがα倍の関係にあることが高い確率で分かる。そして、代理暗号装置は、αmとfαm,r(X)が対応していることを知ってしまえば、fαm,r(X)×α-1により、やはり容易にｍを求めることができる。
【００５４】
以降本形態では、代理暗号装置に対してもmを秘匿とすることを目的とした別の方法を与える。
図９は、この形態のセキュリティシステム２００の全体構成を例示した図である。また、図１０は、公知のコンピュータ上で、所定のプログラムを実行させることによって構成される依頼装置２２０（「第１のセキュリティ装置」に相当）の機能構成を、図１１は代理暗号装置２３０（「第２のセキュリティ装置」に相当）の機能構成を、それぞれ例示した図である。また、図１２〜１４は、この形態におけるセキュリティ方法の処理手順を説明するためのフローチャートである。なお、外部機関装置２１０の構成・処理は、第１の実施の形態と同様である（図３の（ａ））。
【００５５】
以下、これらの図を用いて、この形態の構成及び処理の説明を行う。
外部機関装置２１０はまず以下の処理を行う。
＜ステップＳ４０＞
相異なる大きな素数p,qを生成する。
＜ステップＳ４１＞
合成数N=pqを計算する。
＜ステップＳ４２＞
合成数Nを公開する。
【００５６】
次に代理暗号装置２３０は以下の処理を行う。
＜ステップＳ４３＞
通信部２３１において、Nを受信する。
＜ステップＳ４４＞
素数生成部２３２において、相異なる大きな素数p',q'を生成する。
＜ステップＳ４５＞
合成数生成部２３３において、N'=p'q'を計算する。
＜ステップＳ４６＞
合成数生成部２３４において、合成数生成部２３３からN'を受け取り、通信部２３１からNを受け取り、合成数N’’=NN'を計算する。この合成数N’’は合成数記憶部２３５に記憶される。
【００５７】
＜ステップＳ４７＞
秘密鍵生成部２３６において、合成数記憶部２３５から合成数N’’を抽出し、０以上N’’未満でかつN’’と互いに素な整数の中から、秘密鍵としてｔを適当に選ぶ。
＜ステップＳ４８＞
N’’を公開する。即ち、合成数記憶部２３５に記憶された合成数N’’を、通信部２３１及びネットワーク２５０を通じて送信可能とする。
なお、上記のように合成数をN’’=NN'としたのは、外部機関装置２１０に対しても代理暗号装置２３０に対しても合成数に対する素因数分解を困難とするためである。即ちこの合成数を、複数の装置でそれぞれ生成された合成数の積とすることにより、各装置が素因数分解容易な合成数を故意に作成するといった不正を防止することができる。
【００５８】
次に依頼装置２２０は以下の処理を行う。
＜ステップＳ４９＞
通信部２２１において、代理暗号装置２３０から送信された合成数N’’を受信する。
＜ステップＳ５０＞
秘密鍵生成部２２２において、通信部２２１から合成数N’’を受け取り、０以上Ｎ’’未満でかつＮ’’と互いに素な整数の中から、秘密鍵としてｒを適当に選ぶ。選択された秘密鍵ｒは、秘密鍵記憶部２２３に送られ、そこで記憶される。
＜ステップＳ５１＞
平文選択部２２４において、通信部２２１から合成数N’’を受け取り、０以上Ｎ’’未満の整数の中から平文ｍを選ぶ。
【００５９】
＜ステップＳ５２＞
パラメータ決定部２２５において、自然数のパラメータdを決定する。
＜ステップＳ５３＞
整数選択部２２６において、通信部２２１から合成数N’’を受け取り、０以上Ｎ’’未満の整数の中からｄ個の適当な値ai(i=1,…,d)を選ぶ。  
＜ステップＳ５４＞
加減算部２２７において、平文選択部２２４から平文ｍを、通信部２２１から合成数Ｎ’’を、パラメータ決定部２２５からパラメータｄを、整数選択部２２６から加算項ａiを、それぞれ受け取り、
【数２１】
2005084568.tif 000013
に従い加算項ａ０を算出する。
【００６０】
＜ステップＳ５５＞
暗号化部２２８において、秘密鍵記憶部２２３から秘密鍵ｒを抽出し、加減算部２２７から加算項ａ０を受け取り、整数選択部２２６から加算項ａiを受け取り、パラメータ決定部２２５からパラメータｄを受け取り、通信部２２１から合成数Ｎ’’を受け取り、
【数２２】
2005084568.tif 000014
に従い、暗号文Ｃを算出する。
＜ステップＳ５６＞
算出された暗号文Ｃは、通信部２２１に送られ、ネットワーク２５０を通じ、代理暗号装置２３０に送信される。
【００６１】
依頼装置２２０から暗号文Ｃが送られた代理暗号装置２３０は、以下の処理を行う。
＜ステップＳ５７＞
通信部２３１において、暗号文C=fm,r(X)を受信する（入力を受け付ける）。
＜ステップＳ５８＞
パラメータ決定部２３８において、パラメータｄ’を決定する。
＜ステップＳ５９＞
多項式選択部２３９（「加算項選択手段」に相当）において、パラメータ決定部２３８からパラメータｄ’を受け取り、合成数記憶部２３５から合成数Ｎ’’を抽出し、０以上Ｎ’’未満の整数を各項の係数とする一変数ｄ’次多項式の中から、ｄ’個の適当な多項式ｂｉ(Ｘ)(i=1,…,d’)（「加算項」に相当）を選ぶ。
＜ステップＳ６０＞
加減算部２４０（「加算項選択手段」に相当）において、通信部２３１から暗号文Ｃを、合成数記憶部２３５から合成数Ｎ’’を、パラメータ決定部２３８からパラメータｄ’を、多項式選択部２３９から加算項ｂｉ(Ｘ)を、それぞれ受け取り、
【数２３】
2005084568.tif 000015
に従って加算項ｂ０(Ｘ)を算出する。
【００６２】
＜ステップＳ６１＞
暗号化部２４１において、秘密鍵記憶部２３７から秘密鍵ｔを抽出し、加減算部２４０から加算項ｂ０(Ｘ)を受け取り、多項式選択部２３９から加算項ｂｉ(Ｘ)を受け取り、パラメータ決定部２３８からパラメータｄ’を受け取り、合成数記憶部２３５から合成数Ｎ’’を受け取り、
【数２４】
2005084568.tif 000016
に従い、暗号文Ｃ’を算出する。
＜ステップＳ６２＞
算出された暗号文Ｃ’は通信部２３１に送られ、そこからネットワーク２５０を通じて、依頼装置に返信（出力）される。
【００６３】
次に、依頼装置２２０は、以下の処理を行う。
＜ステップＳ６３＞
通信部２２１において、暗号文Ｃ’を受信する（入力を受け付ける）。
＜ステップＳ６４＞
復号部２２９において、通信部２２１から暗号文Ｃ’を受け取り、秘密鍵記憶部２２３から秘密鍵ｒを抽出し、暗号文C’の秘密鍵ｒを用いた復号処理F(Y)=fC,t(r-1,Y)を行い、復号結果F(Y)を得る。するとＦ（Ｙ）は、平文ｍを、代理暗号装置２３０の秘密鍵ｔで暗号処理した暗号文ｆｍ，ｔ（Ｙ）とみることができる。
ここで、代理暗号装置２３０が、Ｆ（Ｙ）を復号せずにＣ’とＦ（Ｙ）の対応関係を判定することは容易でない。よって、代理暗号装置２３０が暗号文Ｃ’からＦ（Ｙ）を特定し、その復号によって平文ｍを取得することは困難である。
最後に、Ｆ（Ｙ）が平文ｍを秘密鍵ｔで暗号処理した暗号文であること、即ち、F(t-1)=m
mod N’’となることを確認しておく。
【００６４】
まず、F(Y)=fC,t(r-1,Y)について、上述の式（９）より、
【数２５】
2005084568.tif 000017
が成り立つ。
また、上述の式（８）より、
【数２６】
2005084568.tif 000018
であり、上述の式（７）より、暗号文ＣのＸにｒ-1を代入した復号結果はfm,r(r-1)=m mod N’’である。よって、式（１１）より、
【数２７】
2005084568.tif 000019
も成り立つ。
よって、上述の式（１０）（１２）より、
【数２８】
2005084568.tif 000020
が成り立つことが分かる。
【００６５】
〔第４の実施の形態〕
次に、本発明における第４の実施の形態について説明する。
この形態は、代理暗号装置の秘密鍵で暗号処理された暗号文を保有する依頼装置が、代理復号装置にその復号処理を依頼し、その代理復号装置に平文を知られること無く、この依頼装置が平文を取得するものである。
【００６６】
図１５は、この形態のセキュリティシステム３００の全体構成を例示した図である。また、図１６は、公知のコンピュータ上で、所定のプログラムを実行させることによって構成される依頼装置３１０（「第１のセキュリティ装置」に相当）の機能構成を、図１７は代理復号装置３３０（「第２のセキュリティ装置」に相当）の機能構成を、それぞれ例示した図である。また、図１８及び１９は、この形態におけるセキュリティ方法の処理手順を説明するためのフローチャートである。なお、代理暗号装置３５０の構成・処理は、第３の実施の形態の代理暗号装置２３０と同様である（図１１）。
【００６７】
以下、これらの図を用いて、この形態の構成及び処理の説明を行う。
依頼装置３１０は、例えば第３の実施の形態で取得した暗号文F(Y)=fm,t(Y)を暗号文記憶部３１１内に保有しており、代理復号装置３３０は秘密鍵記憶部３３１内に秘密鍵ｔを保有している。
まず依頼装置３１０は以下の処理を行う。
＜ステップＳ７０＞
まず、通信部３１２、ネットワーク３４０を通じ、代理暗号装置３５０から公開・送信された合成数Ｎ’’を受信（抽出）する。次に、秘密鍵生成部３１３において、この合成数Ｎ’’を受け取り、０以上Ｎ’’未満でかつN’’と互いに素な整数の中から、秘密鍵としてｒを適当に選ぶ（抽出する）。秘密鍵ｒは秘密鍵記憶部３１４に送られ、そこに記憶される。
【００６８】
＜ステップＳ７１＞
パラメータ決定部３１５において、自然数のパラメータd’’を決定する。
＜ステップＳ７２＞
多項式選択部３１６において、パラメータ決定部３１５からパラメータｄ’’を受け取り、通信部３１２から合成数Ｎ’’を抽出し、０以上Ｎ’’未満の整数を各項の係数とする一変数ｄ’’次多項式の中から、ｄ’’個の適当な多項式ｂ’ｉ(Y)(i=1,…,d’’)を
選ぶ。
＜ステップＳ７３＞
加減算部３１７において、暗号文記憶部３１１から暗号文Ｆ（Ｙ）を、通信部３１２から合成数Ｎ’’を、パラメータ決定部３１５からパラメータｄ’’を、多項式選択部３１６から加算項ｂ’ｉ(Y)を、それぞれ受け取り、
【数２９】
2005084568.tif 000021
に従って加算項ｂ’0(Y)を算出する。
【００６９】
＜ステップＳ７４＞
暗号化部３１８において、秘密鍵記憶部３１４から秘密鍵ｒを抽出し、加減算部３１７から加算項ｂ’０(Ｙ)を受け取り、多項式選択部３１６から加算項ｂ’０(Ｙ)を受け取り、パラメータ決定部３１５からパラメータｄ’’を受け取り、通信部３１２から合成数Ｎ’’を受け取り、
【数３０】
2005084568.tif 000022
に従い、暗号文Ｃ’’を算出する。
＜ステップＳ７５＞
算出された暗号文Ｃ’’は、通信部３１２に送られ、ネットワーク３４０を通じ、代理復号装置３３０に送信（出力）される。
【００７０】
依頼装置３１０から暗号文Ｃ’’が送られた代理復号装置３３０は、以下の処理を行う。
＜ステップＳ７６＞
通信部３３２において暗号文Ｃ’’を受信する（入力を受け付ける）。
＜ステップＳ７７＞
復号部３３において、通信部３３２から暗号文Ｃ’’を受け取り、秘密鍵記憶部３３１から秘密鍵ｔを抽出し、
【数３１】
2005084568.tif 000023
を計算する。
＜ステップＳ７８＞
算出された復号結果Ｆ’（Ｚ）は、通信部３３２及びネットワーク３４０を通じ、依頼装置３１０に返信（出力）される。
【００７１】
次に、依頼装置３１０は、以下の処理を行う。
＜ステップＳ７９＞
通信部３１２において、復号結果Ｆ’（Ｚ）を受信し（入力を受け付け）、復号部３２０に送る。
＜ステップＳ８０＞
復号部３２０において、秘密鍵記憶部３１４から秘密鍵ｒを抽出し、暗号文Ｆ’（Ｚ）に対し、秘密鍵ｒを用いた復号処理F’(r-1)=mを行い、平文ｍを得る。なお、F’(r-1)=mが成り立つことは第３の実施の形態と同様の手法で示すことができるため、ここでは説明を省略する。
【００７２】
〔第５の実施の形態〕
次に、本発明における第５の実施の形態について説明する。
本形態は、ある秘密の平文を保有する依頼装置が、複数の代理暗号機関装置に暗号処理を依頼し、多重暗号文を生成するものである。
【００７３】
図２０は、この形態のセキュリティシステム４００の全体構成を例示した図である。また、図２１は、公知のコンピュータ上で、所定のプログラムを実行させることによって構成される代理暗号装置４１０（「第２のセキュリティ装置」に相当）の機能構成を、図２
２は代理暗号装置４３０（「第２のセキュリティ装置」に相当）の機能構成を、図２３及び図２４は依頼装置４５０（「第１のセキュリティ装置」に相当）の機能構成を、それぞれ例示した図である。また、図２５〜２９は、この形態におけるセキュリティ方法の処理手順を説明するためのフローチャートである。
【００７４】
以下、これらの図を用いて、この形態の構成及び処理の説明を行う。
今、２つの代理暗号装置４１０、４３０があるものとする。これらは依頼装置４５０からの依頼により暗号処理を行う。
代理暗号装置４１０はまず以下の処理を行う。
＜ステップＳ９０＞
素数生成部４１１において、相異なる大きな素数p,qを生成し、合成数生成部４１２に送る。
＜ステップＳ９１＞
合成数生成部４１２において、合成数NA=pqを計算し、合成数記憶部４１３に送り、そこで記憶させる。
＜ステップＳ９２＞
NAを公開する。即ち、合成数記憶部４１３に格納された合成数NＡを、通信部４１４及びネットワーク４７０を通じて送信可能とする。
【００７５】
同様に代理暗号装置４３０はまず以下の処理を行う。
＜ステップＳ１００＞
素数生成部４３１において、相異なる大きな素数p’,q’を生成し、合成数生成部４３２に送る。
＜ステップＳ１０１＞
合成数生成部４３２において、合成数NB=p’q’を計算し、合成数記憶部４３３に送り、そこに記憶させる。
＜ステップＳ１０２＞
NＢを公開する。即ち、合成数記憶部４３３に格納された合成数NＢを、通信部４３４及びネットワーク４７０を通じて送信可能とする。
【００７６】
次に代理暗号装置４１０は以下の処理を行う。
＜ステップＳ９３＞
通信部４１４において、代理暗号装置４３０より公開・送信された合成数NBを取得する。
＜ステップＳ９４＞
合成数生成部４１５において、合成数記憶部４１３から合成数ＮＡを抽出し、通信部４１４から合成数ＮＢを受け取り、合成数N=NANBを計算する。生成した合成数Ｎは、合成数記憶部４１６に送られ、そこに記憶される。
＜ステップＳ９５＞
Nを公開する。即ち、合成数記憶部４１６に格納された合成数Nを、通信部４１４及びネットワーク４７０を通じて送信可能とする。
＜ステップＳ９６＞
秘密鍵生成部４１７において、合成数記憶部４１６から合成数Ｎを抽出し、０以上Ｎ未満でかつＮと互いに素な整数の中から、秘密鍵としてrを適当に選ぶ。秘密鍵ｒは秘密鍵記憶部４１８に記憶される。
【００７７】
同様に代理暗号装置４３０は以下の処理を行う。
＜ステップＳ１０３＞
通信部４３４において、代理暗号装置４１０より公開・送信された合成数NＡを取得する。
＜ステップＳ１０４＞
合成数生成部４３５において、合成数記憶部４３３から合成数ＮＢを抽出し、通信部４３４から合成数ＮＡを受け取り、合成数N=NANBを計算する。生成した合成数Ｎは、合成数記憶部４３６に送られ、そこに記憶される。
＜ステップＳ１０５＞
Nを公開する。即ち、合成数記憶部４３６に格納された合成数Nを、通信部４３４及びネットワーク４７０を通じて送信可能とする。
＜ステップＳ１０６＞
秘密鍵生成部４３７において、合成数記憶部４３６から合成数Ｎを抽出し、０以上Ｎ未満でかつＮと互いに素な整数の中から、秘密鍵としてｓを適当に選ぶ。秘密鍵ｓは秘密鍵記憶部４３８に記憶される。
【００７８】
次に依頼装置４５０は以下の処理を行う。
＜ステップＳ１１０＞
通信部４５１において、代理暗号装置４１０又は４２０より公開・送信された合成数Nを受信する。
＜ステップＳ１１１＞
秘密鍵生成部４５２において、通信部４５１から合成数Ｎを取得し、０以上Ｎ未満でかつＮと互いに素な整数の中から、秘密鍵としてtを適当に選ぶ。秘密鍵ｔは秘密鍵記憶部４５３に送られ、そこに記憶される。
＜ステップＳ１１２＞
平文選択部４５４において、通信部４５１から合成数Ｎを取得し、０以上Ｎ未満の整数の中から平文ｍを選ぶ。
＜ステップＳ１１３＞
パラメータ決定部４５５において、自然数のパラメータdを決定する。
＜ステップＳ１１４＞
整数選択部４５６において、通信部４５１から合成数Ｎを受け取り、パラメータ決定部４５５からパラメータｄを受け取り、０以上Ｎ未満の整数の中からｄ個の適当な値ａｉ(i=1,…,d)を選ぶ。
＜ステップＳ１１５＞
加減算部４５７において、平文選択部４５４から平文ｍを、通信部４５１から合成数Ｎを、パラメータ決定部４５５からパラメータｄを、整数選択部４５６から加算項ａiを、それぞれ受け取り、上述の式（１）に従い加算項ａ０を算出する。
【００７９】
＜ステップＳ１１６＞
暗号化部４５８において、秘密鍵記憶部４５３から秘密鍵ｔを抽出し、加減算部４５７から加算項ａ０を受け取り、整数選択部４５６から加算項ａiを受け取り、パラメータ決定部４５５からパラメータｄを受け取り、通信部４５１から合成数Ｎを受け取り、
【数３２】
2005084568.tif 000024
に従い、暗号文Ｃを算出する。
＜ステップＳ１１７＞
通信部４５１及びネットワーク４７０を通じ、算出された暗号文Ｃを代理暗号装置４１０に送信する。
【００８０】
次に代理暗号装置４１０は以下の処理を行う。
＜ステップＳ１１８＞
通信部４１４において、暗号文Ｃを受信し、加減算部４２１に送る。
＜ステップＳ１１９＞
第３の実施の形態で述べた方法（パラメータ決定部４１９、多項式選択部４２０、加減算部４２１及び暗号化部４２２におけるステップＳ５８〜Ｓ６１と同様な処理）により、暗号文Cに対し、秘密鍵記憶部４１８の秘密鍵rを用いて暗号処理を行い、暗号文C’=fC,r(X,Y)を生成する。
＜ステップＳ１２０＞
通信部４１４及びネットワーク４７０を通じ、生成された暗号文Ｃ’を依頼装置４５０に返信する。
【００８１】
次に依頼装置４５０は以下の処理を行う。
＜ステップＳ１２１＞
通信部４５１において、暗号文Ｃ’を受信する。
＜ステップＳ１２２＞
復号部４５９において、通信部４５１から暗号文Ｃ’を受け取り、秘密鍵記憶部４５３から秘密鍵ｔを抽出し、復号処理F(Y)=fC,r(t-1,Y)を行いF(Y)を得る。第３の実施の形態同様、F(Y)は平文mを秘密鍵rで暗号処理した暗号文
【数３３】
2005084568.tif 000025
とみることができる。これにより依頼装置４５０は代理暗号装置４１０の秘密鍵ｒを用いて暗号処理した暗号文を得ることができた。
【００８２】
次に依頼装置４５０は以下の処理を行う。
＜ステップＳ１２３＞
秘密鍵生成部４６０において、通信部４５１から合成数Ｎを受け取り、０以上Ｎ未満でかつＮと互いに素な整数の中から、秘密鍵としてt'を適当に選ぶ。秘密鍵ｔ’は秘密鍵記憶部４６１に送られ、そこで記憶される。
＜ステップＳ１２４＞
パラメータ決定部４６２において、パラメータd’’を決定する。
＜ステップＳ１２５＞
多項式選択部４６３において、パラメータ決定部４６２からパラメータｄ’’を受け取り、通信部４５１から合成数Ｎを受け取って、０以上Ｎ未満の整数を各項の係数とする一変数ｄ’’次多項式の中から、d’’個の適当な多項式（「加算項」に相当）ｃｉ(Ｙ)(i=1,…,d’’)を選ぶ。
【００８３】
＜ステップＳ１２６＞
加減算部４６４において、復号部４５９から暗号文Ｆ（Ｙ）を暗号化対象として受け取り、通信部４５１から合成数Ｎを受け取り、パラメータ決定部４６２からパラメータｄ’’を受け取り、多項式選択部４６３から加算項ｃｉを受け取って、
【数３４】
2005084568.tif 000026
に従い、加算項ｃ0（Ｙ）を算出する。
【００８４】
＜ステップＳ１２７＞
暗号化部４６５において、秘密鍵記憶部４６１から秘密鍵ｔ’を抽出し、加減算部４６４から加算項ｃ0（Ｙ）を受け取り、多項式選択部４６３から加算項ｃｉ（Ｙ）を受け取り、パラメータ決定部４６２からパラメータｄ’’を受け取り、通信部４５１から合成数Ｎを受け取り、
【数３５】
2005084568.tif 000027
に従い、暗号文Ｃ’’を算出する。
＜ステップＳ１２８＞
算出された暗号文Ｃ’’は、通信部４５１及びネットワーク４７０を通じ、代理暗号装置４３０に送信される。
【００８５】
次に代理暗号装置４３０は、以下の処理を行う。
＜ステップＳ１２９＞
通信部４３４において、暗号文Ｃ’’を受信する。
＜ステップＳ１３０＞
パラメータ決定部４３９において、パラメータd’’’を決定する。
＜ステップＳ１３１＞
多項式選択部４４０において、パラメータ決定部４３９からパラメータｄ’’’を受け取り、合成数記憶部４３６から合成数Ｎを抽出し、０以上Ｎ未満の整数を各項の係数とする二変数ｄ’’’次多項式の中から、ｄ’’’個の適当な多項式（「加算項」に相当）ｅｉ(Ｘ，Ｙ)（i=1,…,d’’’）を選ぶ。
【００８６】
＜ステップＳ１３２＞
加減算部４４１において、通信部４３４から暗号文Ｃ’’を受け取り、合成数記憶部４３６から合成数Ｎを抽出し、パラメータ決定部４３９からパラメータｄ’’’を受け取り、多項式選択部４４０から加算項ｅｉ(Ｘ，Ｙ)を受け取って、
【数３６】
2005084568.tif 000028
に従い、加算項ｅ０(Ｘ，Ｙ)を算出する。
＜ステップＳ１３３＞
暗号化部４４２において、秘密鍵記憶部４３８から秘密鍵ｓを抽出し、加減算部４４１から加算項ｅ０(Ｘ，Ｙ)を受け取り、多項式選択部４４０から加算項ｅｉ(Ｘ，Ｙ)を受け取り、パラメータ決定部４３９からパラメータｄ’’’を受け取り、合成数記憶部４３６から合成数Ｎを抽出し、
【数３７】
2005084568.tif 000029
に従い、暗号文Ｃ’’’を算出する。
＜ステップＳ１３４＞
算出された暗号文Ｃ’’’は、通信部４３４及びネットワーク４７０を通じ、依頼装置４５０に返信される。
【００８７】
次に、依頼装置４５０は以下の処理を行う。
＜ステップＳ１３５＞
通信部４５１において、暗号文Ｃ’’’を受信する。
＜ステップＳ１３６＞
復号部４６６において、通信部４５１から、暗号文Ｃ’’’を受け取り、秘密鍵記憶部４６１から秘密鍵ｔ’を抽出し、復号処理F’(Y,Z)=fC’’,s(t-1,Y,Z)を行い、復号結果Ｆ’(Ｙ，Ｚ)を得る。この復号結果Ｆ’（Ｙ，Ｚ）は、平文ｍを秘密鍵ｒで暗号処理した暗号文を、更に秘密鍵ｓで暗号処理した暗号文fm,(r,s)(Y,Z) mod ZN[Y,Z]とみることができる。
【００８８】
このように、本形態では、代理暗号装置を複数設け、秘密鍵、パラメータ及び加算項を、代理暗号装置ごとに独立して設定した。そして、代理暗号装置から依頼装置４５０に送信された暗号文の復号結果を、依頼装置４５０の暗号化対象とし、その暗号文の出力先となる代理暗号装置を変更しつつ、第３の実施の形態の処理を繰り返すこととした。これにより依頼装置４５０は、代理暗号装置４１０の秘密鍵ｒと代理暗号装置４３０の秘密鍵ｓを用いて暗号処理した多重暗号文を得ることができた。そして、この多重暗号文が代理暗号装置４１０、４３０の何れかに知られたとしても、各代理暗号装置４１０、４３０単独では、この代理暗号文から平文ｍを復号することはできない。これにより、安全性がより向上した。
【００８９】
なお、この例では代理暗号装置４１０、４３０が２つの場合を例に挙げたが、３つ以上の代理暗号装置がある場合でも、本質的に同じ手続きを繰り返すことで、多重に暗号化さ
れた暗号文を生成できる。
またＦ’(Y,Z)に対する復号処理は代理復号装置が行うことになるが、その順序は暗号処理の順序とは関係なく、どちらから行っても最終的にｍを得ることができる。
【００９０】
更に復号処理の際に第４の実施の形態を組み合わせることで、代理復号装置に平文を知られないようにすることができる。即ち、代理復号装置（「第２のセキュリティ装置」に相当）を複数設け、代理復号装置から依頼装置（「第１のセキュリティ装置」に相当）に送信された暗号文を復号した結果を、この依頼装置の暗号化対象とし、その暗号文の出力先となる代理復号装置を変更しつつ、第４の実施の形態の処理を繰り返すことにより、この効果を得ることができる。
【００９１】
〔第６の実施の形態〕
次に、本発明における第６の実施の形態について説明する。
本形態は、それぞれ秘密値を保有する複数の依頼装置が、自身の秘密値を他の依頼装置に明かす事無く、それら秘密値の調和平均を取得するものである。
図３０は、本形態のセキュリティシステム５００の全体構成を例示した図であり、図３１は、本形態のセキュリティ方法を説明するためのフローチャートである。
【００９２】
以下、これらの図を用いて、この形態の構成及び処理の説明を行う。なお、依頼装置５１１（「第２のセキュリティ装置」に相当）、代理暗号装置５２０（「第１のセキュリティ装置」に相当）、代理復号装置５３０（「第３のセキュリティ装置」に相当）が行う暗号処理や復号処理及び機能構成は、上述の実施の形態で説明したものと本質的に同様である。よって、本形態では、依頼装置５１１、代理暗号装置５２０、代理復号装置５３０の機能構成、処理の詳細については説明を省略する。
【００９３】
今、依頼装置５１１がＶ個（複数）あり、それぞれが秘密値（「提供値」に相当）ｍｉ(i=1,…,V)を保有しているものとする。
このときｍｉの調和平均Ｈは、
【数３８】
2005084568.tif 000030
が格納されているものとする。
【００９４】
以下、本形態における処理を説明する。
＜ステップＳ１４０＞
まず各依頼装置５１１は、ネットワーク５４０を通じ、秘密値ｍｉを代理暗号装置５２０に送信（出力）する。
＜ステップＳ１４１＞
代理暗号装置５２０において、各依頼装置５１１から送信された秘密値ｍｉを受信する（入力を受け付ける）。
＜ステップＳ１４２＞
次に代理暗号装置５２０は、受信した各秘密値ｍｉを暗号化対象として特定し、例えば、第１の実施の形態と同様な方法により、各秘密値ｍｉに対応する複数の暗号文Ci=fm,r(X) mod ZN[X]を算出する。なお、暗号処理の手順については既に説明しているものと同様であるため、説明を省略する。
【００９５】
＜ステップＳ１４３＞
算出された全ての暗号文Ｃｉは、ネットワーク５４０を通じ、各依頼装置５１１に返信（出力）される。
＜ステップＳ１４４＞
各依頼装置５１１は、全ての暗号文Ｃｉを受信し（入力を受け付け）、全暗号文Ｃｉを共有する。その後、各依頼装置５１１は、それぞれのメモリに格納されている上述の式（１３）（１４）で示される関数を抽出し、これらに暗号文Ｃｉを代入する。即ち、
【数３９】
2005084568.tif 000031
を計算する。
＜ステップＳ１４５＞
この算出結果M(C1,…,CV)及びM’(C1,…,CV)（「代入値」に相当）は、ネットワーク５４０を通じ、代理復号装置５３０に送信（出力）される。
【００９６】
＜ステップＳ１４６＞
代理復号装置５３０は、この算出結果M(C1,…,CV)及びM’(C1,…,CV)を受信し（入力を受け付け）、例えば、第１の実施の形態と同様な方法により、算出結果M(C1,…,CV)及びM’(C1,…,CV)を復号し（秘密鍵ｒを抽出し、算出結果M(C1,…,CV)及びM’(C1,…,CV)にｒ-1を代入し）、調和平均を特定する値である平文M(m1,…,mV) mod N及びM’(m1,…,mV) mod Nを算出する。なお、復号処理の手順については既に説明しているものと同様であるため、説明を省略する。
＜ステップＳ１４７＞
代理復号装置５３０は、平文M(m1,…,mV) mod N及びM’(m1,…,mV) mod Nを、ネットワーク５４０を通じ、依頼装置５１１に返信（出力）する。
【００９７】
＜ステップＳ１４８＞
依頼装置５１１において、平文M(m1,…,mV) mod N及びM’(m1,…,mV) mod Nを受信し（入力を受け付け）、最終的にVM(m1,…,mV)/M’(m1,…,mV)=Hを計算することで調和平均を
得ることができる。
なお、この例では依頼装置５１１が、秘密値ｍｉをそのまま代理暗号装置５２０に送ることとしたが、例えば第１の実施の形態と同様な方法により、依頼装置５１１が、秘密値ｍｉを暗号化し、その暗号文を代理暗号装置５２０に送信することとしてもよい。これにより、依頼装置５１１は、代理暗号装置５２０に対しても秘密値ｍｉを秘匿できる。
【００９８】
〔第７の実施の形態〕
次に、本発明における第７の実施の形態について説明する。
この形態は、関数の処理を秘匿とするものである。
図３２は、この形態におけるセキュリティシステム６００の全体構成を例示した図であり、図３３は、公知のコンピュータに所定のプログラムを実行させることにより構成される暗号装置６１０（「第１のセキュリティ装置」に相当）の機能構成を、図３４は多項式演算装置６２０（「第２のセキュリティ装置」に相当）の機能構成を、それぞれ例示した図である。また、図３５は、この形態におけるセキュリティ方法を説明するためのフローチャートである。なお、暗号装置６１０における暗号処理や、復号装置６３０（「第３のセキュリティ装置」に相当）における復号処理は、第１の実施の形態等で説明したものと同様であるため、ここではその詳細を省略する。
【００９９】
今g(x,y)=axy+bx+cy+dを、０又は１を入力としたとき０又は１を返すような関数とする。このとき例えば(a,b,c,d)=(1,0,0,0)であれば、g(x,y)はANDゲートを表す関数であり、(1,-1,-1,1)、(-2,1,1,0)であれば、それぞれNORゲート、XORゲートを表す関数である。即ち、本形態の暗号アルゴリズムを用いてg(x,y)の各項の係数を暗号化することで、関数の処理を秘匿とすることができる。
ここでは具体的に関数
【数４０】
2005084568.tif 000032
を知ること無しに、関数gの処理を実行する方法について説明する。
【０１００】
暗号装置６１０は以下の処理を行う。
＜ステップＳ１５０＞
論理ゲート入力部６１１において、上述の式（１５）の入力（「論理ゲートを特定する情報」の入力）を受け付ける。
＜ステップＳ１５１＞
まず、暗号化部６１２において、論理ゲート入力部６１１から、論理ゲート（x1∩x2）を特定する情報を受け取る。次に、この論理ゲートを多項式表現した場合の各係数を暗号化対象として特定し、例えば第１の実施の形態と同様な方法により、これら各係数の暗号文f1,r(X)、f0,r(X)、f0,r(X)、f0,r(X)を算出する。そして、これら各暗号文を係数とした多項式関数x5=g1(X,x1,x2)=f1,r(X)x1x2+f0,r(X)x1+f0,r(X)x2+f0,r(X) mod ZN[X,x1,x2]を生成する。
【０１０１】
＜ステップＳ１５２＞
続いて、暗号化部６１２において、論理ゲート入力部６１１から、論理ゲート
【数４１】
2005084568.tif 000033
を特定する情報を受け取る。次に、この論理ゲートを多項式表現した場合の各係数を暗号化対象として特定し、例えば第１の実施の形態と同様な方法により、これら各係数の暗号文f2,r(X)、f-1,r(X)、f-1,r(X)、f1,r(X)を算出する。そして、これら各暗号文を係数とした多項式関数x6=g2(X,x3,x4)=f2,r(X)x3x4+f-1,r(X)x3+f-1,r(X)x4+f1,r(X) mod ZN[X,
x3,x4]を生成する。
【０１０２】
＜ステップＳ１５３＞
さらに、暗号化部６１４において、論理ゲート入力部６１１から論理ゲート∩を特定する情報を受け取り、暗号化部６１２、６１３から、それぞれ多項式関数x5,x6を受け取る。次に、論理ゲートx5∩x6を多項式表現した場合の各係数を暗号化対象として特定し、例えば第１の実施の形態と同様な方法により、これら各係数の暗号文f-1,r(X)、f1,r(X)、f1,r(X)、f0,r(X)を算出する。そして、これら各暗号文を係数とした多項式関数g3(X,x5,x6)=f-1,r(X)x5x6+f1,r(X)x5+f1,r(X)x6+f0,r(X) mod ZN[X,x5,x6]を生成する。
【０１０３】
なお上述のfα,β(x)は、第１の実施の形態同様、本発明の暗号アルゴリズムにより、平文αを秘密鍵βで暗号処理した暗号文である。また、この例では１２個の暗号文が生成・公開されるため、安全性を考慮し、パラメータｄをd=12+1=13としておく。また、暗号装置６１０では、例えばf0,r(x)が複数生成されているが、同じ平文（この場合平文は０）であっても暗号文は確率的であり一般に異なる（上述の式（１）参照。加算項の取り方によって暗号文が異なるため。）。
【０１０４】
＜ステップＳ１５４＞
暗号化部６１２、６１３、６１４で算出された多項式関数g1(X,x1,x2),g2(X,x3,x4),g3(X,x5,x6)は、例えばその処理コード（多項式関数の演算プログラム）と共に、それぞれ通信部６１５及びネットワーク６４０を通じ、多項式演算装置６２０に送信（出力）される。
【０１０５】
次に、多項式演算装置６２０は以下の処理を行う。なお、この例では、関数g(x1,x2,x3,x4)への代入値を(x1,x2,x3,x4)=(0,1,1,1)とする場合を例に採って説明する。
＜ステップＳ１５５＞
通信部６２１において、多項式関数g1(X,x1,x2),g2(X,x3,x4),g3(X,x5,x6)、及びその処理コードを受信する（入力を受け付ける）。
＜ステップＳ１５６＞
代入値入力部６２２において、代入値(x1,x2,x3,x4)=(0,1,1,1)の入力を受け付ける。
【０１０６】
＜ステップＳ１５７＞
まず、受け取った処理コードに従い、代入演算部６２３において、通信部６２１から多項式関数g1(X,x1,x2)を受け取り、代入値入力部６２２から代入値(x1,x2)=(0,1)を受け取り、G1=g1(X,0,1)=f0,r(X)+f0,r(X) mod ZN[X]を計算する（多項式関数g1(X,x1,x2)の演算）。
＜ステップＳ１５８＞
次に、代入演算部６２４において、通信部６２１から多項式関数g2(X,x3,x4)を受け取り、代入値入力部６２２から代入値(x3,x4)=(1,1)を受け取り、G2=g2(X,1,1)=f2,r(X)+f-1,r(X)+f-1,r(X)+f1,r(X) mod ZN[X]を計算する（多項式関数g2(X,x3,x4)の演算）。
【０１０７】
＜ステップＳ１５９＞
続いて、代入演算部６２５において、通信部６２１から多項式関数g3(X,x5,x6)を受け取り、代入演算部６２３、６２４から、それぞれ演算結果G1及びG2を受け取り、G3(X)=g3(X,G1,G2)=f-1,r(X)G1G2+f1,r(X)G1+f1,r(X)G2+f0,r(X) mod ZN[X]を計算する（多項式関数g3(X,x5,x6)の演算）。
＜ステップＳ１６０＞
算出された演算結果Ｇ３は、通信部６２１及びネットワーク６４０を通じ、復号装置６３０に送信（出力）される。なお、この演算結果G3(X)は、g(0,1,1,1)を秘密鍵ｒで暗号処理した３９次多項式からなる暗号文となっている。
【０１０８】
次に復号装置６３０は以下の処理を行う。
＜ステップＳ１６１＞
演算結果G3(X)を受信する（入力を受け付ける）。
＜ステップＳ１６２＞
入力された演算結果G3(X)に、例えば第１の実施の形態と同様な手順により、秘密鍵ｒの逆数ｒ-1を代入する。即ち、秘密鍵ｒを用いてG3(X)を復号する。これにより、g(0,1,1
,1)を得ることができる。
なお、本実施の形態で示した方法の応用として、例えば、暗号装置６１０において、関数ｇの実行結果の一部に意図的な値が含まれるよう操作し、復号装置６３０が、復号結果に対してその意図的な値が含まれているかどうかチェックすることで、多項式演算装置６２０による改ざんを防止することができる。
【０１０９】
〔第８の実施の形態〕
この形態は、暗号処理を行う代理暗号装置の処理正当性を検証するものである。なお、ここでの「処理正当性の検証」とは、適切な秘密鍵で処理を行っている旨の検証を意味する。
図３６は、本形態のセキュリティシステム７００の全体構成を例示した図である。また、図３７の（ａ）は、公知のコンピュータに所定のプログラムを実行させることにより実現される復号装置７１０（「第２のセキュリティ装置」に相当）の機能構成を、（ｂ）は検証装置７４０の機能構成を、それぞれ例示した図である。また、図３８は、この形態のセキュリティ方法を説明するためのフローチャートである。なお、暗号装置７３０（「第１のセキュリティ装置」に相当）の暗号処理や、復号装置７１０の復号処理は、例えば第１の実施の形態と同様であるため、その詳細は省略する。
【０１１０】
以下、これらの図を用い、本形態における機能構成及び処理について説明を行う。
まず復号装置７１０は以下の処理を行う。
＜ステップＳ１７０＞
素数生成部７１８において、相異なる大きな素数ｐ,ｑを生成し、合成数生成部７１９に送る。合成数生成部７１９は、合成数N=pq,N2=p2q2を算出し、合成数記憶部７２０に記憶させる。
＜ステップＳ１７１＞
初期値決定部７１３において、合成数記憶部７２０から合成数Ｎ,Ｎ2を抽出し、ＺＮ2の元で位数がＮとなる初期値ｇ0を決定する。なお、「ＺＮ2」の添え字はＮ２を意味している。
【０１１１】
＜ステップＳ１７２＞
次に、指数演算部７１４において、パラメータ記憶部７２２から自然数のパラメータｄを抽出し、秘密鍵記憶部７１２から秘密鍵ｒを抽出し、i=1,…,dについて、公開値giを
【数４２】
2005084568.tif 000034
に従って算出する。算出された公開値giは、公開値記憶部７１５に送られ、そこで記憶される。
＜ステップＳ１７３＞
公開値giを公開する。即ち、公開値記憶部７１５に記憶された公開値giを、通信部７１１及びネットワーク７５０を通じ、検証装置７４０に送信とする（出力する）。
【０１１２】
＜ステップＳ１７４＞
ゼロ知識証明部７１６において、乱数生成部７２１で生成された乱数を受け取り、合成数記憶部７２０から合成数Ｎ,Ｎ2を抽出し、公開値記憶部７１５から公開値giを抽出し、秘密鍵記憶部７１２から秘密鍵ｒを抽出し、通信部７１１及びネットワーク７５０を通じ、秘密鍵ｒを知っていることのゼロ知識証明を行う（ゼロ知識証明情報（レスポンス等）を出力する）。なお、ゼロ知識証明については、例えば、「D. Chaum and T. P. Pedersen, “Wallet databases with observers,” E. Brickell (Ed.), Advanes in Cryptology-CRYPTO ’92, LNCS 740, Springer-Verlag, pp. 89-105,1993.」に詳しいため、ここでは説明を省略する。
【０１１３】
次に暗号装置７３０は以下の処理を行う。
＜ステップＳ１７５＞
例えば、第１の形態と同様な手順により、暗号文fm,r(X)を計算する。
＜ステップＳ１７６＞
暗号文fm,r(X)を公開する。即ち、暗号文fm,r(X)を、ネットワーク７５０を通じ、復号装置７１０及び検証装置７４０に送信（出力）可能とする。
【０１１４】
次に復号装置７１０は以下の処理を行う。
＜ステップＳ１７７＞
通信部７１１において、暗号文fm,r(X)を受信する。
＜ステップＳ１７８＞
復号部７１７において、通信部７１１から暗号文fm,r(X)を受け取り、秘密鍵記憶部７１２から秘密鍵ｒを抽出し、第１の実施の形態と同様な手順によりfm,r(r-1)=mを計算する。
＜ステップＳ１７９＞
次に、このｍ（「暗号化対象」に相当）を、通信部７１１及びネットワーク７５０を通じて検証装置７４０に送信（出力）する。
【０１１５】
次に検証装置７４０は以下の処理を行う。
＜ステップＳ１８０＞
通信部７４１において、公開値gi(i=1,…,d)、暗号文fm,r(X)及び暗号化対象mを受信する（入力を受け付ける）。
＜ステップＳ１８１＞
次に、検証部７４２において、通信部７４１から公開値gi(i=1,…,d)、暗号文fm,r(X)及び暗号化対象mを受け取り、暗号文fm,r(X)の各係数をc0,…,cdとした場合における、
【数４３】
2005084568.tif 000035
が成立しているか否かを判断し、成立していれば処理が正当であると判断する。これにより、暗号装置７３０が正当な秘密鍵ｒ以外の秘密鍵で暗号処理を行った事実を検知することができる。即ち、適切な秘密鍵ｒが使用された場合、暗号文はfm,r(X)=adrdXd+ad-1rd-1Xd-1+…+a1rX+a0mod ZN[X]となり、(c0,c1,…,cd-1,cd)=(a0,a1r,…,ad-1rd-1,adrd)となる。そのため、上述の式（１７）の右辺は、
【数４４】
2005084568.tif 000036
となる。これは、秘密鍵ｒ以外の秘密鍵を用いて暗号化された場合には、一般に成立しない関係である。
【０１１６】
この形態の変形例として、図３７の（ａ）の機能構成を暗号装置７３０に設け、ステップＳ１７０〜１７４の処理を暗号装置７３０に行わせることとしてもよい。この場合、復号装置７１０が正当な秘密鍵ｒ以外の秘密鍵で復号処理を行った事実を検知することができる。
【０１１７】
なお、この発明は上述の各実施の形態に限定されるものではない。例えば、上述の各実
施の形態では、何れかの装置が素数を生成し、その積によって合成数を生成することとしたが、全装置が協力し、素因数が未知の合成数を生成することとしてもよい。この具体的手法については、例えば、「D. Boneh and M. Franklin, “Efficient generation of shared RSA keys,” B. S. Kaliski Jr. (Ed.), Advces in Cryptology-CRYPTO ’97, LNCS
1233, Springer-Verlag, pp. 425-439, 1997.」や、その改良である「I. Damgard and M. Koprowski, “Practical threshold RSA signatures without a trusted dealer,” B.
Pfitzmann (Ed.), Advanced in Cryptology-EUROCRYPT ’01, LNCS 2045, Springer-Verlag, pp. 152-165, 2001.」に詳しい。
【０１１８】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。さらに、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
さらに、上述の各実施の形態ではコンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１１９】
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述した本発明のセキュリティ装置をコンピュータによって実現する場合、その装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能が実現される。
【０１２０】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１２１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１２３】
なお、上記のプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）をも含むものとする。
【産業上の利用可能性】
【０１２４】
本発明の産業上の利用分野としては、上述の実施の形態で説明したものの他、例えば、
ＭＡ(Mobile Agent)の分野を挙げることができる。ＭＡとは、通常、あるホストから別のホストへ自律的に移動して情報取得、判断、実行等の各種処理を行うプログラムのことを指す。このＭＡの普及を妨げる最も深刻な問題として、ＭＡへの不正解析や実行結果の改ざんが挙げられる。しかし、本発明の技術により、ＭＡの内容や、処理結果を秘匿できるため、このＭＡのセキュリティ問題を効果的に解決することができる。
【図面の簡単な説明】
【０１２５】
【図１】第１の実施の形態のセキュリティシステムの全体構成を例示した図。
【図２】暗号装置の機能構成を例示した図。
【図３】（ａ）は外部機関装置の機能構成を、（ｂ）は復号装置の機能構成を、それぞれ例示した図。
【図４】第１の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図５】第２の実施の形態のセキュリティシステムの全体構成を例示した図。
【図６】依頼装置の機能構成を例示した図。
【図７】代理演算装置の機能構成を、それぞれ例示した図。
【図８】第２の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図９】第３の実施の形態のセキュリティシステムの全体構成を例示した図。
【図１０】依頼装置の機能構成を例示した図。
【図１１】代理暗号装置の機能構成を例示した図。
【図１２】第３の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図１３】第３の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図１４】第３の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図１５】第４の実施の形態のセキュリティシステムの全体構成を例示した図。
【図１６】依頼装置の機能構成を例示した図。
【図１７】代理復号装置の機能構成を例示した図。
【図１８】第４の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図１９】第４の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図２０】第５の実施の形態のセキュリティシステムの全体構成を例示した図。
【図２１】代理暗号装置の機能構成を例示した図。
【図２２】代理暗号装置の機能構成を例示した図。
【図２３】依頼装置の機能構成を例示した図。
【図２４】依頼装置の機能構成を例示した図。
【図２５】第５の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図２６】第５の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図２７】第５の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図２８】第５の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図２９】第５の実施の形態におけるセキュリティ方法の処理手順を説明するためのフローチャート。
【図３０】第６の実施の形態のセキュリティシステムの全体構成を例示した図。
【図３１】第６の実施の形態のセキュリティ方法を説明するためのフローチャート。
【図３２】第７の実施の形態におけるセキュリティシステムの全体構成を例示した図。
【図３３】暗号装置の機能構成を例示した図。
【図３４】多項式演算装置の機能構成を例示した図。
【図３５】第７の実施の形態におけるセキュリティ方法を説明するためのフローチャート。
【図３６】第８の実施の形態のセキュリティシステムの全体構成を例示した図。
【図３７】（ａ）は、復号装置の機能構成を、（ｂ）は検証装置の機能構成を、それぞれ例示した図。
【図３８】第８の実施の形態のセキュリティ方法を説明するためのフローチャート。
【符号の説明】
【０１２６】
１、１００〜７００  セキュリティシステム
１０、２１０  外部機関装置
２０、６１０、７３０  暗号装置
３０、６３０、７１０  復号装置
１１０、２２０、３１０、４５０、５１１  依頼装置
１３０  代理演算装置
２３０、３５０、４１０、４３０、５２０、５３０  代理暗号装置
３３０  代理復号装置
６２０  多項式演算装置
７４０  検証装置
【図１】
2005084568.tif 000047
【図２】
2005084568.tif 000048
【図３】
2005084568.tif 000049
【図４】
2005084568.tif 000050
【図５】
2005084568.tif 000051
【図６】
2005084568.tif 000052
【図７】
2005084568.tif 000053
【図８】
2005084568.tif 000054
【図９】
2005084568.tif 000055
【図１０】
2005084568.tif 000056
【図１１】
2005084568.tif 000057
【図１２】
2005084568.tif 000058
【図１３】
2005084568.tif 000059
【図１４】
2005084568.tif 000060
【図１５】
2005084568.tif 000061
【図１６】
2005084568.tif 000062
【図１７】
2005084568.tif 000063
【図１８】
2005084568.tif 000064
【図１９】
2005084568.tif 000065
【図２０】
2005084568.tif 000066
【図２１】
2005084568.tif 000067
【図２２】
2005084568.tif 000068
【図２３】
2005084568.tif 000069
【図２４】
2005084568.tif 000070
【図２５】
2005084568.tif 000071
【図２６】
2005084568.tif 000072
【図２７】
2005084568.tif 000073
【図２８】
2005084568.tif 000074
【図２９】
2005084568.tif 000075
【図３０】
2005084568.tif 000076
【図３１】
2005084568.tif 000077
【図３２】
2005084568.tif 000078
【図３３】
2005084568.tif 000079
【図３４】
2005084568.tif 000080
【図３５】
2005084568.tif 000081
【図３６】
2005084568.tif 000082
【図３７】
2005084568.tif 000083
【図３８】
2005084568.tif 000084