(57)【要約】【課題】損失落とし戸関数に対して電子透かしを埋め込み、検出し、除去する。【解決手段】電子透かし鍵生成装置１０はベクトル空間パラメータと公開鍵と埋込鍵と検出鍵と除去鍵を生成する。また、損失落とし戸関数の鍵生成アルゴリズムにより単射鍵と逆関数鍵と損失鍵を生成する。電子透かし埋込装置２０は入力された埋込対象関数鍵から埋込鍵を用いて透かし付関数鍵を出力する。電子透かし検出装置３０は入力された検出対象関数鍵から検出鍵を用いて電子透かしが埋め込まれているか否かを出力する。電子透かし除去装置４０は入力された除去対象関数鍵から除去鍵を用いて除去済関数鍵を出力する。関数実行装置５０は情報xから透かし付関数鍵を用いて損失落とし戸関数の計算アルゴリズムを実行することで情報yを出力する。また、情報yから逆関数鍵を用いて損失落とし戸関数の逆計算アルゴリズムを実行することで情報xを出力する。【選択図】図４
2013213962.tif 000002
【特許請求の範囲】
【請求項１】
電子透かし鍵生成装置と電子透かし埋込装置と電子透かし検出装置と電子透かし除去装置を含む電子透かし処理システムであって、
G,GTは素数位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B*,B^はベクトル空間Vの基底であり、基底Bと基底B*は双対直交基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であり、αはN以下の任意の整数であるとして、
前記電子透かし鍵生成装置は、
前記素数qと前記ベクトル空間Vと前記標準基底Aと前記双線形写像eを用いてベクトル空間パラメータparamV:=(q,V,GT,A,e)を生成するベクトル空間パラメータ生成部と、
前記ベクトル空間パラメータparamVを用いて前記基底B,B*を生成する双対直交基底生成部と、
前記基底B*を用いてk0を生成し、前記基底Bを用いて前記基底B^を生成し、損失落とし戸関数LTFの関数鍵生成アルゴリズムSampを用いて、公開鍵pk:=(paramV,B^,k0,Samp)を生成する公開鍵生成部と、
前記基底Bから前記基底B^に含まれない元を選択して埋込鍵mkを生成する埋込鍵生成部と、
前記基底B*を用いて検出鍵dk:=B*を生成する検出鍵生成部と、
前記正則行列Xを用いて除去鍵rk:=Xを生成する除去鍵生成部と、
α×αの行列Mを単位行列に設定し、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekおよび逆関数鍵ikをそれぞれ単射鍵ekIおよび逆関数鍵ikとして生成する単射鍵生成部と、
前記行列Mをゼロ行列に設定し、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekを損失鍵ekLとして生成する損失鍵生成部と、
を含み、
前記電子透かし埋込装置は、
埋込対象関数鍵ekを入力として、前記埋込鍵mkを用いて、透かし付関数鍵WM(ek)を出力する電子透かし埋込部と、
を含み、
前記電子透かし検出装置は、
検出対象関数鍵ek’を入力として、前記検出鍵dkを用いて、検出対象関数鍵ek’に電子透かしが埋め込まれているか否かを示す情報を出力する電子透かし検出部と、
を含み、
前記電子透かし除去装置は、
除去対象関数鍵ek”を入力として、前記除去鍵rkを用いて、除去済関数鍵ek^を出力する電子透かし除去部と、
を含む
ことを特徴とする電子透かし処理システム。
【請求項２】
請求項１に記載の電子透かし処理システムであって、
・T（上付き文字のT）は・の転置行列を表し、・-1（上付き文字の-1）は・の逆行列を表し、前記正則行列Xはχi,j(i,j=1,…,N)を前記一般線形群GL(N,Fq)からランダムに選択して生成した正則行列であり、nはN=4n+2であり、前記ベクトル空間Vは
【数５５】
2013213962.tif 000057
で定義され、前記標準基底Aは
【数５６】
2013213962.tif 000058
で定義され、前記基底Bは
【数５７】
2013213962.tif 000059
で定義され、前記基底B*は
【数５８】
2013213962.tif 000060
で定義され、前記基底B^は
【数５９】
2013213962.tif 000061
で定義され、前記埋込鍵mkはmk:=(bn+1,…,b4n)で定義され、前記行列MはM:=mi,j(i,j=1,…,α)で定義されるとして、
前記公開鍵生成部は、
有限体Fq上のn次元ベクトルη→をランダムに生成し、前記基底B*を用いて
【数６０】
2013213962.tif 000062
を生成し、前記関数鍵生成アルゴリズムSampを用いて、前記公開鍵pk:=(paramV,B^,k0,Samp)を生成し、
前記電子透かし埋込部は、
前記埋込対象関数鍵
【数６１】
2013213962.tif 000063
を入力として、有限体Fq上のn次元ベクトルπ→iをランダムに選択し、前記埋込鍵mkに含まれる(bn+1,…,b2n)を用いて、i=1,…,αについて、
【数６２】
2013213962.tif 000064
を計算し、前記透かし付関数鍵
【数６３】
2013213962.tif 000065
を出力し、
前記電子透かし検出部は、
検出対象関数鍵
【数６４】
2013213962.tif 000066
を入力として、有限体Fq上のn次元ベクトルσ→,η→をランダムに生成し、前記検出鍵dk:=B*を用いて、
【数６５】
2013213962.tif 000067
を生成し、i=1,…,nについて、
【数６６】
2013213962.tif 000068
を計算し、いずれかのiについてδi≠1である場合には、電子透かしが埋め込まれていることを示す情報を出力し、すべてのiについてδi=1である場合には、電子透かしが埋め込まれていないことを示す情報を出力し、
前記電子透かし除去部は、
前記除去対象関数鍵
【数６７】
2013213962.tif 000069
を入力として、前記除去鍵rk:=Xと前記基底Bを用いて、i=1,…,α、n’<4n+1について、ベクトル分解アルゴリズムDecomp(υ~i,,(b0,…,bn’),X,B)を実行することでzi,jbj(i=1,…,α、j=0,…,4n+1)を求め、
【数６８】
2013213962.tif 000070
を計算し、前記除去済関数鍵
【数６９】
2013213962.tif 000071
を生成し、
前記関数鍵生成アルゴリズムSampは、
前記ベクトル空間パラメータparamVと前記基底B^を入力として、有限体Fq上のα次元ベクトルψをランダムに生成し、j=1,…,αについて、
【数７０】
2013213962.tif 000072
を計算し、有限体Fqからζ1,…,ζα、φ1,…,φαをランダムに選択し、有限体Fq上のn次元ベクトルω→1,…,ω→αをランダムに生成し、i,j=1,…,αについて、
【数７１】
2013213962.tif 000073
を計算し、前記関数鍵
【数７２】
2013213962.tif 000074
を生成し、前記逆関数鍵
【数７３】
2013213962.tif 000075
を生成する
ことを特徴とする電子透かし処理システム。
【請求項３】
GTは素数位数qの巡回乗法群であり、Fqは位数qの有限体であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B^はベクトル空間Vの基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であり、αはN以下の任意の整数であるとして、
αビットの情報xを入力として、透かし付関数鍵WM(ek)を用いて損失落とし戸関数LTFの計算アルゴリズムEvalを実行することで、情報yを出力する関数実行部と、
前記情報yを入力として、逆関数鍵ikを用いて前記損失落とし戸関数LTFの逆計算アルゴリズムInvertを実行することで、前記情報xを出力する逆関数実行部と、
を含み、
前記透かし付関数鍵WM(ek)は、ベクトル空間パラメータparamV:=(q,V,GT,A,e)と前記基底B^と単位行列もしくはゼロ行列であるα×αの行列Mを用いて前記損失落とし戸関数LTFの関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekに、前記基底Bから前記基底B^に含まれない元を選択した埋込鍵mkを用いて生成されたものであり、
前記逆関数鍵ikは、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られるものである
ことを特徴とする関数実行装置。
【請求項４】
請求項３に記載の関数実行装置であって、
・T（上付き文字のT）は・の転置行列を表し、・-1（上付き文字の-1）は・の逆行列を表し、Gは素数位数qの巡回乗法群であり、gは群Gの生成元であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xはχi,j(i,j=1,…,N)を前記一般線形群GL(N,Fq)からランダムに生成した正則行列であり、nはN=4n+2であり、前記ベクトル空間Vは
【数７４】
2013213962.tif 000076
で定義され、前記標準基底Aは
【数７５】
2013213962.tif 000077
で定義され、前記基底Bは
【数７６】
2013213962.tif 000078
で定義され、前記基底B^は
【数７７】
2013213962.tif 000079
で定義され、前記埋込鍵mkはmk:=(bn+1,…,b4n)で定義され、前記行列MはM:=mi,j(i,j=1,…,α)で定義されるとして、
前記関数鍵生成アルゴリズムSampは、
前記ベクトル空間パラメータparamVと前記基底B^を入力として、有限体Fq上のα次元ベクトルψをランダムに生成し、j=1,…,αについて、
【数７８】
2013213962.tif 000080
を計算し、有限体Fqからζ1,…,ζα、φ1,…,φαをランダムに選択し、有限体Fq上のn次元ベクトルω→1,…,ω→αをランダムに生成し、i,j=1,…,αについて、
【数７９】
2013213962.tif 000081
を計算し、前記関数鍵
【数８０】
2013213962.tif 000082
を生成し、前記逆関数鍵
【数８１】
2013213962.tif 000083
を生成し、
前記計算アルゴリズムEvalは、
前記情報x:=(x1,…,xα)を入力として、前記透かし付関数鍵WM(ek)を用いて、i,j:=1,…,αについて、
【数８２】
2013213962.tif 000084
を計算し、前記情報y:=(y1,…,yα,y’α+1)を出力し、
前記逆計算アルゴリズムInvertは、
前記情報yを入力として、前記逆関数鍵ikを用いて、i,j:=1,…,αについて、
【数８３】
2013213962.tif 000085
を計算し、前記情報xを出力する
ことを特徴とする関数実行装置。
【請求項５】
G,GTは素数位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B*,B^はベクトル空間Vの基底であり、基底Bと基底B*は双対直交基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であり、αはN以下の任意の整数であるとして、
前記素数qと前記ベクトル空間Vと前記標準基底Aと前記双線形写像eを用いてベクトル空間パラメータparamV:=(q,V,GT,A,e)を生成するベクトル空間パラメータ生成部と、
前記ベクトル空間パラメータparamVを用いて前記基底B,B*を生成する双対直交基底生成部と、
前記基底B*を用いてk0を生成し、前記基底Bを用いて前記基底B^を生成し、損失落とし戸関数LTFの関数鍵生成アルゴリズムSampを用いて、公開鍵pk:=(paramV,B^,k0,Samp)を生成する公開鍵生成部と、
前記基底Bから前記基底B^に含まれない元を選択して埋込鍵mkを生成する埋込鍵生成部と、
前記基底B*を用いて検出鍵dk:=B*を生成する検出鍵生成部と、
前記正則行列Xを用いて除去鍵rk:=Xを生成する除去鍵生成部と、
α×αの行列Mを単位行列に設定し、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekおよび逆関数鍵ikをそれぞれ単射鍵ekIおよび逆関数鍵ikとして生成する単射鍵生成部と、
前記行列Mをゼロ行列に設定し、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekを損失鍵ekLとして生成する損失鍵生成部と、
を含む電子透かし鍵生成装置。
【請求項６】
G,GTは素数位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B*,B^はベクトル空間Vの基底であり、基底Bと基底B*は双対直交基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であるとして、
埋込対象関数鍵ekを入力として、埋込鍵mkを用いて、透かし付関数鍵WM(ek)を出力する電子透かし埋込部を含み、
前記埋込鍵mkは、前記基底Bから前記基底B^に含まれない元を選択して生成されたものであり、
前記基底Bは、前記ベクトル空間パラメータparamV:=(q,V,GT,A,e)を用いて生成されたものである
ことを特徴とする電子透かし埋込装置。
【請求項７】
G,GTは素数位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B*,B^はベクトル空間Vの基底であり、基底Bと基底B*は双対直交基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であるとして、
検出対象関数鍵ek’を入力として、検出鍵dkを用いて、検出対象関数鍵ek’に電子透かしが埋め込まれているか否かを示す情報を出力する電子透かし検出部を含み、
前記検出鍵dkは、前記基底B*を用いて生成されたものであり、
前記基底B*は、前記ベクトル空間パラメータparamV:=(q,V,GT,A,e)を用いて生成されたものである
ことを特徴とする電子透かし検出装置。
【請求項８】
qは素数であり、Fqは位数qの有限体であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であるとして、
除去対象関数鍵ek”を入力として、除去鍵rkを用いて、除去済関数鍵ek^を出力する電子透かし除去部を含み、
前記除去鍵rkは、前記正則行列Xを用いて生成されたものである
ことを特徴とする電子透かし除去装置。
【請求項９】
G,GTは素数位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B*,B^はベクトル空間Vの基底であり、基底Bと基底B*は双対直交基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であり、αはN以下の任意の整数であるとして、
前記素数qと前記ベクトル空間Vと前記標準基底Aと前記双線形写像eを用いてベクトル空間パラメータparamV:=(q,V,GT,A,e)を生成するベクトル空間パラメータ生成ステップと、
前記ベクトル空間パラメータparamVを用いて前記基底B,B*を生成する双対直交基底生成ステップと、
前記基底B*を用いてk0を生成し、前記基底Bを用いて前記基底B^を生成し、損失落とし戸関数LTFの関数鍵生成アルゴリズムSampを用いて、公開鍵pk:=(paramV,B^,k0,Samp)を生成する公開鍵生成ステップと、
前記基底Bから前記基底B^に含まれない元を選択して埋込鍵mkを生成する埋込鍵生成ステップと、
前記基底B*を用いて検出鍵dk:=B*を生成する検出鍵生成ステップと、
前記正則行列Xを用いて除去鍵rk:=Xを生成する除去鍵生成ステップと、
α×αの行列Mを単位行列に設定し、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekおよび逆関数鍵ikをそれぞれ単射鍵ekIおよび逆関数鍵ikとして生成する単射鍵生成ステップと、
前記行列Mをゼロ行列に設定し、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekを損失鍵ekLとして生成する損失鍵生成ステップと、
埋込対象関数鍵ekを入力として、前記埋込鍵mkを用いて、透かし付関数鍵WM(ek)を出力する電子透かし埋込ステップと、
検出対象関数鍵ek’を入力として、前記検出鍵dkを用いて、検出対象関数鍵ek’に電子透かしが埋め込まれているか否かを示す情報を出力する電子透かし検出ステップと、
除去対象関数鍵ek”を入力として、前記除去鍵rkを用いて、除去済関数鍵ek^を出力する電子透かし除去ステップと、
を含む電子透かし処理方法。
【請求項１０】
GTは素数位数qの巡回乗法群であり、Fqは位数qの有限体であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B^はベクトル空間Vの基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であり、αはN以下の任意の整数であるとして、
αビットの情報xを入力として、透かし付関数鍵WM(ek)を用いて損失落とし戸関数LTFの計算アルゴリズムEvalを実行することで、情報yを出力する関数実行ステップと、
前記情報yを入力として、逆関数鍵ikを用いて前記損失落とし戸関数LTFの逆計算アルゴリズムInvertを実行することで、前記情報xを出力する逆関数実行ステップと、
を含み、
前記透かし付関数鍵WM(ek)は、ベクトル空間パラメータparamV:=(q,V,GT,A,e)と前記基底B^と単位行列もしくはゼロ行列であるα×αの行列Mを用いて前記損失落とし戸関数LTFの関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekに、前記基底Bから前記基底B^に含まれない元を選択した埋込鍵mkを用いて生成されたものであり、
前記逆関数鍵ikは、前記ベクトル空間パラメータparamVと前記基底B^と前記行列Mを用いて前記関数鍵生成アルゴリズムSampを実行することにより得られるものである
ことを特徴とする関数実行方法。
【請求項１１】
請求項３または４に記載の関数実行装置もしくは請求項５に記載の電子透かし鍵生成装置もしくは請求項６に記載の電子透かし埋込装置もしくは請求項７に記載の電子透かし検出装置もしくは請求項８に記載の電子透かし除去装置としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、著作権保護や不正コピー防止等に利用される電子透かし技術に関し、特に、電気通信システムの暗号機能を実現するために用いられる暗号学的関数に対する電子透かし処理技術に関する。
【背景技術】
【０００２】
従来からデジタル音声、デジタル画像、デジタル動画等のマルチメディア情報に対して著作権保護や不正コピーの追跡、制御等を目的として電子透かし技術が用いられている。また、ソフトウェア、プログラムに対する電子透かしを実現するために、関数に対して電子透かしを入れる技術が考えられている。
【０００３】
関数に対する電子透かしを実現する方法として、例えば、ハッシュ関数へ著作権を付与する方法（非特許文献１）や、放送暗号における復号関数へ著作権を付与する方法（非特許文献２）がある。これらの方式は、電子透かしの概念と近い技術であり、不正な関数生成を防止することができる。また、ペアリング上のベクトル空間におけるベクトル分解問題に基づき、デジタル署名への電子透かし方法が提案されている（非特許文献３）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】David Naccache, Adi Shamir, and Julien P. Stern. “How to copyright a function?”, In Public Key Cryptography, volume 1560 of Lecture Notes in Computer Science, pages 188-196. Springer, 1999.
【非特許文献２】Aggelos Kiayias and Moti Yung. “Traitor tracing with constant transmission rate.”, In EUROCRYPT, volume 2332 of Lecture Notes in Computer Science, pages 450-465. Springer, 2002.
【非特許文献３】Maki Yoshida and Toru Fujiwara. “Toward digital watermarking for cryptographic data.”, IEICE Transactions, 94-A(1):270-272, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の電子透かし技術は暗号学的な取り扱いがなされず、暗号学的に証明可能な安全性を有していなかった。また、暗号学的関数への電子透かし技術はこれまで実現されていなかった。
【０００６】
例えば、非特許文献１に記載の技術は、著作権を付与することができるのはハッシュ関数のみである。ハッシュ関数は署名に利用することはできるが、公開鍵暗号や紛失通信など、その他の強力な暗号プリミティブを実現できるかどうかがわかっていない。また、非特許文献１の方式は電子透かしの検出をデータベースに登録してある情報を検索することでしか実現できず、電子透かしの除去もできない。さらに、著作権付与回数が限定されている。非特許文献２に記載の技術も、著作権を付与できるのは復号関数のみであるので、その他の強力な暗号プリミティブに応用できるかどうかがわかっておらず、著作権付与回数が限定されている。非特許文献３に記載の技術は、電子署名に対してしか実現できておらず、その他の強力な暗号プリミティブに応用できるかどうかがわかっていない。また、暗号学的に証明可能な安全性を有していない。
【０００７】
この発明はこのような点に鑑みてなされたものであり、様々な暗号プリミティブを実現することができる暗号学的関数である損失落とし戸関数に対して電子透かしを埋め込み、検出し、除去することができる電子透かし処理技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、この発明の電子透かし処理システムは、電子透かし鍵生成装置と電子透かし埋込装置と電子透かし検出装置と電子透かし除去装置を含む。この発明では、G,GTは素数位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、B,B*,B^はベクトル空間Vの基底であり、基底Bと基底B*は双対直交基底であり、基底B^は基底Bから所定の元を選択した部分基底であり、eはV×V→GTの双線形写像であり、αはN以下の任意の整数であるとする。
【０００９】
電子透かし鍵生成装置は、ベクトル空間パラメータ生成部と双対直交基底生成部と公開鍵生成部と埋込鍵生成部と検出鍵生成部と除去鍵生成部と単射鍵生成部と損失鍵生成部を備える。ベクトル空間パラメータ生成部は、素数qとベクトル空間Vと標準基底Aと双線形写像eを用いてベクトル空間パラメータparamV:=(q,V,GT,A,e)を生成する。双対直交基底生成部は、ベクトル空間パラメータparamVを用いて基底B,B*を生成する。公開鍵生成部は、基底B*を用いてk0を生成し、基底Bを用いて基底B^を生成し、損失落とし戸関数LTFの関数鍵生成アルゴリズムSampを用いて、公開鍵pk:=(paramV,B^,k0,Samp)を生成する。埋込鍵生成部は、基底Bから基底B^に含まれない元を選択して埋込鍵mkを生成する。検出鍵生成部は、基底B*を用いて検出鍵dk:=B*を生成する。除去鍵生成部は、正則行列Xを用いて除去鍵rk:=Xを生成する。単射鍵生成部は、α×αの行列Mを単位行列に設定し、ベクトル空間パラメータparamVと基底B^と行列Mを用いて関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekおよび逆関数鍵ikをそれぞれ単射鍵ekIおよび逆関数鍵ikとして生成する。損失鍵生成部は、行列Mをゼロ行列に設定し、ベクトル空間パラメータparamVと基底B^と行列Mを用いて関数鍵生成アルゴリズムSampを実行することにより得られる関数鍵ekを損失鍵ekLとして生成する。
【００１０】
電子透かし埋込装置は、電子透かし埋込部を含む。電子透かし埋込部は、埋込対象関数鍵ekを入力として、埋込鍵mkを用いて、透かし付関数鍵WM(ek)を出力する。
【００１１】
電子透かし検出装置は、電子透かし検出部を含む。電子透かし検出部は、検出対象関数鍵ek’を入力として、検出鍵dkを用いて、検出対象関数鍵ek’に電子透かしが埋め込まれているか否かを示す情報を出力する。
【００１２】
電子透かし除去装置は、電子透かし除去部を含む。除去対象関数鍵ek”を入力として、除去鍵rkを用いて、除去済関数鍵ek^を出力する。
【発明の効果】
【００１３】
この発明の電子透かし処理技術によれば、様々な暗号プリミティブを実現することができる暗号学的関数である損失落とし戸関数に対して電子透かしを埋め込み、検出し、除去することができる。したがって、損失落とし戸関数により実現される暗号プリミティブを実装するソフトウェアに対して著作権の付与や不正コピーの防止等が可能となる。
【図面の簡単な説明】
【００１４】
【図１】損失落とし戸関数を説明する図。
【図２】関数に対する電子透かしの埋込および除去を説明する図。
【図３】関数に対する電子透かしの検出を説明する図。
【図４】電子透かし処理システムの構成例を示すブロック図。
【図５】電子透かし鍵生成装置の構成例を示すブロック図。
【図６】（Ａ）電子透かし埋込装置の構成例を示すブロック図、（Ｂ）電子透かし検出装置の構成例を示すブロック図、（Ｃ）電子透かし除去装置の構成例を示すブロック図。
【図７】関数実行装置の構成例を示すブロック図。
【図８】電子透かし処理システムのデータフローを説明する図。
【図９】電子透かし鍵生成装置の動作例を示すフローチャート。
【図１０】（Ａ）電子透かし埋込装置の動作例を示すフローチャート、（Ｂ）電子透かし検出装置の動作例を示すフローチャート、（Ｃ）電子透かし除去装置の動作例を示すフローチャート。
【図１１】関数実行装置の動作例を示すフローチャート。
【図１２】この発明の電子透かし処理技術と従来技術との比較を示す図。
【発明を実施するための形態】
【００１５】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１６】
［この明細書で使用する表記方法］
【００１７】
【数１】
2013213962.tif 000003
【００１８】
は、ある値a,bについて、aにbを代入する、またはaをbで定義することを表す。
【００１９】
【数２】
2013213962.tif 000004
【００２０】
は、ある有限集合Sについて、集合Sから要素rを一様ランダムに選ぶことを表す。
【００２１】
【数３】
2013213962.tif 000005
【００２２】
は、ある確率的多項式時間アルゴリズムAについて、アルゴリズムAがxを入力にとり、乱数を生成して動作し、aを出力することを表す。
【００２３】
λはセキュリティパラメータを表す。qはλビットの素数である。G,GTは素数位数qの巡回乗法群である。gは群Gの生成元である。eは双線形写像である。Fqは位数qの有限体である。GL(n,Fq)は有限体Fq上のn次元一般線形群である。BMSetupは1λを入力とし、双線形写像のパラメータ(q,g,G,GT,e)を出力する標準的なアルゴリズムである。
【００２４】
【数４】
2013213962.tif 000006
【００２５】
は、有限体Fq上のベクトル表現を表す。x→（上付き文字の→）も同様である。つまり、x→は(x1,…,xn)∈Fqを表す。
【００２６】
【数５】
2013213962.tif 000007
【００２７】
および
【００２８】
【数６】
2013213962.tif 000008
【００２９】
は、x→とy→の内積を表す。すなわち、x→=(x1,…,xn)、y→=(y1,…,yn)であるとして、
【００３０】
【数７】
2013213962.tif 000009
【００３１】
である。
【００３２】
【数８】
2013213962.tif 000010
【００３３】
は行列Xの転置行列を表す。
【００３４】
【数９】
2013213962.tif 000011
【００３５】
は行列Xの逆行列を表す。
【００３６】
bi∈V(i=1,…,n)のとき、span<b1,…,bn>⊆Vは、b1,…,bnによって生成される部分空間である。基底B:=(b1,…,bN)と基底B*:=(b*1,…,b*N)に対し、
【００３７】
【数１０】
2013213962.tif 000012
【００３８】
とする。
ベクトルe→jは標準基底ベクトル
【００３９】
【数１１】
2013213962.tif 000013
【００４０】
である。
【００４１】
［双線形写像の説明］
双線形写像とは、楕円曲線上の二点に定義されるペアリング演算を行うための関数である。G×G→GTの双線形写像eは以下の性質を満たす。
＜双線型性＞任意のg,h∈Gおよび任意のa,b∈Fqに対して、e(ag,bh)=e(g,h)abが成立する。
＜非退化性＞e(g,g)≠1を満たすgが存在する。つまり、もしgがGの生成元ならe(g,g)はGTの生成元である。
＜計算可能性＞任意のg,h∈Gに対して、e(g,h)を効率的に（つまり多項式時間で）計算可能である。
【００４２】
双線形写像の具体例としては、例えば、WeilペアリングやTateペアリングなどが考えられる。ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMillerのアルゴリズムなどが存在する。詳しくは「D. Boneh and M. K. Franklin. “Identity-Based Encryption from the Weil Pairing.”, In CRYPTO’01,volume 2139 of Lecture Notes in Computer Science, pages 213-229. Springer, 2001.」や「D. Moriyama, R. Nishimaki, and T. Okamoto. “公開鍵暗号の数理” 共立出版, 2011.」および「黒澤馨, “現代暗号への招待”, サイエンス社」を参照されたい。
【００４３】
［双対ペアリングベクトル空間の説明］
この発明では双対ペアリングベクトル空間を利用する。対称ペアリング群(q,g,G,GT,e)による双対ペアリングベクトル空間(q,V,GT,A,e)とは、素数q、有限体Fq上のN次元ベクトル空間V、位数qの巡回群GT、N次元ベクトル空間Vの標準基底A、およびV×V→GTである双線形写像eの組である。
【００４４】
N次元ベクトル空間Vは以下の式で定義される。
【００４５】
【数１２】
2013213962.tif 000014
【００４６】
N次元ベクトル空間Vの標準基底Aは以下の式で定義される。
【００４７】
【数１３】
2013213962.tif 000015
【００４８】
双線形写像eは以下の式で定義される。
【００４９】
【数１４】
2013213962.tif 000016
【００５０】
これは非退化双線形である。つまり、e(sx,ty)=e(x,y)st、かつ、もしすべてのy∈Vに対しe(x,y)=1ならばx=0である。すべてのiおよびjに対しe(ai,aj)=e(G,G)δi,jである。ただし、i=jならδi,j=1、そうでなければδi,j=0である。またe(G,G)≠1である。
【００５１】
双対ペアリングベクトル空間生成アルゴリズムGdpvsは1λとベクトル空間Vの次元数である自然数Nを入力として、ベクトル空間パラメータparamV:=(q,V,GT,A,e)を得る。双対ペアリングベクトル空間生成アルゴリズムGdpvsはBMSetupを使用して構成することができる。
【００５２】
双対ペアリングベクトル空間において、双対基底を構成する方法は以下の通りである。まず、双線形写像パラメータ(q,g,G,GT,e)を以下の式により生成する。
【００５３】
【数１５】
2013213962.tif 000017
【００５４】
次に、双対直交基底(paramV,B,B*)を以下の式により生成する。
【００５５】
【数１６】
2013213962.tif 000018
【００５６】
双対ペアリングベクトル空間は以下の性質を有する。
【００５７】
＜ペアリング演算＞双対ペアリングベクトル空間の要素x,y∈Vについて、以下の式が成立する。
【００５８】
【数１７】
2013213962.tif 000019
【００５９】
ここで、xおよびyは基底A上の係数ベクトルとして表現可能である。つまり、以下の式のように表すことができる。
【００６０】
【数１８】
2013213962.tif 000020
【００６１】
＜基底変換＞標準基底Aは以下の式で定義される一様ランダムな正則行列Xを用いてN次元ベクトル空間Vの基底Bに変換可能である。
【００６２】
【数１９】
2013213962.tif 000021
【００６３】
ただし、基底Bは以下の式で定義される。
【００６４】
【数２０】
2013213962.tif 000022
【００６５】
また、標準基底Aは正則行列Xを用いてベクトル空間Vの基底B*に変換可能である。ただし、基底B*は以下の式で定義される。
【００６６】
【数２１】
2013213962.tif 000023
【００６７】
基底Bと基底B*は双対直交基底である。つまり、以下の式が成立する。
【００６８】
【数２２】
2013213962.tif 000024
【００６９】
ここで、x:=x1b1+…+xNbN∈V、y:=y1b*1+…+yNb*N∈Vは基底Bと基底B*の係数ベクトルとして表現可能である。つまり、以下の式が成立する。
【００７０】
【数２３】
2013213962.tif 000025
【００７１】
双対ペアリングベクトル空間についての詳細は、「Tatsuaki Okamoto and Katsuyuki Takashima. “Fully secure functional encryption with general relations from the decisional linear assumption.”, In CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 191-208. Springer, 2010.」を参照されたい。
【００７２】
［損失落とし戸関数の説明］
この発明では損失落とし戸関数に対する電子透かしを実現する。図１を参照して、損失落とし戸関数について説明する。ここでは、損失落とし戸関数LTFを定義域Dから定義域Rへの写像とする。損失落とし戸関数LTFは単射関数fと損失関数flossのいずれとしても動作することができるが、単射関数fと損失関数flossは識別不可能である。単射関数fは１対１の写像である。そして、逆関数f-1が計算可能である。逆関数f-1は計算が困難であるが、落とし戸tがあれば効率的に計算することができる。損失関数flossは単射ではない。したがって、落とし戸tがあったとしても逆関数floss-1は計算することができない。
【００７３】
損失落とし戸関数LTFは以下の４つの多項式時間アルゴリズムからなる。ここで、λはセキュリティパラメータであり、n(λ)は関数の入力長である。
単射鍵生成：アルゴリズムLTF.IGenは、計算鍵ekIと逆計算鍵ikを出力する。
計算：アルゴリズムLTF.Evalek(X)(X∈D)は像Y=fek(X)を出力する。
逆計算：アルゴリズムLTF.Invertik(Y)は逆像X=f-1ik(Y)を出力する。
損失鍵生成：アルゴリズムLTF.LGenは計算鍵ekLを出力する。
【００７４】
損失落とし戸関数LTFは以下の性質を有する。
【００７５】
＜完全性＞すべての計算鍵ekと逆計算鍵ikの組み合わせ
【００７６】
【数２４】
2013213962.tif 000026
【００７７】
およびX∈Dに対して、fik-1(fek(X))=Xが成立する。
【００７８】
＜識別不可能性＞すべての確率的多項式時間攻撃者Aに対して
【００７９】
【数２５】
2013213962.tif 000027
【００８０】
が成立する。ここで、neglは無視できる関数である。
【００８１】
＜損失性＞損失落とし戸関数LTFがγ損失であるとは、すべての
【００８２】
【数２６】
2013213962.tif 000028
【００８３】
に対して、像fek’(D)のサイズが高々|D|/2γとなることである。
【００８４】
損失落とし戸関数を利用することで、一方向性関数、落とし戸付一方向性関数、衝突困難ハッシュ関数、選択暗号文攻撃に対して安全な公開鍵暗号、紛失通信などの様々な暗号プリミティブを実現することができる。したがって、損失落とし戸関数に対する電子透かしを実現することは、様々な電子透かし付き暗号プリミティブを実現できることを意味している。
【００８５】
損失落とし戸関数についての詳細は、「Chris Peikert and Brent Waters. “Lossy trapdoor functions and their applications.”, In STOC'08, pages 187-196. ACM, 2008.」および「D. Moriyama, R. Nishimaki, and T. Okamoto. “公開鍵暗号の数理” 共立出版, 2011.」を参照されたい。
【００８６】
［関数への電子透かし処理の説明］
図２を参照して、関数に対する電子透かしの埋込方法および除去方法を説明する。関数fに対して電子透かしを埋め込むために、埋込アルゴリズムMarkは埋込鍵mkを用いてそれぞれに異なるパターンが埋め込まれた透かし付き関数fm1,…,fmnを出力する。透かし付き関数fm1,…,fmnはいずれも電子透かしを埋め込む前の関数fと同じ計算を行う。
【００８７】
電子透かしを除去する除去アルゴリズムRemoveは除去鍵rkを用いて透かし付き関数fm1,…,fmnに埋め込まれた電子透かしを除去して元の関数fを復元することができる。
【００８８】
図３を参照して、関数に対する電子透かしの検出方法を説明する。関数に対して電子透かしが埋め込まれているか否かを検出する検出アルゴリズムDetectは検出鍵dkを用いて入力された関数に電子透かしが埋め込まれているかを示す情報を出力する。透かし付き関数fmjが入力された場合には、電子透かしが埋め込まれていることを示す「true」を出力する。透かしなし関数fが入力された場合には、電子透かしが埋め込まれていないことを示す「false」を出力する。不正ユーザjが他のユーザに関数fmjのコピーを渡した場合、コピーされた関数に電子透かしが埋め込まれているか否かを検出し、検出した電子透かしのパターンから関数fmjの流出元である不正ユーザjが誰かを特定することができる。
【００８９】
したがって、電子透かしを実現するために必要とされる要件は、電子透かしの偽造を防止するために、埋込鍵mkがなければ電子透かしを埋め込むことができないこと、そして、除去鍵rkがないと関数の機能を破壊することなく電子透かしを取り除くことができないことである。
【００９０】
［この発明のポイント］
損失落とし戸関数への電子透かしを実現するために、この発明では、双対ペアリングベクトル空間を利用する。そして、双対ペアリングベクトル空間の双対直交基底を使用した電子透かしの実現のために、準機能暗号文と準機能鍵を利用する。準機能暗号文は通常の暗号文と識別不可能であり、通常の鍵を用いる限り通常通り復号が可能である。準機能鍵は通常の鍵と識別不可能であり、通常の暗号文については通常通り復号可能である。一方で、準機能暗号文を準機能鍵で復号することは不可能である。この準機能暗号文と準機能鍵の性質は、従来は暗号の安全性を証明するためのテクニックとして用いられてきたが、暗号機能を実行する上では利用されてこなかった。この発明による問題解決手法として重要な点は、これら準機能暗号文と準機能鍵を証明のテクニックとしてだけではなく、暗号機能を実行する上で利用したことである。
【００９１】
また、電子透かしの除去を可能とするために、双対ペアリングベクトル空間の生成に使用した正則行列Xを利用する。これまで双対ペアリングベクトル空間を利用した技術は双対直交基底を利用することで様々な問題を解決してきたが、その生成に用いた行列Xそのものを利用することは考えられていなかった。このように正則行列Xを利用することも問題解決手法として重要な点である。
【００９２】
［第１の実施形態］
＜構成＞
図４を参照して、この発明の第１の実施形態に係る電子透かし処理システム１の構成例を詳細に説明する。電子透かし処理システム１は電子透かし鍵生成装置１０、電子透かし埋込装置２０、電子透かし検出装置３０、電子透かし除去装置４０、ネットワーク９から構成される。電子透かし処理システム１を利用する装置を関数実行装置５０とする。電子透かし鍵生成装置１０と電子透かし埋込装置２０と電子透かし検出装置３０と電子透かし除去装置４０と関数実行装置５０はネットワーク９に接続されている。ネットワーク９は電子透かし処理システム１を構成する各装置間と関数実行装置５０が相互に通信可能であればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、電子透かし処理システム１と関数実行装置５０は必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、電子透かし鍵生成装置１０が出力する情報をＵＳＢメモリなどの可搬媒体に記憶し、その可搬媒体から関数実行装置５０へオフラインで入力するように構成してもよい。
【００９３】
図５を参照して、電子透かし鍵生成装置１０の構成例を説明する。電子透かし鍵生成装置１０は、双線形写像パラメータ生成部１１０とベクトル空間パラメータ生成部１１５と双対直交基底生成部１２０と公開鍵生成部１２５と埋込鍵生成部１３０と検出鍵生成部１３５と除去鍵生成部１４０と透かし鍵配信部１４５と単射鍵生成部１５０と損失鍵生成部１５５と関数鍵配信部１６０を備える。
【００９４】
図６（Ａ）を参照して、電子透かし埋込装置２０の構成例を説明する。電子透かし埋込装置２０は、電子透かし埋込部２１０と埋込鍵記憶部２９０を備える。図６（Ｂ）を参照して、電子透かし検出装置３０の構成例を説明する。電子透かし検出装置３０は、電子透かし検出部３１０と検出鍵記憶部３９０を備える。図６（Ｃ）を参照して、電子透かし除去装置４０の構成例を説明する。電子透かし除去装置４０は、電子透かし除去部４１０と除去鍵記憶部４９０を備える。
【００９５】
図７を参照して、関数実行装置５０の構成例を説明する。関数実行装置５０は、関数実行部５１０と逆関数実行部５２０と関数鍵記憶部５９０を備える。
【００９６】
＜鍵生成処理＞
図８を参照して、電子透かし鍵生成装置１０が実行する鍵生成処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【００９７】
電子透かし鍵生成装置１０の備える双線形写像パラメータ生成部１１０は、BMSetupを実行して、双線形写像パラメータ(q,g,G,GT,e)を生成する(S110)。したがって、双線形写像パラメータ生成部１１０の処理は以下の式のように表すことができる。
【００９８】
【数２７】
2013213962.tif 000029
【００９９】
電子透かし鍵生成装置１０の備えるベクトル空間パラメータ生成部１１５は、双対ペアリングベクトル空間生成アルゴリズムGdpvsを実行して、ベクトル空間パラメータparamV:=(q,V,GT,A,e)を生成する(S115)。したがって、ベクトル空間パラメータ生成部１１５の処理は以下の式のように表すことができる。ただし、nはベクトル空間Vの次元数をNとして、N=4n+2である。
【０１００】
【数２８】
2013213962.tif 000030
【０１０１】
電子透かし鍵生成装置１０の備える双対直交基底生成部１２０は、ベクトル空間パラメータparamV:=(q,V,GT,A,e)を用いて、ベクトル空間Vの基底B,B*を生成する(S120)。まず、双対直交基底生成部１２０は、以下の式のように正則行列Xを生成する。
【０１０２】
【数２９】
2013213962.tif 000031
【０１０３】
次に、双対直交基底生成部１２０は、以下の式のように基底Bを生成する。
【０１０４】
【数３０】
2013213962.tif 000032
【０１０５】
そして、双対直交基底生成部１２０は、以下の式のように基底B*を生成する。
【０１０６】
【数３１】
2013213962.tif 000033
【０１０７】
電子透かし鍵生成装置１０の備える公開鍵生成部１２５は、公開鍵pk:=(paramV,B^,k0,Samp)を生成する(S125)。まず、公開鍵生成部１２５は、有限体Fq上のn次元ベクトルη→をランダムに生成する。
【０１０８】
【数３２】
2013213962.tif 000034
【０１０９】
次に、n次元ベクトルη→と基底B*を用いて以下の式のようにk0を生成する。
【０１１０】
【数３３】
2013213962.tif 000035
【０１１１】
続いて、公開鍵生成部１２５は以下の式のように基底B^を生成する。
【０１１２】
【数３４】
2013213962.tif 000036
【０１１３】
そして、損失落とし戸関数LTFの関数鍵生成アルゴリズムSampを用いて、公開鍵pk:=(paramV,B^,k0,Samp)を生成する。関数鍵生成アルゴリズムSampについては後述する。
【０１１４】
電子透かし鍵生成装置１０の備える埋込鍵生成部１３０は、基底Bから基底B^に含まれない元を選択して埋込鍵mkを生成する(S130)。すなわち、mk:=(bn+1,…,b4n)である。
【０１１５】
電子透かし鍵生成装置１０の備える検出鍵生成部１３５は、基底B*を用いて検出鍵dkを生成する(S135)。すなわち、dk:=B*:=(b*0,…,b*4n+1)である。
【０１１６】
電子透かし鍵生成装置１０の備える除去鍵生成部１４０は、正則行列Xを用いて除去鍵rkを生成する(S140)。すなわち、rk:=Xである。
【０１１７】
電子透かし鍵生成装置１０の備える透かし鍵配信部１４５は、生成した公開鍵pkと埋込鍵mkと検出鍵dkと除去鍵rkを各装置に配信する(S145)。図１１に電子透かし鍵生成装置１０が生成した電子透かし鍵を配信する動作例を示す。公開鍵pkは電子透かし埋込装置２０と電子透かし検出装置３０と電子透かし鍵除去装置４０に配信される。埋込鍵mkは電子透かし埋込装置２０に配信される。検出鍵dkは電子透かし検出装置３０に配信される。除去鍵rkは電子透かし除去装置４０に配信される。
【０１１８】
電子透かし鍵生成装置１０の備える単射鍵生成部１５０は、単射鍵ekIおよび逆関数鍵ikを生成する(S150)。まず、単射鍵生成部１５０は、α×αの行列M:=mi,j(i,j=1,…,α)を単位行列に設定する。すなわち、mi,j=1(i=j)かつmi,j=0(i≠j)である。次に、ベクトル空間パラメータparamVと基底B^と行列Mを用いて関数鍵生成アルゴリズムSampを実行する。そして、関数鍵生成アルゴリズムSampの出力する関数鍵ekを単射鍵ekIとして設定し、関数鍵生成アルゴリズムSampの出力する逆関数鍵ikを取得する。
【０１１９】
関数鍵生成アルゴリズムSampは、ベクトル空間パラメータparamVと基底B^を入力として、関数鍵ekと逆関数鍵ikを出力する。まず、有限体Fq上のα次元ベクトルψを以下の式のように生成する。
【０１２０】
【数３５】
2013213962.tif 000037
【０１２１】
次に、j=1,…,αについて、以下の式のようにgTを計算する。
【０１２２】
【数３６】
2013213962.tif 000038
【０１２３】
続いて、ζ1,…,ζα、φ1,…,φαおよび有限体Fq上のn次元ベクトルω→1,…,ω→αを以下の式のように生成する。
【０１２４】
【数３７】
2013213962.tif 000039
【０１２５】
次に、i,j=1,…,αについて、以下の式のようにu,υを計算する。
【０１２６】
【数３８】
2013213962.tif 000040
【０１２７】
そして、関数鍵ekを以下の式のように設定する。
【０１２８】
【数３９】
2013213962.tif 000041
【０１２９】
ここで、{ui,j}i,jは(u1,1,…,uα,α)を表し、{υ1,…,υα}は(υ1,…,υα)を表す。これを行列で表現すると、以下の式のように表すことができる。
【０１３０】
【数４０】
2013213962.tif 000042
【０１３１】
また、関数鍵生成アルゴリズムSampは逆関数鍵ikを設定する。単射鍵を生成する場合には、逆関数鍵ikはik:=ψが設定される。損失鍵を生成する場合には、逆関数ikはik:=⊥が設定される。損失関数は逆関数を計算できないためである。
【０１３２】
電子透かし鍵生成装置１０の備える損失鍵生成部１５５は、損失鍵ekLを生成する(S155)。まず、損失鍵生成部１５５は、α×αの行列M:=mi,j(i,j=1,…,α)をゼロ行列に設定する。すなわち、すべてのi,jについてmi,j=0である。次に、ベクトル空間パラメータparamVと基底B^と行列Mを用いて関数鍵生成アルゴリズムSampを実行する。そして、関数鍵生成アルゴリズムSampの出力する関数鍵ekを損失鍵ekLとして生成する。
【０１３３】
電子透かし鍵生成装置１０の備える関数鍵配信部１６０は、生成した単射関数鍵ekIもしくは損失関数鍵ekLと逆関数鍵ikを各装置に配信する。図１１に電子透かし鍵生成装置１０が生成した関数鍵を配信する動作例を示す。単射関数鍵ekIもしくは損失関数鍵ekLは電子透かし埋込装置２０に配信される。逆関数鍵ikは関数実行装置５０に配信される。電子透かしを埋め込まずに損失落とし戸関数LTFを利用したい場合には、単射関数鍵ekIもしくは損失関数鍵ekLを関数実行装置５０に配信することができる。
【０１３４】
＜電子透かし埋込処理＞
図９（Ａ）を参照して、電子透かし埋込装置２０が実行する電子透かし埋込処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１３５】
電子透かし埋込装置２０の備える埋込鍵記憶部２９０には、電子透かし鍵生成装置１０が生成した公開鍵pkと埋込鍵mkが記憶されている。埋込鍵記憶部２９０は、例えば、ＲＡＭ（Random Access Memory）や、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、リレーショナルデータベースやキーバリューストアなどのミドルウェア、又は、ハードディスクや光ディスクなどの補助記憶装置により構成することができる。
【０１３６】
電子透かし埋込装置２０の備える電子透かし埋込部２１０は、埋込対象関数鍵ekを入力として、埋込鍵記憶部２９０に記憶されている埋込鍵mkを用いて、透かし付関数鍵WM(ek)を出力する(S211)。埋込対象関数鍵ekは、以下の式のように表すことができる。
【０１３７】
【数４１】
2013213962.tif 000043
【０１３８】
まず、電子透かし埋込部２１０は、有限体Fq上のn次元ベクトルπ→iを以下の式のように生成する。
【０１３９】
【数４２】
2013213962.tif 000044
【０１４０】
次に、電子透かし埋込部２１０は、埋込鍵mkに含まれる(bn+1,…,b2n)を用いて、i=1,…,αについて、以下の式のようにυ~iを計算する。
【０１４１】
【数４３】
2013213962.tif 000045
【０１４２】
そして、透かし付関数鍵WM(ek)を以下の式のように出力する(S212)。
【０１４３】
【数４４】
2013213962.tif 000046
【０１４４】
＜電子透かし検出処理＞
図９（Ｂ）を参照して、電子透かし検出装置３０が実行する電子透かし検出処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１４５】
電子透かし検出装置３０の備える検出鍵記憶部３９０には、電子透かし鍵生成装置１０が生成した公開鍵pkと検出鍵dkが記憶されている。検出鍵記憶部３９０は、例えば、ＲＡＭ（Random Access Memory）や、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、リレーショナルデータベースやキーバリューストアなどのミドルウェア、又は、ハードディスクや光ディスクなどの補助記憶装置により構成することができる。
【０１４６】
電子透かし検出装置３０の備える電子透かし検出部３１０は、検出対象関数鍵ek’を入力として、検出鍵dkを用いて、検出対象関数鍵ek’に電子透かしが埋め込まれているか否かを示す情報を出力する(S311)。検出対象関数鍵ek’は、以下の式のように表すことができる。
【０１４７】
【数４５】
2013213962.tif 000047
【０１４８】
まず、電子透かし検出部３１０は、有限体Fq上のn次元ベクトルσ→,η→を以下の式のように生成する。
【０１４９】
【数４６】
2013213962.tif 000048
【０１５０】
次に、検出鍵dk:=B*を用いて、以下の式のようにkを計算する。
【０１５１】
【数４７】
2013213962.tif 000049
【０１５２】
次に、i=1,…,nについて、以下の式のようにδを計算する。
【０１５３】
【数４８】
2013213962.tif 000050
【０１５４】
いずれかのiについてδi≠1である場合には、電子透かしが埋め込まれていることを示す情報を出力する(S312)。例えば、「true」とδi≠1であるiの値を出力する。出力するiは電子透かしが埋め込まれている位置を示している。すべてのiについてδi=1である場合には、電子透かしが埋め込まれていないことを示す情報を出力する。例えば、「false」を出力する。
【０１５５】
＜電子透かし除去処理＞
図９（Ｃ）を参照して、電子透かし除去装置４０が実行する電子透かし除去処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１５６】
電子透かし除去装置４０の備える除去鍵記憶部４９０には、電子透かし鍵生成装置１０が生成した公開鍵pkと除去鍵rkが記憶されている。除去鍵記憶部４９０は、例えば、ＲＡＭ（Random Access Memory）や、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、リレーショナルデータベースやキーバリューストアなどのミドルウェア、又は、ハードディスクや光ディスクなどの補助記憶装置により構成することができる。
【０１５７】
電子透かし除去装置４０の備える電子透かし除去部４１０は、除去対象関数鍵ek”を入力として、除去鍵記憶部４９０に記憶されている除去鍵rkを用いて、除去済関数鍵ek^を出力する(S411)。除去対象関数鍵ek”は以下の式のように表すことができる。
【０１５８】
【数４９】
2013213962.tif 000051
【０１５９】
まず、除去鍵rk:=Xと基底Bを用いて、i=1,…,α、n’=0,…,4n+1について、ベクトル分解アルゴリズムDecomp(υ~i,,(b0,…,bn’),X,B)を実行し、zi,jbj(i=1,…,α、j=0,…,4n+1)を出力する。
【０１６０】
ベクトル分解アルゴリズムDecompについての詳細は、「Tatsuaki Okamoto and Katsuyuki Takashima, “Homomorphic encryption and signatures from vector decomposition.”, In Pairing, volume 5209 of Lecture Notes in Computer Science, pages 57-74. Springer, 2008.」を参照されたい。
【０１６１】
次に、電子透かし除去部４１０は、以下の式のようにυ’iを計算する。
【０１６２】
【数５０】
2013213962.tif 000052
【０１６３】
そして、以下の式のように、除去済関数鍵ek^を出力する(S412)。
【０１６４】
【数５１】
2013213962.tif 000053
【０１６５】
＜関数実行処理＞
図１０を参照して、関数実行装置５０が実行する関数実行処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１６６】
関数実行装置５０の備える関数鍵記憶部５９０には、電子透かし鍵生成装置１０が生成した透かし付関数鍵WM(ek)と逆関数鍵ikが記憶されている。関数鍵記憶部５９０は、例えば、ＲＡＭ（Random Access Memory）や、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、リレーショナルデータベースやキーバリューストアなどのミドルウェア、又は、ハードディスクや光ディスクなどの補助記憶装置により構成することができる。
【０１６７】
関数実行装置５０の備える関数実行部５１０は、αビットの情報x:=(x1,…,xα)を入力として、関数鍵記憶部５９０に記憶されている透かし付関数鍵WM(ek)を用いて損失落とし戸関数LTFの計算アルゴリズムEvalを実行することで、情報yを出力する(S510)。
【０１６８】
計算アルゴリズムEvalは情報xと関数鍵ekを入力として情報yを出力する。まず、計算アルゴリズムEvalは、関数鍵ekを用いて、i,j:=1,…,αについて、以下の式により情報y:=(y1,…,yα,y’α+1)を出力する。
【０１６９】
【数５２】
2013213962.tif 000054
【０１７０】
ここで、ζ→:=(ζ1,…,ζα)、φ→:=(φ1,…,φα)である。また、ω’→iを縦ベクトルとしたとき、以下の式のように表すことができる。
【０１７１】
【数５３】
2013213962.tif 000055
【０１７２】
＜逆関数実行処理＞
図１１を参照して、関数実行装置５０が実行する逆関数実行処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１７３】
関数実行装置５０の備える逆関数実行部５２０は、情報yを入力として、関数鍵記憶部５９０に記憶されている逆関数鍵ikを用いて損失落とし戸関数LTFの逆計算アルゴリズムInvertを実行することで、情報xを出力する(S520)。
【０１７４】
逆計算アルゴリズムInvertは情報yと逆関数鍵ikを入力として情報xを出力する。逆計算アルゴリズムInvertは、逆関数鍵ikを用いて、i,j:=1,…,αについて、以下の式により情報xを出力する。
【０１７５】
【数５４】
2013213962.tif 000056
【０１７６】
［この発明と従来技術との比較］
図１２にこの発明の電子透かし技術と従来技術との比較を示す。“方式”列は、この明細書における文献の番号、もしくはこの明細書における実施例の番号を表す。“タイプ”列は、それぞれの方式が目的としている技術の種類を表す。“対象”列は、それぞれの方式で著作権や電子透かしを処理する対象となる関数の種類を表す。“仮定”列は、それぞれの方式が安全性の根拠とする暗号学的な仮定を表す。“安全性”列は、それぞれの方式の安全性における特徴を表す。
【０１７７】
非特許文献１および非特許文献２は関数に対する著作権付与の方式であり、付与回数が限定されている。非特許文献３は関数に対する電子透かしの方式であるが、暗号学的に証明可能な安全性を有していない。このように、付与回数の限定がなく暗号学的に証明可能な安全性を有している電子透かし方式は、この発明のみが実現していることがわかる。
【０１７８】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１７９】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１８０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１８１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１８２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１８３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１８４】
１  電子透かし処理システム
９  ネットワーク
１０  電子透かし鍵生成装置
２０  電子透かし埋込装置
３０  電子透かし検出装置
４０  電子透かし除去装置
５０  関数実行装置
１１０  双線形写像パラメータ生成部
１１５  ベクトル空間パラメータ生成部
１２０  双対直交基底生成部
１２５  公開鍵生成部
１３０  埋込鍵生成部
１３５  検出鍵生成部
１４０  除去鍵生成部
１４５  透かし鍵配信部
１５０  単射鍵生成部
１５５  損失鍵生成部
１６０  関数鍵配信部
２１０  電子透かし埋込部
２９０  埋込鍵記憶部
３１０  電子透かし検出部
３９０  検出鍵記憶部
４１０  電子透かし除去部
４９０  除去鍵記憶部
５１０  関数実行部
５２０  逆関数実行部
５９０  関数鍵記憶部
【図１】
2013213962.tif 000086
【図２】
2013213962.tif 000087
【図３】
2013213962.tif 000088
【図４】
2013213962.tif 000089
【図５】
2013213962.tif 000090
【図６】
2013213962.tif 000091
【図７】
2013213962.tif 000092
【図８】
2013213962.tif 000093
【図９】
2013213962.tif 000094
【図１０】
2013213962.tif 000095
【図１１】
2013213962.tif 000096
【図１２】
2013213962.tif 000097