(57)【要約】【課題】K個の秘密情報を集めるのではなく、真の秘密情報a0を計算せずに、復号文を取得することができる復号システムを提供することを目的とする。【解決手段】復号システムは、端末装置と、N個の代理計算装置ｎとを含む。代理計算装置ｎは、分散された秘密情報f(jn)が記憶される記憶部と、暗号文に対応する情報τと分散された秘密情報f(jn)とを用いて値f(jn)τを求める計算部と、を含む。端末装置は、暗号文に対応する情報τから値f(jn)τを求めるように代理計算装置ｎに対して依頼する依頼部と、k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、K個の値f(jk)τを用いて、復号文に対応する情報a0τを求める復号部と、を含む。【選択図】図１
2015022098.tif 000002
【特許請求の範囲】
【請求項１】
Nを２以上の整数とし、n=1,…,Nとし、端末装置と、N個の代理計算装置ｎとを含む復号システムであって、
Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、
前記代理計算装置ｎは、
前記分散された秘密情報f(jn)が記憶される記憶部と、
暗号文に対応する情報τと前記分散された秘密情報f(jn)とを用いて値f(jn)τを求める計算部と、を含み、
前記端末装置は、
前記暗号文に対応する情報τから値f(jn)τを求めるように前記代理計算装置ｎに対して依頼する依頼部と、
k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、K個の値f(jk)τを用いて、復号文に対応する情報a0τを求める復号部と、を含む、
復号システム。
【請求項２】
請求項１記載の復号システムであって、
さらに、前記N個の代理計算装置ｎを管理する鍵装置を含み、
前記端末装置は、
乱数rnによって前記暗号文との関係をかく乱させたかく乱情報τ(n)を、前記暗号文に対応する情報τとして生成するかく乱情報生成部と、
前記鍵装置を介して前記代理計算装置ｎから値f(jｎ)τ(n)を受け取り、前記乱数rnを用いて、前記値f(jｎ)τ(n)から値f(jｎ)Cを求める第二復号部と、をさらに含み、
前記依頼部は、前記鍵装置を介して、前記かく乱情報τ(n)から値f(jn)τ(n)を求めるように前記代理計算装置ｎに対して依頼し、
前記代理計算装置ｎの計算部は、
前記かく乱情報τ(n)と前記分散された秘密情報f(jn)とを用いて値f(jn)τ(n)を求める、
復号システム。
【請求項３】
Nを２以上の整数とし、n=1,…,Nとし、端末装置と、N個の代理計算装置ｎとを含む署名システムであって、
Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、
前記代理計算装置ｎは、
前記分散された秘密情報f(jn)が記憶される記憶部と、
平文に対応する情報τと前記分散された秘密情報f(jn)とを用いて値f(jn)τを求める計算部と、を含み、
前記端末装置は、
前記平文に対応する情報τから値f(jn)τを求めるように前記代理計算装置ｎに対して依頼する依頼部と、
k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、K個の値f(jk)τを用いて、電子署名に対応する情報a0τを求める署名生成部と、を含む、
署名システム。
【請求項４】
Nを２以上の整数とし、n=1,…,Nとし、N個の代理計算装置ｎに代理計算を依頼する端末装置であって、
Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、
前記暗号文に対応する情報τから値f(jn)τを求めるように前記代理計算装置ｎに対して依頼する依頼部と、
k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、K個の値f(jk)τを用いて、復号文に対応する情報a0τを求める復号部と、を含む、
端末装置。
【請求項５】
請求項４記載の端末装置であって、
乱数rnによって前記暗号文との関係をかく乱させたかく乱情報τ(n)を、前記暗号文に対応する情報τとして生成するかく乱情報生成部と、
鍵装置を介して前記代理計算装置ｎから値f(jｎ)τ(n)を受け取り、前記乱数rnを用いて、前記値f(jｎ)τ(n)から値f(jｎ)Cを求める第二復号部と、をさらに含み、
前記依頼部は、前記鍵装置を介して、前記かく乱情報τ(n)から値f(jn)τ(n)を求めるように前記代理計算装置ｎに対して依頼する、
端末装置。
【請求項６】
Nを２以上の整数とし、n=1,…,Nとし、N個の代理計算装置ｎに代理計算を依頼する端末装置であって、
Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、
前記平文に対応する情報τから値f(jn)τを求めるように前記代理計算装置ｎに対して依頼する依頼部と、
k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、K個の値f(jk)τを用いて、電子署名に対応する情報a0τを求める署名生成部と、を含む、
端末装置。
【請求項７】
Nを２以上の整数とし、n=1,…,Nとし、端末装置と、N個の代理計算装置ｎとを用いる復号方法であって、
Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、
前記端末装置が、前記暗号文に対応する情報τから値f(jn)τを求めるように前記代理計算装置ｎに対して依頼する依頼ステップと、
前記代理計算装置ｎが、予め記憶されている前記分散された秘密情報f(jn)と、暗号文に対応する情報τとを用いて値f(jn)τを求める計算ステップと、
k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、前記端末装置が、K個の値f(jk)τを用いて、復号文に対応する情報a0τを求める復号ステップと、を含む、
復号方法。
【請求項８】
請求項７記載の復号方法であって、
さらに、前記N個の代理計算装置ｎを管理する鍵装置を用い、
前記端末装置が、乱数rnによって前記暗号文との関係をかく乱させたかく乱情報τ(n)を、前記暗号文に対応する情報τとして生成するかく乱情報生成ステップと、
前記端末装置が、前記鍵装置を介して前記代理計算装置ｎから値f(jｎ)τ(n)を受け取り、前記乱数rnを用いて、前記値f(jｎ)τ(n)から値f(jｎ)Cを求める第二復号ステップと、をさらに含み、
前記依頼ステップにおいて、前記鍵装置を介して、前記かく乱情報τ(n)から値f(jn)τ(n)を求めるように前記代理計算装置ｎに対して依頼し、
前記計算ステップにおいて、前記かく乱情報τ(n)と前記分散された秘密情報f(jn)とを用いて値f(jn)τ(n)を求める、
復号方法。
【請求項９】
Nを２以上の整数とし、n=1,…,Nとし、端末装置と、N個の代理計算装置ｎとを含む署名方法であって、
Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、
前記端末装置が、平文に対応する情報τから値f(jn)τを求めるように前記代理計算装置ｎに対して依頼する依頼ステップと、
前記代理計算装置ｎが、予め記憶されている前記分散された秘密情報f(jn)と、平文に対応する情報τとを用いて値f(jn)τを求める計算ステップと、
k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、前記端末装置が、K個の値f(jk)τを用いて、電子署名に対応する情報a0τを求める署名生成ステップと、を含む、
署名方法。
【請求項１０】
請求項４から請求項６の何れかに記載された端末装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散法を用いた復号システム、その復号システムにおいて利用する端末装置、秘密分散法を用いた署名システム、その署名システムにおいて利用する端末装置、その方法、及びプログラムに関する。
【背景技術】
【０００２】
秘密分散法を用いた復号方法として、非特許文献１が従来技術として知られている。
【０００３】
Secret Sharing方式では、多項式
f(x)=aK-1xK-1+…+ a1x1+a0    (1)
を用いて、真の秘密情報a0を保存する代わりに、f(1),f(2),…,f(N)の値を分散された秘密情報として、複数の装置に保存する。
【０００４】
(K,N)しきい値秘密分散法では、N個の分散された秘密情報f(n)のうちの任意の相異なるK個の秘密情報f(nk)が集まると、真の秘密情報a0を求めることができる。一方、任意の相異なるK-1個の秘密情報f(nk')では、真の秘密情報a0に関して全く情報が得られない。ここで、Nは2以上の整数、Kは1以上N以下の整数、n=1,2,…,N、k=1,2,…,K、k'=1,2,…,K-1、nk及びnk'はそれぞれk及びk'に対応する1,2,…,Nの何れかの値である。
【０００５】
複数の装置で分散された秘密情報f(n)を保存することで、K-1個まで分散された秘密情報f(n)を盗まれても真の秘密情報a0が漏れず、また、N-K個まで分散された秘密情報f(n)を紛失したり破壊されても真の秘密情報a0を復元できる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】岡本龍明、山本博資著、「現代暗号」、1997年、産業図書、pp209〜218.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術の場合、一度K個の秘密情報f(nk)を集めてしまうと、真の秘密情報a0を計算できてしまうため、真の秘密情報a0を利用した後に確実に消去する必要があり、消去を失敗すると情報漏洩する可能性がある。
【０００８】
本発明の第一の態様は、真の秘密情報a0を計算せずに、復号文を取得することができる復号システム、その復号システムにおいて利用する端末装置、その方法、及びプログラムを提供することを目的とする。
【０００９】
また、本発明の他の態様は、真の秘密情報a0を計算せずに、電子署名を生成することができる署名システム、その署名システムにおいて利用する端末装置、その方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、本発明の第一の態様によれば、復号システムは、Nを２以上の整数とし、n=1,…,Nとし、端末装置と、N個の代理計算装置ｎとを含む。Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、代理計算装置ｎは、分散された秘密情報f(jn)が記憶される記憶部と、暗号文に対応する情報τと分散された秘密情報f(jn)とを用いて値f(jn)τを求める計算部と、を含む。端末装置は、暗号文に対応する情報τから値f(jn)τを求めるように代理計算装置ｎに対して依頼する依頼部と、k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、K個の値f(jk)τを用いて、復号文に対応する情報a0τを求める復号部と、を含む。
【００１１】
上記の課題を解決するために、本発明の他の態様によれば、署名システムは、Nを２以上の整数とし、n=1,…,Nとし、端末装置と、N個の代理計算装置ｎとを含む。Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とし、代理計算装置ｎは、分散された秘密情報f(jn)が記憶される記憶部と、平文に対応する情報τと分散された秘密情報f(jn)とを用いて値f(jn)τを求める計算部と、を含む。端末装置は、平文に対応する情報τから値f(jn)τを求めるように代理計算装置ｎに対して依頼する依頼部と、k=1,2,…,K、jkをk毎に異なるj1,j2,…,jNの何れかの値とし、K個の値f(jk)τを用いて、電子署名に対応する情報a0τを求める署名生成部と、を含む。
【発明の効果】
【００１２】
本発明によれば、真の秘密情報a0による情報漏洩を防止することができる。
【図面の簡単な説明】
【００１３】
【図１】第一実施形態に係る復号システムの構成例を示す図。
【図２】第一実施形態に係る復号システム１の処理フローを示す図。
【図３】第一実施形態に係る端末装置の機能ブロック図。
【図４】第一実施形態に係る代理計算装置の機能ブロック図
【図５】第二実施形態に係る復号システムの構成例を示す図。
【図６】第三実施形態に係る復号システムの構成例を示す図。
【図７】第三実施形態に係る復号システム１の処理フローを示す図。
【図８】第三実施形態に係る端末装置の機能ブロック図。
【図９】第四実施形態に係る電子署名システムの構成例を示す図。
【図１０】第四実施形態に係る電子署名システムの処理フローを示す図。
【図１１】第四実施形態に係る端末装置の機能ブロック図。
【発明を実施するための形態】
【００１４】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。
【００１５】
＜第一実施形態＞
図１及び図２を用いて第一実施形態に係る復号システム１を説明する。図１は第一実施形態に係る復号システム１の構成例を、図２はその処理フローを示す。
【００１６】
復号システム１は、端末装置１１と、N個の代理計算装置１２−ｎとを含む。これらはネットワークを通じて通信可能に構成されている。ただし、Nは２以上の整数であり、n=1,…,Nである。
【００１７】
ここで、Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とする。平文Mの暗号文Cに対応する情報τと真の秘密情報a0とを用いて復号文M'に対応する情報a0τを求めることができ、復号文M'に対応する情報a0τから復号文M'を得ることができるものとする。ここでは、群で定義された演算を加法的に表現する。すなわちGを巡回群とし、α∈Gに対する「αb」は、群Gで定義された演算をαに対してb回作用させることを意味する。
【００１８】
図３に示すように、端末装置１１は、依頼部１１１と復号部１１２と記憶部１１３とを含む。代理計算装置１２−ｎは、安全に管理される装置であり、図４に示すように、記憶部１２２と計算部１２１とを含む。図３及び図４は、それぞれ端末装置１１及び代理計算装置１２−ｎの機能ブロック図を示す。
【００１９】
端末装置１１及び代理計算装置１２−ｎは、ルータ装置、サーバ装置、携帯電話、ＩＣカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたＣＰＵ(central processing unit)やＲＡＭ(random-access memory)を備えた公知又は専用のコンピュータなどである。
【００２０】
＜事前処理＞
例えば、図示しない分配装置(公開鍵サーバ)は、公開鍵yと、公開鍵yに対応する秘密鍵dを生成し、公開鍵yを公開する。公開鍵暗号方式としては、ElGamal暗号方式、楕円ElGamal暗号方式、RSA暗号方式、Pailler暗号方式などが考えられる。また、分配装置は、秘密鍵dを真の秘密情報a0とし、a0を定数項とするランダムな（K-1）次の多項式を選び、
f(x)=a(K-1)x(K-1)+…+a1x+a0    (1)
とし、代理計算装置１２−ｎに分散された秘密情報f(jn)を配る。さらに、分配装置は、分散された秘密情報f(jn)を配った後に、真の秘密情報a0を削除してもよい。
【００２１】
代理計算装置１２−ｎは、分散された秘密情報f(jn)を受け取り、記憶部１２２に分散された秘密情報f(jn)を格納しておく。
【００２２】
図示しない端末装置は、公開鍵yを用いて、対応する公開鍵暗号方式により平文Mを暗号化し、暗号文C=Enc(y,M)を生成し、暗号文Cを端末装置１１に送信する。
【００２３】
端末装置１１は、暗号文Cを受け取り、記憶部１１３に暗号文Cを格納しておく。
【００２４】
＜復号処理＞
端末装置１１の依頼部１１１は、暗号文Cに対応する情報τから値f(jn)τを求めるように代理計算装置１２−ｎに対して依頼する（ｓ１）。例えば、ネットワークを介して暗号文に対応する情報τと計算依頼情報(値f(jn)τを求めるように記述された情報)とをN個の代理計算装置１２−ｎに送信する。なお、必ずしもN個の代理計算装置１２−ｎに送信する必要はなく、少なくともK個の代理計算装置１２−ｎに送信すればよい。
【００２５】
代理計算装置１２−ｎの計算部１２１は、暗号文Cに対応する情報τを受け取ると、記憶部１２２から分散された秘密情報f(jn)を読み込み、暗号文Cに対応する情報τと分散された秘密情報f(jn)とを用いて値f(jn)τを求め（ｓ２）、端末装置１１に送信する。
【００２６】
端末装置１１の復号部１１２は、K個の値f(jk)τを受け取ると、K個の値f(jk)τを用いて、復号文M'に対応する情報a0τを求める（ｓ３）。ここで、k=1,2,…,K、jkはk毎に異なるj1,j2,…,jnの何れかの値である。例えば、K個の値f(jk)τをそれぞれ定数倍し、加算することで、復号文M'に対応する情報a0τを求める。さらに、復号部１１２は、復号文M'に対応する情報a0τから復号文M'を取得し、ディスプレイ等の出力部から出力する。なお、N-K個まで分散された秘密情報f(n)を紛失したり破壊されても復号文M'に対応する情報a0τを求めることができる。以下、K=2の場合、K=3の場合の例を示す。なお、説明を分かり易くするために、この例では、jn=jk=nとする。
【００２７】
＜K=2の場合＞
例えば、K=2、f(x)=a1x+a0の場合、a0=2f(1)+f(2)の関係が成り立つため(式(1)参照)、端末装置１１の依頼部１１１は、代理計算装置１２−１、１２−２にそれぞれf(1)τ、f(2)τの計算を依頼する。端末装置１１の復号部１１２は、f(1)τ、f(2)τを受け取ると、次式により、復号文M'に対応する情報a0τを求める。
a0τ=2f(1)τ+f(2)τ
【００２８】
このような構成とすることで、離散対数問題が困難な群であれば、端末装置１１は、復号文M'に対応する情報a0τを知った後でも、真の秘密情報a0を知ることはできない。そのため、端末装置１１は、暗号文Cと無関係な暗号文C'に対応する情報τ'から復号文M'に対応する情報a0τ'を求めることはできない。この点が、従来の秘密分散法とは異なる。
【００２９】
＜K=3の場合＞
また、例えば、K=3、f(x)=a2x2+a1x+a0の場合、a0=f(3)-2f(2)+f(1)の関係が成り立つため(式(1)参照)、端末装置１１の依頼部１１１は、代理計算装置１２−１、１２−２、１２−３にそれぞれf(1)τ、f(2)τ、f(3)τの計算を依頼する。端末装置１１の復号部１１２は、f(1)τ、f(2)τ、f(3)τを受け取ると、次式により、復号文M'に対応する情報a0τを求める。
a0τ=f(3)τ-2f(2)τ+f(1)τ
【００３０】
以下、RSA暗号、ElGamal暗号、楕円ElGamal暗号を用いた場合の公開鍵暗号方式についてそれぞれ説明する。
【００３１】
(RSA暗号を用いた公開鍵暗号方式について)
RSA暗号を用いた公開鍵暗号方式の一例について説明する。まず、tをセキュリティパラメータとする。p,q(p≠q)をt/2ビットの素数とし、m=pqとする。eをφ(m)未満の正の整数で、φ(m)と互いに素な数とし、d(=a0)を、φ(m)を法としたeの逆数（de≡1(modφ(m))）とする。ただし、ここでφ(m)はmのオイラー関数で、この場合は(p-1)(q-1)に等しい。0以上m未満の整数の集合をZmで表す。Mを平文空間Zmの元とする。
【００３２】
RSA暗号を用いた公開鍵暗号方式では、公開鍵y=(e,m)とする。
【００３３】
図示しない端末装置は、公開鍵y=(e,m)を用いて、平文Mを次式により暗号化する。
C=Me mod m
ここでは、群で定義された演算を乗法的に表現する。すなわちGを群とし、α∈Gに対する「αb」は、群Gで定義された演算をαに対してb回作用させることを意味する。暗号文Cに対応する情報τを暗号文Cそのもの(τ=C)とし、復号文M'に対応する情報a0τをCa_0とし、復号文M'を次式により表す。
M'=Ca_0 mod m
なお、上付き添え字a_0は、a0を意味する。
【００３４】
端末装置１１は、暗号文Cと計算依頼情報(値Cf(n)を求めるように記述された情報)とをN個の代理計算装置１２−ｎに送信する。
【００３５】
代理計算装置１２−ｎは、値Cf(n)を求め、端末装置１１に送信する。
【００３６】
端末装置１１は、公開鍵y=(m,e)とK個の値Cf(k)とを用いて、復号文M'=Cf(0) mod mを求める。
【００３７】
例えば、K=2、f(x)=a1x+a0の場合、a0=2f(1)+f(2)の関係が成り立つため、Cf(1)、Cf(2)を用いて、次式により復号文M'=Ca_0mod mを求めることができる。
M'=Ca_0 mod m =C2f(1)+f(2)mod m
【００３８】
(ElGamal暗号を用いた公開鍵暗号方式について)
ElGamalを用いた公開鍵暗号方式の一例について説明する。tをセキュリティパラメータとする。巡回群Gで、位数qが素数であり、かつqのビット数がtであるものを選ぶ。Gの生成元gを選ぶ。x(=a0)を{0,…,q-1}からランダムに選ぶ。h=gxとする。平文空間はGであり、MはGの元である。暗号文空間はG2であり、(C1,C2)∈G×Gである。
【００３９】
ElGamal暗号を用いた公開鍵暗号方式では、公開鍵y=(G,q,g,h=ga_0)とする。
【００４０】
図示しない端末装置は、公開鍵y=(G,q,g,h=ga_0)を用いて、平文Mを次式により暗号化する。
C=(C1,C2)
C1=gr
C2=Mhr
ただし、rは図示しない端末装置によって生成される乱数であり、0<r<qからランダムに選ばれる整数である。ここでは、群で定義された演算を乗法的に表現する。暗号文Cに対応する情報τを暗号文Cの一部であるC1とし、復号文M'に対応する情報a0τをC1a_0とし、復号文M'を次式により表す。
M'=C2/C1a_0
【００４１】
端末装置１１は、暗号文の一部C1と計算依頼情報(値C1f(n)を求めるように記述された情報)とをN個の代理計算装置１２−ｎに送信する。
【００４２】
代理計算装置１２−ｎは、値C1f(n)を求め、端末装置１１に送信する。
【００４３】
端末装置１１は、公開鍵y=(G,q,g,h=ga_0)と暗号文Cの一部C2とK個の値C1f(k)とを用いて、復号文M'=C2/C1a_0を求める。
【００４４】
例えば、K=2、f(x)=a1x+a0の場合、a0=2f(1)+f(2)の関係が成り立つため、C1f(1)、C1f(2)を用いて、次式により復号文M'=C2/C1a_0を求めることができる。
M'=C2/C1a_0=C2/C12f(1)+f(2)
【００４５】
(楕円ElGamal暗号を用いた公開鍵暗号方式について)
Eを楕円曲線パラメータ、J及びHを楕円曲線E上の点、qを楕円曲線E上の点Jの位数とし、楕円ElGamal暗号を用いた公開鍵暗号方式では、公開鍵y=(E,q,J,H=a0J)とする。
【００４６】
図示しない端末装置は、公開鍵y=(J,H=a0J)を用いて、平文Mを次式により暗号化する。
C=(C1,C2)
C1=rJ
C2=M+rH
ただし、rは図示しない端末装置によって生成される乱数であり、0<r<qからランダムに選ばれる整数である。ここでは、群で定義された演算を加法的に表現する。暗号文Cに対応する情報τを暗号文Cの一部であるC1とし、復号文M'に対応する情報をa0C1とし、復号文M'を次式により表す。
M'=C2-a0C1
【００４７】
端末装置１１は、暗号文の一部C1と計算依頼情報(値f(n)C1を求めるように記述された情報)とをN個の代理計算装置１２−ｎに送信する。
【００４８】
代理計算装置１２−ｎは、値f(n)C1を求め、端末装置１１に送信する。
【００４９】
端末装置１１は、公開鍵y=(E,q,J,H=a0J)と暗号文の一部C2とK個の値f(k)C1とを用いて、復号文M'=C2-a0C1を求める。
【００５０】
例えば、K=2、f(x)=a1x+a0の場合、a0=2f(1)+f(2)の関係が成り立つため、C1f(1)、C1f(2)を用いて、次式により復号文M'=C2-C1a0を求めることができる。
M'=C2-a0C1=C2-(2f(1)+f(2))C1
【００５１】
＜効果＞
このような構成により、真の秘密情報a0を計算せずに、復号文M'に対応する情報a0τを求めることができ、復号文M'に対応する情報a0τから復号文M'を取得することができる。端末装置１１では、真の秘密情報a0を知ることはできないため、真の秘密情報a0の消去を失敗するということがなく、真の秘密情報a0の消去失敗による情報漏洩を防止することができる。また、秘密情報f(n)を配った後に、秘密鍵d=a0を削除しても、暗号文Cを復号することができ、秘密鍵の管理負担を軽減することができる。
【００５２】
＜変形例＞
本実施形態では、端末装置１１の依頼部１１１が、計算依頼情報を代理計算装置１２−ｎに送信する構成となっているが、計算依頼情報を送信せずとも代理計算装置１２−ｎが暗号文Cを受け取ると、値f(jn)τを計算し、この値を返す構成としてもよい。
【００５３】
図示しない分配装置は、N個の代理計算装置１２−ｎとは別に設けてもよいし、N個の代理計算装置１２−ｎの内の何れかにその機能を持たせてもよい。
【００５４】
＜第二実施形態＞
第一実施形態と異なる部分を中心に説明する。図５を用いて第二実施形態に係る復号システム２を説明する。図５は第二実施形態に係る復号システム２の構成例を示す。
【００５５】
復号システム２は、端末装置１１と、N個の代理計算装置１２−ｎと、鍵装置２３とを含む。これらはネットワークを通じて通信可能に構成されている。鍵装置２３は、N個の代理計算装置１２−ｎを管理する。例えば、鍵装置２３は、N個の代理計算装置１２−ｎのアドレスや、N個の代理計算装置１２−ｎの変更、追加、削除等を行い、端末装置１１とN個の代理計算装置１２−ｎとは、鍵装置２３を介して情報を送受信する。また、鍵装置２３において、アクセス制御を行う構成としてもよい。
【００５６】
第一実施形態では、端末装置１１がN個の代理計算装置１２−ｎに対して計算依頼を直接行っていたが、第二実施形態では、鍵装置２３を介して計算依頼を行う。このとき、鍵装置２３に暗号文Cを渡すと、復号文M'を鍵装置２３に知られてしまう。そこで、本実施形態では、鍵装置２３に暗号文Cそのものではなく暗号文Cの一部C1を渡し、鍵装置２３を介して値f(jn)C1を求めるように代理計算装置１２−ｎに対して依頼する。本実施形態では、暗号文Cに対応する情報τは暗号文Cの一部C1である。なお、暗号文Cの一部C1は、暗号文Cに対応する情報であり、かつ、それのみから復号文M'を復号できない情報である。なお、暗号文Cを復号するためには、暗号文Cの一部C1と他の部分とを必要とする。例えば、暗号文Cの一部C1として第一実施形態のElGamal暗号や楕円ElGamal暗号のC1を用いることができる。
【００５７】
＜事前処理＞
例えば、鍵装置２３は、公開鍵yと、公開鍵yに対応する秘密鍵dを生成し、公開鍵yを公開する。公開鍵暗号方式としては、ElGamal暗号方式、楕円ElGamal暗号方式などが考えられる。また、鍵装置２３は、秘密鍵dを真の秘密情報a0とし、a0を定数項とするランダムな（K-1）次の多項式を選び、
f(x)=a(K-1)x(K-1)+…+a1x+a0
とし、代理計算装置１２−ｎに分散された秘密情報f(jn)を配る。さらに、鍵装置２３は、分散された秘密情報f(jn)を配った後に、真の秘密情報a0を削除してもよい。
【００５８】
代理計算装置１２−ｎは、分散された秘密情報f(jn)を受け取り、記憶部１２２に分散された秘密情報f(jn)を格納しておく。
【００５９】
図示しない端末装置は、公開鍵yを用いて、対応する公開鍵暗号方式により平文Mを暗号化し、暗号文C=Enc(y,M)を生成し、暗号文Cを端末装置１１に送信する。
【００６０】
例えば、ElGamal暗号を用いた公開鍵暗号方式では、公開鍵y=(g,h=ga_0)とし、暗号文Cを
C=(C1,C2)
C1=gr
C2=Mhr
とする。また、楕円ElGamal暗号を用いた公開鍵暗号方式では、公開鍵y=(G,H=a0G)とし、暗号文Cを
C=(C1,C2)
C1=rG
C2=M+rH
とする。
【００６１】
端末装置１１は、暗号文Cを受け取り、記憶部１１３に暗号文Cを格納しておく。例えば、暗号文CはC1とC2とからなり、C=(C1,C2)と表される。
【００６２】
＜復号処理＞
本実施形態では、暗号文Cに対応する情報τとして、暗号文Cの一部C1を用い、端末装置１１の依頼部１１１は、鍵装置２３を介して、暗号文Cの一部C1から値f(jn)C1を求めるようにN個の代理計算装置１２−ｎに対して依頼する（ｓ１）。
【００６３】
代理計算装置１２−ｎの計算部１２１は、暗号文Cの一部C1を受け取ると、記憶部１２２から分散された秘密情報f(jn)を読み込み、暗号文Cの一部C1と分散された秘密情報f(jn)とを用いて値f(jn)C1を求め（ｓ２）、鍵装置２３に送信する。
【００６４】
端末装置１１の復号部１１２は、鍵装置２３を介して代理計算装置１２−ｎから値f(jn)C1を受け取り、K個の値f(jk)C1から復号文M'に対応する情報a0C1を求める（ｓ３）。なお、鍵装置２３において、K個の値f(jk)C1から復号文M'に対応する情報a0C1を求め、復号文M'に対応する情報a0C1を端末装置１１に送信する構成としてもよい。復号文M'に対応する情報a0C1から復号文M'を求める処理は、第一実施形態で説明した通りである。例えば、ElGamal暗号を用いた場合、M'=C2/C1a_0により復号文M'を求め、楕円ElGamal暗号を用いた場合、M'=C2-C1a0により復号文M'を求める。
【００６５】
＜効果＞
このような構成により、第一実施形態と同様の効果を得ることができる。さらに、鍵装置２３で、N個の代理計算装置１２−ｎを管理しているため、端末装置１１は、個別にN個の代理計算装置１２−ｎに計算を依頼する必要がなく、端末装置１１の処理を軽減することができる。暗号文Cの一部C1のみから、復号文M'を復号できないため、鍵装置２３に復号文M'を秘密にしたまま処理を中継させることができる。
【００６６】
＜第三実施形態＞
第二実施形態と異なる部分を中心に説明する。図６及び７を用いて第三実施形態に係る復号システム３を説明する。図６は第三実施形態に係る復号システム３の構成例を、図７はその処理フローを示す。
【００６７】
本実施形態では、鍵装置２３に暗号文Cの一部C1ではなく、乱数rnによって暗号文Cとの関係をかく乱させたかく乱情報τ(n)を渡し、鍵装置２３を介して値f(jn)τ(n)を求めるように代理計算装置１２−ｎに対して依頼する。鍵装置２３がランダム帰着可能な暗号文(かく乱情報)の復号を行う点が第二実施形態と相違する。ランダム帰着可能な暗号化方式は、ランダム化アルゴリズムと復元アルゴリズムとからなる。ランダム化アルゴリズムは、暗号文と乱数とを用いて別の暗号文を出力する確率アルゴリズムで、出力は入力によらずランダムに選ばれた暗号文と識別できない確率分布に従う。復元アルゴリズムはランダム化アルゴリズムの出力である暗号文を復号した結果とランダム化アルゴリズムで用いられた乱数を入力として、もとの暗号文を復号した平文を出力する。このような暗号方式は、例えばElGamal暗号、楕円ElGamal 暗号、RSA暗号、Pailler暗号などの準同型暗号方式を用いて容易に構成できる。第三実施形態は、準同型暗号方式を用いてランダム自己帰着可能な暗号方式を構成した例を示しながら記述する。本実施形態では、暗号文Cに対応する情報τは乱数rnによって暗号文Cとの関係をかく乱させたかく乱情報τ(n)である。なお、かく乱情報τ(n)は、暗号文Cに対応する情報であり、かつ、乱数rnを知らなければ復号文M'を復号できない情報である。なお、乱数rnは、複数の乱数の集合であってもよい。
【００６８】
復号システム３は、端末装置３１と、N個の代理計算装置１２−ｎと、鍵装置２３とを含む。これらはネットワークを通じて通信可能に構成されている(図６参照)。例えば、N個の代理計算装置１２−ｎと、鍵装置２３とから鍵管理クラウドを構成し、クラウド鍵管理型暗号方式（参考文献１参照）を実現することができる。
（参考文献１）特開２０１２−１５１７５６号公報
【００６９】
図８に示すように、端末装置３１は、依頼部１１１と復号部１１２と記憶部１１３とかく乱情報生成部３１４と第二復号部３１５とを含む。図８は、端末装置３１の機能ブロック図を示す。
【００７０】
＜復号処理＞
端末装置３１のかく乱情報生成部３１４は、N個の乱数rnを生成し、暗号文Cを記憶部１１３から取り出し、乱数rnによって暗号文Cとの関係をかく乱させたかく乱情報τ(n)を生成し（ｓ３１）、依頼部１１１へ出力する。N個の乱数rnは記憶部１１３に記憶しておく。言い換えると、かく乱情報生成部３１４は、暗号方式のランダム自己帰着性から定義されるランダム化アルゴリズムに則り、暗号文Cと乱数rnに対応するかく乱情報τ(n)を生成する。例えば暗号文Cが準同型暗号方式の暗号文である場合、かく乱情報生成部３１４は、それと同じ準同型暗号方式に則って公開鍵yで乱数rnを暗号化して得られる暗号文(乱数暗号文)をEnc(y,rn)とし、Enc(y,rn)とCとの乗法によってかく乱情報τ(n)＝Enc(y,rn)・Cを生成する。
【００７１】
端末装置３１の依頼部１１１は、鍵装置２３を介して、かく乱情報τ(n)から値f(jn)τ(n)を求めるようにN個の代理計算装置１２−ｎに対して依頼する（ｓ１）。
【００７２】
代理計算装置１２−ｎの計算部１２１は、かく乱情報τ(n)を受け取ると、記憶部１２２から分散された秘密情報f(jn)を読み込み、前述の準同型暗号化方式に則って、かく乱情報τ(n)と分散された秘密情報f(jn)とを用いて値f(jn)τ(n)を求め（ｓ２）、鍵装置２３に送信する。
【００７３】
端末装置１１の第二復号部３１５は、鍵装置２３を介して代理計算装置１２−ｎから値f(jn)τ(n)を受け取り、乱数rnを記憶部１１３から取り出し、暗号方式のランダム自己帰着性から定義される復元アルゴリズムに則り、乱数rnを用いて、値f(jｎ)τ(n)から値f(jｎ)Cを求め（ｓ３２）、値f(jｎ)Cを復号部１１２に出力する。例えば前述したかく乱情報(n)＝Enc(y,rn)・Cである例の場合、第二復号部３１５は乱数rnの逆元rn−１を用い、f(jn)τ(n)と元rn−１との乗法f(jｎ)C=(rn−１)・f(jn)τ(n)によって値f(jｎ)Cを得ることができる。これは準同型暗号方式の暗号化関数および復号関数が準同型性を持つことに基づく。
【００７４】
端末装置１１の復号部１１２は、K個の値f(jk)Cから復号文M'に対応する情報a0Cを求め、情報a0Cから復号文M'を取得し、ディスプレイ等の出力部から出力する（ｓ３）。
【００７５】
＜効果＞
このような構成により、第二実施形態と同様の効果を得ることができる。さらに本実施形態では、鍵装置２３を経由するのは暗号文Cと乱数rnとに対応するかく乱情報τ(n)であり、暗号文Cそのものではない。鍵装置２３は値f(jn)τ(n)を得ることができても、鍵装置２３は乱数rnを知らないため値f(jn)τ(n)から値f(jｎ)Cを得ることはできない。これにより、鍵装置２３の管理者が仮にK個の値f(jk)τ(k)を取得したとしても暗号文Cの復号結果M'が知られることを防止できる。
【００７６】
なお、暗号文Cに対応する情報τは、乱数rnによって暗号文Cの一部C1との関係をかく乱させたかく乱情報τ(n)であってもよい。
【００７７】
＜第四実施形態＞
図９及び図１０を用いて第四実施形態に係る電子署名システム４を説明する。図９は第四実施形態に係る電子署名システム４の構成例を、図１０はその処理フローを示す。
【００７８】
電子署名システム４は、端末装置４１と、N個の代理計算装置１２−ｎとを含む。これらはネットワークを通じて通信可能に構成されている。ただし、Nは２以上の整数であり、n=1,…,Nである。
【００７９】
ここで、Kを１以上N以下の整数とし、f(x)=a(K-1)x(K-1)+…+a1x+a0とし、a0=f(0)を真の秘密情報とし、jnをn毎に異なる1以上の整数とし、f(jn)を分散された秘密情報とする。平文Mに対応する情報τと真の秘密情報a0とを用いて電子署名σに対応する情報a0τを求めることができ、電子署名σに対応する情報a0τから電子署名σを求めるものとする。ここでは、群で定義された演算を加法的に表現する。
【００８０】
図１１に示すように、端末装置４１は、依頼部４１１と署名生成部４１２と記憶部４１３とを含む。図１１は、端末装置４１の機能ブロック図を示す。
【００８１】
端末装置４１及び代理計算装置１２−ｎは、ルータ装置、サーバ装置、携帯電話、ＩＣカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたＣＰＵ(central processing unit)やＲＡＭ(random-access memory)を備えた公知又は専用のコンピュータなどである。
【００８２】
＜事前処理＞
例えば、図示しない分配装置(公開鍵サーバ)は、公開鍵yと、公開鍵yに対応する秘密鍵dを生成し、公開鍵yを公開する。電子署名の暗号方式としては、ElGamal暗号方式、楕円ElGamal暗号方式、RSA暗号方式、Pailler暗号方式などが考えられる。
【００８３】
また、分配装置は、秘密鍵dを真の秘密情報a0とし、a0を定数項とするランダムな（K-1）次の多項式を選び、
f(x)=a(K-1)x(K-1)+…+a1x+a0
とし、代理計算装置１２−ｎに分散された秘密情報f(jn)を配る。さらに、分配装置は、分散された秘密情報f(jn)を配った後に、真の秘密情報a0を削除してもよい。
【００８４】
代理計算装置１２−ｎは、分散された秘密情報f(jn)を受け取り、記憶部１２２に分散された秘密情報f(jn)を格納しておく。
【００８５】
端末装置４１は、平文Mを受け取り、記憶部４１３に平文Mを格納しておく。
【００８６】
＜署名生成処理＞
端末装置４１の依頼部４１１は、平文Mに対応する情報τから値f(jn)τを求めるように代理計算装置１２−ｎに対して依頼する（ｓ１）。例えば、ネットワークを介して平文Mに対応する情報τと計算依頼情報(値f(jn)τを求めるように記述された情報)とをN個の代理計算装置１２−ｎに送信する。なお、必ずしもN個の代理計算装置１２−ｎに送信する必要はなく、少なくともK個の代理計算装置１２−ｎに送信すればよい。
【００８７】
代理計算装置１２−ｎの計算部１２１は、平文Mに対応する情報τを受け取ると、記憶部１２２から分散された秘密情報f(jn)を読み込み、平文Mに対応する情報τと分散された秘密情報f(jn)とを用いて値f(jn)τを求め（ｓ２）、端末装置４１に送信する。
【００８８】
端末装置４１の署名生成部４１２は、K個の値f(jk)τを受け取ると、K個の値f(jk)τを用いて、電子署名σに対応する情報a0τを求め、電子署名σに対応する情報a0τから電子署名σを求める（ｓ３）。
【００８９】
端末装置４１は、平文Mと電子署名σを図示しない端末装置に送信する。
【００９０】
図示しない端末装置は、平文Mと電子署名σと公開鍵yとを用いて、電子署名σが真正であるか否かを判断することができる。
【００９１】
以下、RSA暗号を用いた場合の電子署名について説明する。なお、説明を分かり易くするために、この例では、jn=jk=nとする。
【００９２】
(RSA暗号を用いた場合の電子署名)
RSA暗号を用いた電子署名では、公開鍵y=(e,m)とする。
【００９３】
平文Mに対応する情報τを平文Mそのもの(τ=M)とし、電子署名σを次式により生成する。
σ=Ma_0
【００９４】
ここでは、群で定義された演算を乗法的に表現する。
【００９５】
端末装置４１は、平文Mと計算依頼情報(値Mf(n)を求めるように記述された情報)とをN個の代理計算装置１２−ｎに送信する。
【００９６】
代理計算装置１２−ｎは、値Mf(n)を求め、端末装置４１に送信する。
【００９７】
端末装置４１は、K個の値Mf(k)を用いて、電子署名σ=Ca_0を生成し、平文Mと電子署名σを図示しない端末装置に送信する。例えば、K=2、f(x)=a1x+a0の場合、a0=2f(1)+f(2)の関係が成り立つため、Mf(1)、Mf(2)を用いて、次式により電子署名σを生成することができる。
σ=Ma_0=M2f(1)+f(2)
【００９８】
図示しない端末装置は、平文Mと電子署名σと公開鍵y=(m,e)とを用いて、次式が成り立つか否か検証し、成り立つ場合には電子署名σが真正であると判断する。
M=σe mod m
【００９９】
＜効果＞
このような構成により、真の秘密情報a0を端末装置４１に対して秘密にしたまま、端末装置４１は平文Mに対する電子署名σを生成することができる。端末装置１１では、真の秘密情報a0を知ることはできないため、真の秘密情報a0の消去失敗による情報漏洩を防止することができる。なお、本実施形態と第二実施形態とを組合せてもよい。例えば、鍵装置２３がN個の代理計算装置１２−ｎを管理し、鍵装置２３を介して情報を送受信する。また、本実施形態と第三実施形態とを組合せてもよい。例えば、乱数rnによって平文との関係をかく乱させたかく乱情報τ(n)を平文に対応する情報τとして生成し、各処理を行う。
【０１００】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【０１０１】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１０２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【０１０４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０５】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2015022098.tif 000003
【図２】
2015022098.tif 000004
【図３】
2015022098.tif 000005
【図４】
2015022098.tif 000006
【図５】
2015022098.tif 000007
【図６】
2015022098.tif 000008
【図７】
2015022098.tif 000009
【図８】
2015022098.tif 000010
【図９】
2015022098.tif 000011
【図１０】
2015022098.tif 000012
【図１１】
2015022098.tif 000013