(57)【特許請求の範囲】
【請求項１】
電子透かし鍵生成装置、電子透かし埋込装置、電子透かし検出装置、電子透かし除去装置及び関数実行装置を含む電子透かしシステムであって、
Nは自然数であり、qは素数であり、G,GTは位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、Fq×は有限体Fq上の乗法群であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、eはV×V→GTの双線形写像であり、γはN以下の任意の整数であり、paramVはparamV:=(q,V,GT,A,e)であるベクトル空間パラメータであり、
上記電子透かし鍵生成装置は、
上記標準基底A及び上記正則行列Xを用いて、上記ベクトル空間Vの双対直交基底である基底B及び基底B*を生成する双対直交基底生成部と、
上記基底Bから所定の元を選択して基底B^を生成した上で上記ベクトル空間パラメータparamV及び上記基底B^を含む公開鍵pk並びに上記基底B*から所定の元を選択した秘密鍵skを生成する鍵ペア生成部と、
上記基底B*から上記秘密鍵skに含まれない元を選択して埋込鍵mkを生成する埋込鍵生成部と、
上記基底Bから上記基底B^に含まれない元を選択して検出鍵dkを生成する検出鍵生成部と、
上記正則行列Xを除去鍵rkとして設定する除去鍵生成部と、
単位行列に設定したγ×γの行列Mを用いて生成した行列ui,j、上記基底Bを用いて生成した行列vi,j及び上記基底B*を用いて生成した値kIDを含む単射鍵ekI並びに有限体Fqからランダムに生成した逆関数鍵ikを生成する単射鍵生成部と、
ゼロ行列に設定したγ×γの行列Mを用いて生成した行列ui,j、上記基底Bを用いて生成した行列vi,j及び上記基底B*を用いて生成した値kIDを含む損失鍵ekLを生成する損失鍵生成部と、
を含み、
上記電子透かし埋込装置は、
埋込対象関数鍵ekを入力として、上記埋込鍵mkを用いて、上記埋込対象関数鍵ekに含まれる値kIDに電子透かしを埋め込んだ透かし付関数鍵WM(ek)を生成する電子透かし埋込部
を含み、
上記電子透かし検出装置は、
検出対象関数鍵ek’を入力として、上記検出鍵dkを用いて、上記検出対象関数鍵ek’に含まれる値kIDに電子透かしが埋め込まれているか否かを示す情報を出力する電子透かし検出部
を含み、
上記電子透かし除去装置は、
除去対象関数鍵ek”を入力として、上記除去鍵rkを用いて、上記除去対象関数鍵ek”に含まれる値kIDから電子透かしを取り除いた除去済関数鍵ek^を出力する電子透かし除去部
を含み、
上記関数実行装置は、
計算対象の情報xを入力として、上記透かし付関数鍵WM(ek)を用いて、計算結果である情報yを出力する関数実行部と、
逆計算対象の情報yを入力として、上記逆関数鍵ikを用いて、逆計算結果である情報xを出力する逆関数実行部と、
を含む
電子透かしシステム。
【請求項２】
請求項１に記載の電子透かしシステムであって、
・Tは行列・の転置行列であり、・-1は行列・の逆行列であり、N=10であり、上記正則行列XはX:=χi,j（i,j=1,…,N）で定義され、上記標準基底AはA:=(a1,…,aN)で定義され、Sampは関数鍵ek及び逆関数鍵ikを出力する関数鍵生成アルゴリズムであり、
上記双対直交基底生成部は、上記基底Bを次式により生成し、
【数８５】
0005975961.tif 000086
上記基底B*を次式により生成するものであり、
【数８６】
0005975961.tif 000087
上記鍵ペア生成部は、上記基底B^:=(b1,b2,b3,b10)を生成した上で上記公開鍵pk:=(paramV,B^,Samp)及び上記秘密鍵sk:=(b*1,b*2,b*3,b*6,b*7)を生成するものであり、
上記埋込鍵生成部は、上記埋込鍵mk:=(b*8,b*9)を生成するものであり、
上記検出鍵生成部は、上記検出鍵dk:=(b8,b9)を生成するものであり、
上記除去鍵生成部は、上記除去鍵rk:=Xを生成するものであり、
上記単射鍵生成部は、上記ベクトル空間パラメータparamV、上記基底B^及び上記秘密鍵skを入力として、上記関数鍵生成アルゴリズムSampを実行し、上記関数鍵ekを上記単射鍵ekIとして生成するものであり、
上記損失鍵生成部は、上記ベクトル空間パラメータparamV、上記基底B^及び上記秘密鍵skを入力として、上記関数鍵生成アルゴリズムSampを実行し、上記関数鍵ekを上記単射鍵ekLとして生成するものであり、
上記関数鍵生成アルゴリズムSampは、任意のビット列IDを生成し、有限体Fq上のγ次元ベクトルψをランダムに生成し、j=1,…,γについて、次式に示すようにgT_jを計算し、
【数８７】
0005975961.tif 000088
有限体Fqから乱数ζ1,…,ζγ、φ1,…,φγ、ω1,…,ωγを選択し、i,j=1,…,γについて次式に示すように行列ui,j及び行列υiを計算し、
【数８８】
0005975961.tif 000089
有限体Fq上の乱数σ及び有限体Fq上の2次元ベクトルη→をランダムに生成し、次式に示すように値kIDを生成し、
【数８９】
0005975961.tif 000090
上記関数鍵ekを次式により生成し、
【数９０】
0005975961.tif 000091
上記逆関数鍵ikをik:=ψと設定するものであり、
上記電子透かし埋込部は、有限体Fq上の乱数μ1,μ2を選択し、次式に示すように値k~IDを計算し、
【数９１】
0005975961.tif 000092
次式により上記透かし付関数鍵WM(ek)を生成するものであり、
【数９２】
0005975961.tif 000093
上記電子透かし検出部は、乗法群Fq×上の乱数δ1,δ2を選択し、次式に示すように値cを計算し、
【数９３】
0005975961.tif 000094
次式に示すように値Δを計算し、
【数９４】
0005975961.tif 000095
Δ≠1であれば電子透かしが埋め込まれていることを示す情報を出力し、Δ=1であれば電子透かしが埋め込まれていないことを示す情報出力するものであり、
上記電子透かし除去部は、i=1,…,10について、次式を満たす値zib*iを計算し、
【数９５】
0005975961.tif 000096
次式に示すように値kIDを計算し、
【数９６】
0005975961.tif 000097
次式に示すように除去済関数鍵ek^を出力するものであり、
【数９７】
0005975961.tif 000098
上記関数実行部は、上記情報xはx:=(x1,…,xγ)と表すとして、i,j=1,…,γについて次式に示すようにy1,…,yγ+1,y'γ+1を計算し、
【数９８】
0005975961.tif 000099
上記情報y:=(y1,…,yγ,y'γ+1)を出力するものであり、
上記逆関数実行部は、i,j:=1,…,γについて次式によりx'jを計算し、
【数９９】
0005975961.tif 000100
j=1,…,γについてx'j=gTx_jを満たす値となるようにxjを設定し、上記情報x:=(x1,…,xγ)を出力するものである
電子透かしシステム。
【請求項３】
請求項１に記載の電子透かしシステムであって、
・Tは行列・の転置行列であり、・-1は行列・の逆行列であり、N=8であり、上記正則行列XはX:=χi,j（i,j=1,…,N）で定義され、上記標準基底AはA:=(a1,…,aN)で定義され、Sampは関数鍵ek及び逆関数鍵ikを出力する関数鍵生成アルゴリズムであり、
上記双対直交基底生成部は、上記基底Bを次式により生成し、
【数１００】
0005975961.tif 000101
上記基底B*を次式により生成するものであり、
【数１０１】
0005975961.tif 000102
上記鍵ペア生成部は、上記基底B^を次式により生成した上で
【数１０２】
0005975961.tif 000103
有限体Fqから乱数α,θ,σを選択し、上記公開鍵pk:=(paramV,B^,Samp)及び上記秘密鍵sk:=(αθd*1,θd*1,θd*2,σd*3,σd*4)を生成するものであり、
上記埋込鍵生成部は、上記埋込鍵mk:=(d*7,d*8)を生成するものであり、
上記検出鍵生成部は、上記検出鍵dk:=(d7,d8)を生成するものであり、
上記除去鍵生成部は、上記除去鍵rk:=Xを生成するものであり、
上記単射鍵生成部は、上記ベクトル空間パラメータparamV、上記基底B^、上記秘密鍵skを入力として、上記関数鍵生成アルゴリズムSampを実行し、上記関数鍵ekを上記単射鍵ekIとして生成するものであり、
上記損失鍵生成部は、上記ベクトル空間パラメータparamV、上記基底B^及び上記秘密鍵skを入力として、上記関数鍵生成アルゴリズムSampを実行し、上記関数鍵ekを上記単射鍵ekLとして生成するものであり、
上記関数鍵生成アルゴリズムSampは、任意のビット列IDを生成し、有限体Fq上のγ次元ベクトルψをランダムに生成し、g^T:=e(d1,d1*)αθとして、j=1,…,γについて、次式に示すようにgT_jを計算し、
【数１０３】
0005975961.tif 000104
有限体Fqから乱数s1,1,…,sγ,1、s1,2,…,sγ,2を選択し、i,j=1,…,γについて次式に示すように行列ui,j及び行列υiを計算し、
【数１０４】
0005975961.tif 000105
有限体Fq上の乱数r1,r2を選択し、次式に示すように値kIDを生成し、
【数１０５】
0005975961.tif 000106
上記関数鍵ekを次式により生成し、
【数１０６】
0005975961.tif 000107
上記逆関数鍵ikをik:=ψと設定するものであり、
上記電子透かし埋込部は、有限体Fq上の乱数t1,t2を選択し、次式に示すように値k~IDを計算し、
【数１０７】
0005975961.tif 000108
次式により上記透かし付関数鍵WM(ek)を生成するものであり、
【数１０８】
0005975961.tif 000109
上記電子透かし検出部は、乗法群Fq×上の乱数z1,z2を選択し、次式に示すように値cを計算し、
【数１０９】
0005975961.tif 000110
次式に示すように値Δを計算し、
【数１１０】
0005975961.tif 000111
Δ≠1であれば電子透かしが埋め込まれていることを示す情報を出力し、Δ=1であれば電子透かしが埋め込まれていないことを示す情報出力するものであり、
上記電子透かし除去部は、i=1,…,8について、次式を満たす値zid*iを計算し、
【数１１１】
0005975961.tif 000112
次式に示すように値kIDを計算し、
【数１１２】
0005975961.tif 000113
次式に示すように除去済関数鍵ek^を出力するものであり、
【数１１３】
0005975961.tif 000114
上記関数実行部は、上記情報xはx:=(x1,…,xγ)と表すとして、i,j=1,…,γについて次式に示すようにy1,…,yγ+1,y'γ+1を計算し、
【数１１４】
0005975961.tif 000115
上記情報y:=(y1,…,yγ,y'γ+1)を出力するものであり、
上記逆関数実行部は、i,j:=1,…,γについて次式によりx'jを計算し、
【数１１５】
0005975961.tif 000116
j=1,…,γについてx'j=g^Tx_jを満たす値となるようにxjを設定し、上記情報x:=(x1,…,xγ)を出力するものである
電子透かしシステム。
【請求項４】
Nは自然数であり、qは素数であり、G,GTは位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、Fq×は有限体Fq上の乗法群であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、eはV×V→GTの双線形写像であり、γはN以下の任意の整数であり、paramVはparamV:=(q,V,GT,A,e)であるベクトル空間パラメータであり、
上記標準基底A及び上記正則行列Xを用いて、上記ベクトル空間Vの双対直交基底である基底B及び基底B*を生成する双対直交基底生成部と、
上記基底Bから所定の元を選択して基底B^を生成した上で上記ベクトル空間パラメータparamV及び上記基底B^を含む公開鍵pk並びに上記基底B*から所定の元を選択した秘密鍵skを生成する鍵ペア生成部と、
上記基底B*から上記秘密鍵skに含まれない元を選択して埋込鍵mkを生成する埋込鍵生成部と、
上記基底Bから上記基底B^に含まれない元を選択して検出鍵dkを生成する検出鍵生成部と、
上記正則行列Xを除去鍵rkとして設定する除去鍵生成部と、
単位行列に設定したγ×γの行列Mを用いて生成した行列ui,j、上記基底Bを用いて生成した行列vi,j及び上記基底B*を用いて生成した値kIDを含む単射鍵ekI並びに有限体Fqからランダムに生成した逆関数鍵ikを生成する単射鍵生成部と、
ゼロ行列に設定したγ×γの行列Mを用いて生成した行列ui,j、上記基底Bを用いて生成した行列vi,j及び上記基底B*を用いて生成した値kIDを含む損失鍵ekLを生成する損失鍵生成部と、
を含む電子透かし鍵生成装置。
【請求項５】
Nは自然数であり、qは素数であり、G,GTは位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、Fq×は有限体Fq上の乗法群であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、eはV×V→GTの双線形写像であり、γはN以下の任意の整数であり、paramVはparamV:=(q,V,GT,A,e)であるベクトル空間パラメータであり、
双対直交基底生成部が、上記標準基底A及び上記正則行列Xを用いて、上記ベクトル空間Vの双対直交基底である基底B及び基底B*を生成する双対直交基底生成ステップと、
鍵ペア生成部が、上記基底Bから所定の元を選択して基底B^を生成した上で上記ベクトル空間パラメータparamV及び上記基底B^を含む公開鍵pk並びに上記基底B*から所定の元を選択した秘密鍵skを生成する鍵ペア生成ステップと、
埋込鍵生成部が、上記基底B*から上記秘密鍵skに含まれない元を選択して埋込鍵mkを生成する埋込鍵生成ステップと、
検出鍵生成部が、上記基底Bから上記基底B^に含まれない元を選択して検出鍵dkを生成する検出鍵生成ステップと、
除去鍵生成部が、上記正則行列Xを除去鍵rkとして設定する除去鍵生成ステップと、
単射鍵生成部が、単位行列に設定したγ×γの行列Mを用いて生成した行列ui,j、上記基底Bを用いて生成した行列vi,j及び上記基底B*を用いて生成した値kIDを含む単射鍵ekI並びに有限体Fqからランダムに生成した逆関数鍵ikを生成する単射鍵生成ステップと、
損失鍵生成部が、ゼロ行列に設定したγ×γの行列Mを用いて生成した行列ui,j、上記基底Bを用いて生成した行列vi,j及び上記基底B*を用いて生成した値kIDを含む損失鍵ekLを生成する損失鍵生成ステップと、
電子透かし埋込部が、埋込対象関数鍵ekを入力として、上記埋込鍵mkを用いて、上記埋込対象関数鍵ekに含まれる値kIDに電子透かしを埋め込んだ透かし付関数鍵WM(ek)を生成する電子透かし埋込ステップと、
電子透かし検出部が、検出対象関数鍵ek’を入力として、上記検出鍵dkを用いて、上記検出対象関数鍵ek’に含まれる値kIDに電子透かしが埋め込まれているか否かを示す情報を出力する電子透かし検出ステップと、
電子透かし除去部が、除去対象関数鍵ek”を入力として、上記除去鍵rkを用いて、上記除去対象関数鍵ek”に含まれる値kIDから電子透かしを取り除いた除去済関数鍵ek^を出力する電子透かし除去ステップと、
関数実行部が、計算対象の情報xを入力として、上記透かし付関数鍵WM(ek)を用いて、計算結果である情報yを出力する関数実行ステップと、
逆関数実行部が、逆計算対象の情報yを入力として、上記逆関数鍵ikを用いて、逆計算結果である情報xを出力する逆関数実行ステップと、
を含む電子透かし方法。
【請求項６】
請求項４に記載の電子透かし鍵生成装置としてコンピュータを機能させるプログラム。
【請求項７】
請求項５に記載の電子透かし方法の各ステップをコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、著作権保護や不正コピー防止などに利用される電子透かし技術に関し、特に、電気通信システムの暗号機能を実現するために用いられる暗号学的関数に対する電子透かし技術に関する。
【背景技術】
【０００２】
従来からデジタル音声、デジタル画像、デジタル動画などのマルチメディア情報に対して著作権保護や不正コピーの追跡、制御などを目的として電子透かし技術が用いられている。また、ソフトウェア、プログラムに対する電子透かしを実現するために、関数に対して電子透かしを入れる技術が考えられている。
【０００３】
関数に対する電子透かしを実現する方法として、例えば、ハッシュ関数へ著作権を付与する方法（非特許文献１）や、放送暗号における復号関数へ著作権を付与する方法（非特許文献２）がある。これらの方式は、電子透かしの概念と近い技術であり、不正な関数生成を防止することができる。また、ペアリング上のベクトル空間におけるベクトル分解問題に基づき、デジタル署名への電子透かし方法が提案されている（非特許文献３）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の電子透かし技術は暗号学的な取り扱いがなされず、暗号学的に証明可能な安全性を有していなかった。また、暗号学的関数への電子透かし技術はこれまで実現されていなかった。
【０００６】
例えば、非特許文献１に記載の技術は、著作権を付与することができるのはハッシュ関数のみである。ハッシュ関数は署名に利用することはできるが、公開鍵暗号や紛失通信など、その他の強力な暗号プリミティブを実現できるかどうかがわかっていない。また、非特許文献１の方式は電子透かしの検出をデータベースに登録してある情報を検索することでしか実現できず、電子透かしの除去もできない。さらに、著作権付与回数が限定されている。非特許文献２に記載の技術も、著作権を付与できるのは復号関数のみであるので、その他の強力な暗号プリミティブに応用できるかどうかがわかっておらず、著作権付与回数が限定されている。非特許文献３に記載の技術は、電子署名に対してしか実現できておらず、その他の強力な暗号プリミティブに応用できるかどうかがわかっていない。また、暗号学的に証明可能な安全性を有していない。
【０００７】
この発明はこのような点に鑑みてなされたものであり、様々な暗号プリミティブを実現することができる暗号学的関数である損失落とし戸関数に対して電子透かしを埋め込み、検出し、除去することができる電子透かし技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、この発明の電子透かしシステムは、電子透かし鍵生成装置、電子透かし埋込装置、電子透かし検出装置、電子透かし除去装置及び関数実行装置を含む。以下では、Nは自然数であり、qは素数であり、G,GTは位数qの巡回乗法群であり、gは群Gの生成元であり、Fqは位数qの有限体であり、Fq×は有限体Fq上の乗法群であり、GL(N,Fq)は有限体Fq上のN次元一般線形群であり、Xは一般線形群GL(N,Fq)からランダムに生成した正則行列であり、Vは有限体Fq上のN次元ベクトル空間であり、Aはベクトル空間Vの標準基底であり、eはV×V→GTの双線形写像であり、γはN以下の任意の整数であり、paramVはparamV:=(q,V,GT,A,e)であるベクトル空間パラメータであるとする。
【０００９】
電子透かし鍵生成装置は、双対直交基底生成部、鍵ペア生成部、埋込鍵生成部、検出鍵生成部、除去鍵生成部、単射鍵生成部及び損失鍵生成部を含む。双対直交基底生成部は、標準基底A及び正則行列Xを用いて、ベクトル空間Vの双対直交基底である基底B及び基底B*を生成する。鍵ペア生成部は、基底Bから所定の元を選択して基底B^を生成した上でベクトル空間パラメータparamV及び基底B^を含む公開鍵pk並びに基底B*から所定の元を選択した秘密鍵skを生成する。埋込鍵生成部は、基底B*から秘密鍵skに含まれない元を選択して埋込鍵mkを生成する。検出鍵生成部は、基底Bから基底B^に含まれない元を選択して検出鍵dkを生成する。除去鍵生成部は、正則行列Xを除去鍵rkとして設定する。単射鍵生成部は、単位行列に設定したγ×γの行列Mを用いて生成した行列ui,j、基底Bを用いて生成した行列vi,j及び基底B*を用いて生成した値kIDを含む単射鍵ekI並びに有限体Fqからランダムに生成した逆関数鍵ikを生成する。損失鍵生成部は、ゼロ行列に設定したγ×γの行列Mを用いて生成した行列ui,j、基底Bを用いて生成した行列vi,j及び基底B*を用いて生成した値kIDを含む損失鍵ekLを生成する。
【００１０】
電子透かし埋込装置は、電子透かし埋込部を含む。電子透かし埋込部は、埋込対象関数鍵ekを入力として、埋込鍵mkを用いて、埋込対象関数鍵ekに含まれる値kIDに電子透かしを埋め込んだ透かし付関数鍵WM(ek)を生成する。
【００１１】
電子透かし検出装置は、電子透かし検出部を含む。電子透かし検出部は、検出対象関数鍵ek’を入力として、検出鍵dkを用いて、検出対象関数鍵ek’に含まれる値kIDに電子透かしが埋め込まれているか否かを示す情報を出力する。
【００１２】
電子透かし除去装置は、電子透かし除去部を含む。電子透かし除去部は、除去対象関数鍵ek”を入力として、除去鍵rkを用いて、除去対象関数鍵ek”に含まれる値kIDから電子透かしを取り除いた除去済関数鍵ek^を出力する。
【００１３】
関数実行装置は、関数実行部及び逆関数実行部を含む。関数実行部は、計算対象の情報xを入力として、透かし付関数鍵WM(ek)を用いて、計算結果である情報yを出力する。逆関数実行部は、逆計算対象の情報yを入力として、逆関数鍵ikを用いて、逆計算結果である情報xを出力する。
【発明の効果】
【００１４】
この発明の電子透かし処理技術によれば、損失落とし戸関数に対して電子透かしを埋め込み、検出し、除去することができる。損失落とし戸関数は、様々な暗号プリミティブを実現することができる暗号学的関数である。したがって、損失落とし戸関数により実現される暗号プリミティブを実装するソフトウェアに対して著作権の付与や不正コピーの防止などが可能となる。
【図面の簡単な説明】
【００１５】
【図１】図１は、損失落とし戸関数を説明するための図である。
【図２】図２は、関数に対する電子透かしの埋込及び除去を説明するための図である。
【図３】図３は、関数に対する電子透かしの検出を説明するための図である。
【図４】図４は、電子透かしシステムの機能構成を例示する図である。
【図５】図５は、電子透かし鍵生成装置の機能構成を例示する図である。
【図６】図６（Ａ）は、電子透かし埋込装置の機能構成を例示する図である。図６（Ｂ）は、電子透かし検出装置の機能構成を例示する図である。図６（Ｃ）は、電子透かし除去装置の機能構成を例示する図である。
【図７】図７は、関数実行装置の機能構成を例示する図である。
【図８】図８は、電子透かし鍵生成装置の処理フローを例示する図である。
【図９】図９（Ａ）は、電子透かし埋込装置の処理フローを例示する図である。図９（Ｂ）は、電子透かし検出装置の処理フローを例示する図である。図９（Ｃ）は、電子透かし除去装置の処理フローを例示する図である。
【図１０】図１０は、関数実行装置の処理フローを例示する図である。
【図１１】図１１は、電子透かしシステムのデータフローを例示する図である。
【図１２】図１２は、この発明の電子透かし処理技術と従来技術との比較を示す図である。
【発明を実施するための形態】
【００１６】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１７】
［表記方法］
実施形態の説明に先立ち、この明細書で用いる表記方法及び用語を定義する。
【００１８】
次式は、ある値a,bについて、aにbを代入する、又は、aをbで定義することを表す。
【００１９】
【数１】
0005975961.tif 000002
【００２０】
_（アンダースコア）は下付き添字を表す。例えば、xy_zはyzがxに対する上付き添字であり、xy_zはyzがxに対する下付き添字であることを表す。
【００２１】
次式は、ある有限集合Sについて、集合Sから要素rを一様ランダムに選ぶことを表す。
【００２２】
【数２】
0005975961.tif 000003
【００２３】
次式は、ある確率的多項式時間アルゴリズムAについて、アルゴリズムAがxを入力にとり、乱数を生成して動作し、aを出力することを表す。
【００２４】
【数３】
0005975961.tif 000004
【００２５】
→（上付き文字の右矢印）は有限体Fq上のベクトル表現を表す。つまり、x→は(x1,…,xn)∈Fqである。数式内における次式も同様である。
【００２６】
【数４】
0005975961.tif 000005
【００２７】
次式はいずれもベクトルx→とベクトルy→の内積を表す。
【００２８】
【数５】
0005975961.tif 000006
【００２９】
すなわち、x→=(x1,…,xn)、y→=(y1,…,yn)であるとして、次式により定義される演算を表す。
【００３０】
【数６】
0005975961.tif 000007
【００３１】
T（上付き文字のT）は行列の転置を表す。例えば、XTは行列Xの転置行列である。数式内における次式も同様である。
【００３２】
【数７】
0005975961.tif 000008
【００３３】
-1（上付き文字の-1）は逆行列を表す。例えば、X-1は行列Xの逆行列である。数式内における次式も同様である。
【００３４】
【数８】
0005975961.tif 000009
【００３５】
bi∈V(i=1,…,n)のとき、span<b1,…,bn>⊆Vは、b1,…,bnによって生成される部分空間である。
【００３６】
基底B:=(b1,…,bN)と基底B*:=(b*1,…,b*N)に対し、次式の演算を定義する。
【００３７】
【数９】
0005975961.tif 000010
【００３８】
ベクトルe→jは次式により定義される標準基底ベクトルである。
【００３９】
【数１０】
0005975961.tif 000011
【００４０】
λはセキュリティパラメータを表す。
【００４１】
qはλビットの素数である。
【００４２】
G,GTは素数位数qの巡回乗法群である。
【００４３】
gは群Gの生成元である。
【００４４】
eはe:V×V→GTの双線形写像である。
【００４５】
Fqは位数qの有限体である。
【００４６】
Fq×は有限体Fqの乗法群である。
【００４７】
GL(n,Fq)は有限体Fq上のn次元一般線形群である。
【００４８】
BMSetupは1λを入力とし、双線形写像のパラメータ(q,g,G,GT,e)を出力する標準的なアルゴリズムである。
【００４９】
［双線形写像の説明］
双線形写像とは、楕円曲線上の二点に定義されるペアリング演算を行うための関数である。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,GT,g,e)による双対ペアリングベクトル空間(q,V,GT,A,e)とは、素数q、有限体Fq上のN次元ベクトル空間V、位数qの巡回群GT、ベクトル空間Vの標準基底A及びe:V×V→GTである双線形写像eの組である。
【００５２】
ここで、N次元ベクトル空間Vは以下の式で定義される。
【００５３】
【数１１】
0005975961.tif 000012
【００５４】
ベクトル空間Vの標準基底Aは以下の式で定義される。
【００５５】
【数１２】
0005975961.tif 000013
【００５６】
双線形写像eは以下の式で定義される。
【００５７】
【数１３】
0005975961.tif 000014
【００５８】
これは非退化双線形である。つまり、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ならばδi,j=0である。またe(g,g)≠1である。
【００６０】
双対ペアリングベクトル空間生成アルゴリズムGdpvsは1λ及び自然数Nを入力として、ベクトル空間パラメータparamV:=(q,V,GT,A,e)を得る。ここで、Nはベクトル空間Vの次元数である。双対ペアリングベクトル空間生成アルゴリズムGdpvsはGbmpを使用して構成することができる。
【００６１】
双対ペアリングベクトル空間において、双対基底を構成する方法は以下の通りである。まず、双線形写像パラメータ(q,g,G,GT,e)を次式により生成する。
【００６２】
【数１４】
0005975961.tif 000015
【００６３】
次に、双対直交基底(paramV,B,B*)を次式により生成する。
【００６４】
【数１５】
0005975961.tif 000016
【００６５】
ただし、gobは次式により定義される。
【００６６】
【数１６】
0005975961.tif 000017
【００６７】
双対ペアリングベクトル空間は以下の性質を有する。
＜ペアリング演算＞双対ペアリングベクトル空間Vの要素x,y∈Vについて、次式が成立する。
【００６８】
【数１７】
0005975961.tif 000018
【００６９】
ここで、x及びyは基底A上の係数ベクトルとして表現可能である。つまり、次式に示すように表すことができる。
【００７０】
【数１８】
0005975961.tif 000019
【００７１】
＜基底変換＞標準基底Aは一様ランダムな正則行列Xを用いて、N次元ベクトル空間Vの基底Bに変換可能である。ただし、正則行列Xは有限体Fq上のN次元一般線形群GL(N,Fq)よりランダムに生成され、次式により定義される。
【００７２】
【数１９】
0005975961.tif 000020
【００７３】
また、基底Bは次式により定義される。
【００７４】
【数２０】
0005975961.tif 000021
【００７５】
標準基底Aは上記の正則行列Xを用いてN次元ベクトル空間Vの基底B*にも変換可能である。ただし、基底B*は次式により定義される。
【００７６】
【数２１】
0005975961.tif 000022
【００７７】
ここで注目すべきは次式が成立することである。
【００７８】
【数２２】
0005975961.tif 000023
【００７９】
つまり、基底Bと基底B*はベクトル空間Vの双対直交基底である。
【００８０】
ここで、x:=x1b1+…+xNbN∈V及びy:=y1b*1+…+yNb*N∈Vは基底B及び基底B*の係数ベクトルとして表現可能である。つまり、次式が成立する。
【００８１】
【数２３】
0005975961.tif 000024
【００８２】
双対ペアリングベクトル空間についての詳細は、「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は、計算鍵ekと逆計算鍵ikを出力する。
・計算：アルゴリズムLTF.Evalek(X)(ただし、X∈D)は像Y=fek(X)を出力する。
・逆計算：アルゴリズムLTF.Invertik(Y)は逆像X=f-1ik(Y)を出力する。
・損失鍵生成：アルゴリズムLTF.LGenは計算鍵ek’を出力する。
【００８５】
損失落とし戸関数LTFは以下の性質を有する。
＜完全性＞すべての計算鍵ek及び逆計算鍵ikの組み合わせ
【００８６】
【数２４】
0005975961.tif 000025
【００８７】
及びX∈Dに対して、fik-1(fek(X))=Xが成立する。
＜識別不可能性＞すべての確率的多項式時間攻撃者Αに対して
【００８８】
【数２５】
0005975961.tif 000026
【００８９】
が成立する。ここで、neglは無視できる関数である。
＜損失性＞損失落とし戸関数LTFがγ損失であるとは、すべての
【００９０】
【数２６】
0005975961.tif 000027
【００９１】
に対して、像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を利用することも問題解決手法として重要な点である。
【０１００】
［第一実施形態］
＜構成＞
図４を参照して、この発明の第一実施形態に係る電子透かしシステム１の機能構成例を説明する。電子透かしシステム１は電子透かし鍵生成装置１０、電子透かし埋込装置２０、電子透かし検出装置３０、電子透かし除去装置４０、関数実行装置５０及びネットワーク９から構成される。電子透かし鍵生成装置１０、電子透かし埋込装置２０、電子透かし検出装置３０、電子透かし除去装置４０及び関数実行装置５０はネットワーク９に接続されている。ネットワーク９は電子透かしシステム１を構成する各装置が相互に通信可能であればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、電子透かしシステム１を構成する各装置間は必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、電子透かし鍵生成装置１０が出力する情報をＵＳＢメモリなどの可搬記録媒体に記憶し、その可搬記録媒体から関数実行装置５０へオフラインで入力するように構成してもよい。
【０１０１】
図５を参照して、電子透かしシステム１に含まれる電子透かし鍵生成装置１０の構成例を説明する。電子透かし鍵生成装置１０は、双線形写像パラメータ生成部１１０、ベクトル空間パラメータ生成部１１５、双対直交基底生成部１２０、鍵ペア生成部１２５、埋込鍵生成部１３０、検出鍵生成部１３５、除去鍵生成部１４０、透かし鍵配信部１４５、単射鍵生成部１５０、損失鍵生成部１５５及び関数鍵配信部１６０を備える。電子透かし鍵生成装置１０は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。電子透かし鍵生成装置１０は、例えば、中央演算処理装置の制御のもとで各処理を実行する。電子透かし鍵生成装置１０に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【０１０２】
図６（Ａ）を参照して、電子透かしシステム１に含まれる電子透かし埋込装置２０の構成例を説明する。電子透かし埋込装置２０は、電子透かし埋込部２１０及び埋込鍵記憶部２９０を備える。電子透かし埋込装置２０は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。電子透かし埋込装置２０は、例えば、中央演算処理装置の制御のもとで各処理を実行する。電子透かし埋込装置２０に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。埋込鍵記憶部２９０は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスク若しくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、又はリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【０１０３】
図６（Ｂ）を参照して、電子透かしシステム１に含まれる電子透かし検出装置３０の構成例を説明する。電子透かし検出装置３０は、電子透かし検出部３１０及び検出鍵記憶部３９０を備える。電子透かし検出装置３０は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。電子透かし検出装置３０は、例えば、中央演算処理装置の制御のもとで各処理を実行する。電子透かし検出装置３０に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。検出鍵記憶部３９０は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスク若しくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、又はリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【０１０４】
図６（Ｃ）を参照して、電子透かしシステム１に含まれる電子透かし除去装置４０の構成例を説明する。電子透かし除去装置４０は、電子透かし除去部４１０及び除去鍵記憶部４９０を備える。電子透かし除去装置４０は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。電子透かし除去装置４０は、例えば、中央演算処理装置の制御のもとで各処理を実行する。電子透かし除去装置４０に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。除去鍵記憶部４９０は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスク若しくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、又はリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【０１０５】
図７を参照して、電子透かしシステム１に含まれる関数実行装置５０の構成例を説明する。関数実行装置５０は、関数実行部５１０、逆関数実行部５２０及び関数鍵記憶部５９０を備える。関数実行装置５０は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。関数実行装置５０は、例えば、中央演算処理装置の制御のもとで各処理を実行する。関数実行装置５０に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。関数鍵記憶部５９０は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスク若しくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、又はリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【０１０６】
＜鍵生成処理＞
図８を参照して、電子透かし鍵生成装置１０が実行する鍵生成処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１０７】
ステップＳ１１０において、電子透かし鍵生成装置１０の備える双線形写像パラメータ生成部１１０は、セキュリティパラメータ1λを入力として、次式に示すようにBMSetupを実行して、双線形写像パラメータ(q,g,G,GT,e)を生成する。
【０１０８】
【数２７】
0005975961.tif 000028
【０１０９】
ステップＳ１１５において、電子透かし鍵生成装置１０の備えるベクトル空間パラメータ生成部１１５は、次式に示すように双対ペアリングベクトル空間生成アルゴリズムGdpvsを実行して、ベクトル空間パラメータparamV:=(q,V,GT,A,e,gT)を生成する。
【０１１０】
【数２８】
0005975961.tif 000029
【０１１１】
ここで、gTは、有限体Fqの乗法群Fq×から乱数ψを選択し、次式により計算する。
【０１１２】
【数２９】
0005975961.tif 000030
【０１１３】
ステップＳ１２０において、電子透かし鍵生成装置１０の備える双対直交基底生成部１２０は、ベクトル空間パラメータparamV:=(q,V,GT,A,e,gT)を用いて、ベクトル空間Vの基底B,B*,B^を生成する。まず、双対直交基底生成部１２０は、次式に示すように10次元一般線形群GL(10,Fq)から正則行列Xをランダムに生成する。ただし、i,j=1,…,10である。
【０１１４】
【数３０】
0005975961.tif 000031
【０１１５】
次に、双対直交基底生成部１２０は、次式に示すように基底Bを生成する。
【０１１６】
【数３１】
0005975961.tif 000032
【０１１７】
続いて、双対直交基底生成部１２０は、次式に示すように基底B*を生成する。
【０１１８】
【数３２】
0005975961.tif 000033
【０１１９】
そして、双対直交基底生成部１２０は、基底B:=(b1,…,b10)を用いて基底B^:=(b1,b2,b3,b10)を生成する。
【０１２０】
ステップＳ１２５において、電子透かし鍵生成装置１０の備える鍵ペア生成部１２５は、公開鍵pk:=(paramV,B^,Samp)を生成する。ここで、Sampは双対ペアリングベクトル空間のパラメータを用いて損失落とし戸関数の関数インデックスを生成する関数鍵生成アルゴリズムである。第一実施形態に係る関数鍵生成アルゴリズムSampについての詳細は後述する。
【０１２１】
そして、鍵ペア生成部１２５は、基底B*:=(b*1,…,b*10)を用いて秘密鍵sk:=(b*1,b*2,b*3,b*6,b*7)を生成する。
【０１２２】
ステップＳ１３０において、電子透かし鍵生成装置１０の備える埋込鍵生成部１３０は、基底B*:=(b*1,…,b*10)を用いて埋込鍵mk:=(b*8,b*9)を生成する。
【０１２３】
ステップＳ１３５において、電子透かし鍵生成装置１０の備える検出鍵生成部１３５は、基底B:=(b1,…,b10)を用いて検出鍵dk:=(b8,b9)を生成する。
【０１２４】
ステップＳ１４０において、電子透かし鍵生成装置１０の備える除去鍵生成部１４０は、正則行列Xを用いて除去鍵rk:=X=(χi,j)（i,j=1,…,10）を生成する。
【０１２５】
ステップＳ１４５において、電子透かし鍵生成装置１０の備える透かし鍵配信部１４５は、生成した公開鍵pk:=(paramV,B^,Samp)、埋込鍵mk:=(b*8,b*9)、検出鍵dk:=(b8,b9)及び除去鍵rk:=Xを各装置に配信する。図１１に電子透かし鍵生成装置１０が生成した電子透かし鍵を配信する動作例を示す。公開鍵pkは電子透かし埋込装置２０、電子透かし検出装置３０及び電子透かし除去装置４０に配信される。埋込鍵mkは電子透かし埋込装置２０に配信される。検出鍵dkは電子透かし検出装置３０に配信される。除去鍵rkは電子透かし除去装置４０に配信される。
【０１２６】
電子透かし埋込装置２０は、配信された公開鍵pk及び埋込鍵mkを埋込鍵記憶部２９０へ記憶する。電子透かし検出装置３０は、配信された公開鍵pk及び検出鍵dkを検出鍵記憶部３９０へ記憶する。電子透かし除去装置４０は、配信された公開鍵pk及び除去鍵rkを除去鍵記憶部４９０へ記憶する。
【０１２７】
ステップＳ１５０において、電子透かし鍵生成装置１０の備える単射鍵生成部１５０は、ベクトル空間パラメータparamV、基底B^及び秘密鍵skを入力として関数鍵生成アルゴリズムSampを実行し、関数鍵ek及び逆関数鍵ikを生成する。このとき、出力された関数鍵ekを単射鍵ekIとする。
【０１２８】
第一実施形態に係る関数鍵生成アルゴリズムSampは、以下のように関数鍵ek及び逆関数鍵ikを生成する。まず、任意のビット列ID∈{0,1}*を選択し、有限体Fq上のγ次元ベクトルψを次式に示すようにランダムに生成する。
【０１２９】
【数３３】
0005975961.tif 000034
【０１３０】
次に、j=1,…,γについて、次式に示すようにgT_jを計算する。
【０１３１】
【数３４】
0005975961.tif 000035
【０１３２】
続いて、i=1,…,γについて、有限体Fq上の乱数ζi,φi,ωiを次式に示すように生成する。
【０１３３】
【数３５】
0005975961.tif 000036
【０１３４】
次に、i,j=1,…,γについて、行列ui,j及び行列υiを次式に示すように計算する。
【０１３５】
【数３６】
0005975961.tif 000037
【０１３６】
ただし、行列ui,jを生成する際に用いる行列mi,j（i,j=1,…,γ）は単位行列である。すなわち、mi,j=1（i=j）かつmi,j=0（i≠j）とする。
【０１３７】
次に、有限体Fq上の乱数σ及び有限体Fq上の2次元ベクトルη→を次式に示すようにランダムに生成する。
【０１３８】
【数３７】
0005975961.tif 000038
【０１３９】
次に、ビット列ID、乱数σ、ベクトルη→及び基底B*を用いて次式に示すように値kIDを生成する。
【０１４０】
【数３８】
0005975961.tif 000039
【０１４１】
そして、関数鍵生成アルゴリズムSampは、関数鍵ekを次式に示すように設定する。
【０１４２】
【数３９】
0005975961.tif 000040
【０１４３】
ここで、{ui,j}i,jは(u1,1,…,uγ,γ)を表し、{υi}iは(υ1,…,υγ)を表す。これを行列で表現すると、次式に示すように表すことができる。
【０１４４】
【数４０】
0005975961.tif 000041
【０１４５】
また、関数鍵生成アルゴリズムSampは、逆関数鍵ikをik:=ψと設定する。
【０１４６】
ステップＳ１５５において、電子透かし鍵生成装置１０の備える損失鍵生成部１５５は、単射鍵生成部１５０と同様に、関数鍵生成アルゴリズムSampを実行することで、損失鍵ekL及び逆関数ikを生成する。ただし、関数鍵生成アルゴリズムSampにおいて、行列ui,jを生成する際に用いる行列mi,j（i,j=1,…,γ）はゼロ行列に設定する。すなわち、すべてのi,jについてmi,j=0である。また、逆関数ikはik:=⊥が設定される。損失関数は逆関数を計算できないためである。
【０１４７】
ステップＳ１６０において、電子透かし鍵生成装置１０の備える関数鍵配信部１６０は、生成した単射鍵ekI若しくは損失鍵ekL及び逆関数鍵ikを各装置に配信する。図１１に電子透かし鍵生成装置１０が生成した関数鍵を配信する動作例を示す。単射鍵ekI若しくは損失鍵ekLは電子透かし埋込装置２０に配信される。逆関数鍵ikは関数実行装置５０に配信される。電子透かしを埋め込まずに損失落とし戸関数LTFを利用したい場合には、単射鍵ekI若しくは損失鍵ekLを関数実行装置５０に配信してもよい。
【０１４８】
電子透かし埋込装置２０は、配信された単射鍵ekI若しくは損失鍵ekLを埋込鍵記憶部２９０へ記憶する。関数実行装置５０は、配信された逆関数鍵ikを関数鍵記憶部５９０へ記憶する。また、関数実行装置５０は、単射鍵ekI若しくは損失鍵ekLが配信された場合には、その単射鍵ekI若しくは損失鍵ekLを関数鍵記憶部５９０へ記憶する。
【０１４９】
＜電子透かし埋込処理＞
図９（Ａ）を参照して、電子透かし埋込装置２０が実行する電子透かし埋込処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１５０】
上述の通り、電子透かし埋込装置２０の備える埋込鍵記憶部２９０には、電子透かし鍵生成装置１０が生成した公開鍵pk及び埋込鍵mkが記憶されている。
【０１５１】
ステップＳ２１１において、電子透かし埋込装置２０の備える電子透かし埋込部２１０は、埋込対象関数鍵ekを入力として、埋込鍵記憶部２９０に記憶されている公開鍵pk及び埋込鍵mkを用いて、透かし付関数鍵WM(ek)を出力する。埋込対象関数鍵ekは、電子透かし鍵生成装置１０により生成された単射鍵ekI若しくは損失鍵ekLであり、次式に示すように表すことができる。
【０１５２】
【数４１】
0005975961.tif 000042
【０１５３】
まず、電子透かし埋込部２１０は、有限体Fq上の乱数μ1,μ2を選択する。
【０１５４】
【数４２】
0005975961.tif 000043
【０１５５】
次に、電子透かし埋込部２１０は、埋込対象関数鍵ekに含まれる値kID、乱数μ1,μ2及び基底B*を用いて、次式に示すように値k~IDを計算する。
【０１５６】
【数４３】
0005975961.tif 000044
【０１５７】
ステップＳ２１２において、電子透かし埋込部２１０は、透かし付関数鍵WM(ek)を次式に示すように出力する。
【０１５８】
【数４４】
0005975961.tif 000045
【０１５９】
＜電子透かし検出処理＞
図９（Ｂ）を参照して、電子透かし検出装置３０が実行する電子透かし検出処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１６０】
上述の通り、電子透かし検出装置３０の備える検出鍵記憶部３９０には、電子透かし鍵生成装置１０が生成した公開鍵pk及び検出鍵dkが記憶されている。
【０１６１】
ステップＳ３１１において、電子透かし検出装置３０の備える電子透かし検出部３１０は、検出対象関数鍵ek’を入力として、検出鍵記憶部３９０に記憶されている公開鍵pk及び検出鍵dkを用いて、検出対象関数鍵ek’に電子透かしが埋め込まれているか否かを示す情報を出力する。検出対象関数鍵ek’は、電子透かし鍵生成装置１０により生成された電子透かしが埋め込まれていない単射鍵ekI若しくは損失鍵ekL又は電子透かし埋込装置２０により電子透かしが埋め込まれた透かし付関数鍵WM(ek)であり、次式に示すように表すことができる。
【０１６２】
【数４５】
0005975961.tif 000046
【０１６３】
まず、電子透かし検出部３１０は、有限体Fqの乗法群Fq×上の乱数δ1,δ2を選択する。
【０１６４】
【数４６】
0005975961.tif 000047
【０１６５】
次に、電子透かし検出部３１０は、検出鍵dk:=(b8,b9)及び乱数δ1,δ2を用いて、次式に示すように値cを計算する。
【０１６６】
【数４７】
0005975961.tif 000048
【０１６７】
そして、電子透かし検出部３１０は、検出対象関数鍵ek’に含まれる値k~ID及び値cを用いて、次式に示すように値Δを計算する。
【０１６８】
【数４８】
0005975961.tif 000049
【０１６９】
ステップＳ３１２において、電子透かし検出装置３０の備える電子透かし検出部３１０は、値Δを検証し、検証結果を出力する。具体的には、Δ≠1であれば、電子透かしが埋め込まれていることを示す情報として、例えば「true」を出力する。Δ=1であれば、電子透かしが埋め込まれていないことを示す情報として、例えば「false」を出力する。
【０１７０】
＜電子透かし除去処理＞
図９（Ｃ）を参照して、電子透かし除去装置４０が実行する電子透かし除去処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１７１】
上述の通り、電子透かし除去装置４０の備える除去鍵記憶部４９０には、電子透かし鍵生成装置１０が生成した公開鍵pk及び除去鍵rkが記憶されている。
【０１７２】
ステップＳ４１１において、電子透かし除去装置４０の備える電子透かし除去部４１０は、除去対象関数鍵ek”を入力として、除去鍵記憶部４９０に記憶されている公開鍵pk及び除去鍵rkを用いて、除去済関数鍵ek^を出力する。除去対象関数鍵ek”は、電子透かし埋込装置２０により電子透かしが埋め込まれた透かし付関数鍵WM(ek)であり、次式に示すように表すことができる。
【０１７３】
【数４９】
0005975961.tif 000050
【０１７４】
まず、電子透かし除去部４１０は、除去鍵rk:=X=(χi,j)及び基底Bを用いて、ベクトル分解アルゴリズムDecomp(υ,(b1,…,bβ),X,B)を実行し、i=1,…,10について、次式を満たすzib*i（zi∈Fq）を出力する。
【０１７５】
【数５０】
0005975961.tif 000051
【０１７６】
ベクトル分解アルゴリズムDecompは、(υ,(b1,…,bβ),X,B)を入力にとり、次式により定義される値を出力する。
【０１７７】
【数５１】
0005975961.tif 000052
【０１７８】
ただし、次式が成り立つ。
【０１７９】
【数５２】
0005975961.tif 000053
【０１８０】
ここで、γ2はγ1より小さい任意の整数なので最小のγ2から順にベクトルを分解すれば、すべてのiに対してxibiを計算できる。
【０１８１】
ベクトル分解アルゴリズム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.（参考文献７）」に記載のアルゴリズムをそのまま利用することが可能である。参考文献７に記載のアルゴリズムを以下に示す。
【０１８２】
【数５３】
0005975961.tif 000054
【０１８３】
ここで、prjiは、以下の通りである。A:=(a1,…,aN)をベクトル空間Vの標準基底とし、ベクトルaiはFの固有値νiをもつ。Fの多項式prjj:=(Πi≠j(νj-νi))-1Πi≠j(F-νi)は標準基底Aに関するj番目の射影演算である。つまり、к≠jに対してはprjj(aк)=0であり、к=jに対してはprjj(aj)=ajである。
【０１８４】
そして、電子透かし除去部４１０は、次式に示すようにkIDを計算する。
【０１８５】
【数５４】
0005975961.tif 000055
【０１８６】
ステップＳ４１２において、電子透かし除去装置４０の備える電子透かし除去部４１０は、次式に示すように除去済関数鍵ek^を出力する。
【０１８７】
【数５５】
0005975961.tif 000056
【０１８８】
＜関数実行処理＞
図１０を参照して、関数実行装置５０が実行する関数実行処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１８９】
上述の通り、関数実行装置５０の備える関数鍵記憶部５９０には、電子透かし鍵生成装置１０が生成した透かし付関数鍵WM(ek)及び逆関数鍵ikが記憶されている。
【０１９０】
ステップＳ５１０において、関数実行装置５０の備える関数実行部５１０は、計算対象の情報x∈{0,1}γを入力として、関数鍵記憶部５９０に記憶されている透かし付関数鍵WM(ek)を用いて損失落とし戸関数LTFの計算アルゴリズムEvalを実行することで、計算結果である情報y:=(y1,…,yγ,y'γ+1)を出力する。
【０１９１】
まず、計算アルゴリズムEvalは、x:=(x1,…,xγ)=x→として、j=1,…,γについて、次式に示すようにy1,…,yγ+1を計算する。
【０１９２】
【数５６】
0005975961.tif 000057
【０１９３】
ただし、ζ→:=(ζ1,…,ζγ)、ω→:=(ω1,…,ωγ)及びφ→:=(φ1,…,φγ)である。次に、計算アルゴリズムEvalは、次式に示すように値y'γ+1を計算する。
【０１９４】
【数５７】
0005975961.tif 000058
【０１９５】
そして、関数実行部５１０は、情報y:=(y1,…,yγ,y'γ+1)を出力する。
【０１９６】
＜逆関数実行処理＞
図１０を参照して、関数実行装置５０が実行する逆関数実行処理の動作例を実際に行われる手続きの順に従って詳細に説明する。
【０１９７】
上述の通り、関数実行装置５０の備える関数鍵記憶部５９０には、電子透かし鍵生成装置１０が生成した透かし付関数鍵WM(ek)及び逆関数鍵ikが記憶されている。
【０１９８】
ステップＳ５２０において、関数実行装置５０の備える逆関数実行部５２０は、逆計算対象の情報y:=(y1,…,yγ,y'γ+1)を入力として、関数鍵記憶部５９０に記憶されている逆関数鍵ikを用いて損失落とし戸関数LTFの逆計算アルゴリズムInvertを実行することで、逆計算結果である情報x:=(x1,…,xγ)を出力する。
【０１９９】
逆計算アルゴリズムInvertは、i,j:=1,…,γについて、次式に示すようにx'jを計算する。
【０２００】
【数５８】
0005975961.tif 000059
【０２０１】
次に、j=1,…,γについて、x'j=gTx_jを満たす値となるように、xj∈{0,1}を設定する。
【０２０２】
そして、逆関数実行部５２０は、情報x:=(x1,…,xγ)を出力する。
【０２０３】
［第二実施形態］
以降の説明では、第一実施形態と相違する点を中心に説明し、第一実施形態と同様の部分については説明を省略する。
【０２０４】
第二実施形態の電子透かしシステムの機能構成及び処理フローは第一実施形態と同様である。したがって、以降では第一実施形態に係る図４から図１０を参照しながら説明をする。
【０２０５】
＜鍵生成処理＞
図８に示すステップＳ１２０において、電子透かし鍵生成装置１０の備える双対直交基底生成部１２０は、ベクトル空間パラメータparamV:=(q,V,GT,A,e,gT)を用いて、ベクトル空間Vの基底D,D*,D^を生成する。まず、双対直交基底生成部１２０は、次式に示すように8次元一般線形群GL(8,Fq)から正則行列Xをランダムに生成する。ただし、i,j=1,…,8である。
【０２０６】
【数５９】
0005975961.tif 000060
【０２０７】
次に、双対直交基底生成部１２０は、次式に示すように基底Dを生成する。
【０２０８】
【数６０】
0005975961.tif 000061
【０２０９】
続いて、双対直交基底生成部１２０は、次式に示すように基底D*を生成する。
【０２１０】
【数６１】
0005975961.tif 000062
【０２１１】
そして、双対直交基底生成部１２０は、基底D:=(d1,…,d8)を用いて基底D^:=(d1,d2,d3,d4)を生成する。
【０２１２】
ステップＳ１２５において、電子透かし鍵生成装置１０の備える鍵ペア生成部１２５は、公開鍵pk:=(paramV,D^,Samp)を生成する。ここで、Sampは双対ペアリングベクトル空間のパラメータを用いて損失落とし戸関数の関数インデックスを生成する関数鍵生成アルゴリズムである。第二実施形態に係る関数鍵生成アルゴリズムSampについての詳細は後述する。
【０２１３】
そして、鍵ペア生成部１２５は、有限体Fqから乱数α,θ,σを選択し、g^T:=e(d1,d*1)αθとして、秘密鍵sk:=(αθd*1,θd*1,θd*2,σd*3,σd*4)を生成する。
【０２１４】
ステップＳ１３０において、電子透かし鍵生成装置１０の備える埋込鍵生成部１３０は、基底D*:=(d*1,…,d*8)を用いて埋込鍵mk:=(d*7,d*8)を生成する。
【０２１５】
ステップＳ１３５において、電子透かし鍵生成装置１０の備える検出鍵生成部１３５は、基底D:=(d1,…,d8)を用いて検出鍵dk:=(d7,d8)を生成する。
【０２１６】
ステップＳ１４０において、電子透かし鍵生成装置１０の備える除去鍵生成部１４０は、正則行列Xを用いて除去鍵rk:=X=(χi,j)（i,j=1,…,8）を生成する。
【０２１７】
ステップＳ１５０において、電子透かし鍵生成装置１０の備える単射鍵生成部１５０は、ベクトル空間パラメータparamV、基底D^及び秘密鍵skを入力として関数鍵生成アルゴリズムSampを実行し、関数鍵ek及び逆関数鍵ikを生成する。このとき、出力された関数鍵ekを単射鍵ekIとする。
【０２１８】
第二実施形態に係る関数鍵生成アルゴリズムSampは、以下のように関数鍵ek及び逆関数鍵ikを生成する。まず、任意のビット列ID∈{0,1}*を選択し、有限体Fq上のγ次元ベクトルψを次式に示すように生成する。
【０２１９】
【数６２】
0005975961.tif 000063
【０２２０】
次に、基底D,D*、乱数α,θを用いて、次式に示すようにg^Tを計算する。
【０２２１】
【数６３】
0005975961.tif 000064
【０２２２】
次に、j=1,…,γについて、次式に示すようにgT_jを計算する。
【０２２３】
【数６４】
0005975961.tif 000065
【０２２４】
続いて、i=1,…,γについて、有限体Fq上の値si,1,si,2を次式に示すように生成する。
【０２２５】
【数６５】
0005975961.tif 000066
【０２２６】
次に、i,j=1,…,γについて、行列ui,j及び行列υiを次式に示すように計算する。
【０２２７】
【数６６】
0005975961.tif 000067
【０２２８】
ただし、行列ui,jを生成する際に用いる行列mi,j（i,j=1,…,γ）は単位行列である。すなわち、mi,j=1（i=j）かつmi,j=0（i≠j）とする。
【０２２９】
次に、有限体Fq上の乱数r1,r2を選択する。
【０２３０】
【数６７】
0005975961.tif 000068
【０２３１】
次に、ビット列ID、乱数α,θ,σ,r1,r2及び基底D*を用いて、次式に示すように値kIDを生成する。
【０２３２】
【数６８】
0005975961.tif 000069
【０２３３】
そして、関数鍵生成アルゴリズムSampは、関数鍵ekを次式に示すように設定する。
【０２３４】
【数６９】
0005975961.tif 000070
【０２３５】
また、関数鍵生成アルゴリズムSampは、逆関数鍵ikをik:=ψと設定する。
【０２３６】
＜電子透かし埋込処理＞
図９（Ａ）に示すステップＳ２１１において、電子透かし埋込装置２０の備える電子透かし埋込部２１０は、埋込対象関数鍵ekを入力として、埋込鍵記憶部２９０に記憶されている公開鍵pk及び埋込鍵mkを用いて、透かし付関数鍵WM(ek)を出力する。埋込対象関数鍵ekは、電子透かし鍵生成装置１０により生成された単射鍵ekI若しくは損失鍵ekLであり、次式に示すように表すことができる。
【０２３７】
【数７０】
0005975961.tif 000071
【０２３８】
まず、電子透かし埋込部２１０は、有限体Fq上の乱数t1,t2を選択する。
【０２３９】
【数７１】
0005975961.tif 000072
【０２４０】
次に、電子透かし埋込部２１０は、埋込対象関数鍵ekに含まれる値kID、乱数t1,t2及び基底D*を用いて、次式に示すように値k~IDを計算する。
【０２４１】
【数７２】
0005975961.tif 000073
【０２４２】
ステップＳ２１２において、電子透かし埋込部２１０は、透かし付関数鍵WM(ek)を次式に示すように出力する。
【０２４３】
【数７３】
0005975961.tif 000074
【０２４４】
＜電子透かし検出処理＞
図９（Ｂ）に示すステップＳ３１１において、電子透かし検出装置３０の備える電子透かし検出部３１０は、検出対象関数鍵ek’を入力として、検出鍵記憶部３９０に記憶されている公開鍵pk及び検出鍵dkを用いて、検出対象関数鍵ek’に電子透かしが埋め込まれているか否かを示す情報を出力する。検出対象関数鍵ek’は、電子透かし鍵生成装置１０により生成された電子透かしが埋め込まれていない単射鍵ekI若しくは損失鍵ekL又は電子透かし埋込装置２０により電子透かしが埋め込まれた透かし付関数鍵WM(ek)であり、次式に示すように表すことができる。
【０２４５】
【数７４】
0005975961.tif 000075
【０２４６】
まず、電子透かし検出部３１０は、有限体Fqの乗法群Fq×上の乱数z1,z2を選択する。
【０２４７】
【数７５】
0005975961.tif 000076
【０２４８】
次に、電子透かし検出部３１０は、検出鍵dk:=(d7,d8)及び乱数z1,z2を用いて、次式に示すように値cを計算する。
【０２４９】
【数７６】
0005975961.tif 000077
【０２５０】
そして、電子透かし検出部３１０は、検出対象関数鍵ek’に含まれるk~ID及び値cを用いて、次式に示すように値Δを計算する。
【０２５１】
【数７７】
0005975961.tif 000078
【０２５２】
ステップＳ３１２において、電子透かし検出装置３０の備える電子透かし検出部３１０は、値Δを検証し、検証結果を出力する。具体的には、Δ≠1であれば、電子透かしが埋め込まれていることを示す情報として、例えば「true」を出力する。Δ=1であれば、電子透かしが埋め込まれていないことを示す情報として、例えば「false」を出力する。
【０２５３】
＜電子透かし除去処理＞
図９（Ｃ）に示すステップＳ４１１において、電子透かし除去装置４０の備える電子透かし除去部４１０は、除去対象関数鍵ek”を入力として、除去鍵記憶部４９０に記憶されている公開鍵pk及び除去鍵rkを用いて、除去済関数鍵ek^を出力する。除去対象関数鍵ek”は、電子透かし埋込装置２０により電子透かしが埋め込まれた透かし付関数鍵WM(ek)であり、次式に示すように表すことができる。
【０２５４】
【数７８】
0005975961.tif 000079
【０２５５】
まず、電子透かし除去部４１０は、除去鍵rk:=X=(χi,j)及び基底Dを用いて、上述のベクトル分解アルゴリズムDecomp(υ,(d1,…,dβ),X,D)を実行し、i=1,…,8について、次式を満たすzid*i（zi∈Fq）を出力する。
【０２５６】
【数７９】
0005975961.tif 000080
【０２５７】
そして、電子透かし除去部４１０は、次式に示すようにkIDを計算する。
【０２５８】
【数８０】
0005975961.tif 000081
【０２５９】
ステップＳ４１２において、電子透かし除去装置４０の備える電子透かし除去部４１０は、次式に示すように除去済関数鍵ek^を出力する。
【０２６０】
【数８１】
0005975961.tif 000082
【０２６１】
＜関数実行処理＞
図１０に示すステップＳ５１０において、関数実行装置５０の備える関数実行部５１０は、計算対象の情報x∈{0,1}γを入力として、関数鍵記憶部５９０に記憶されている透かし付関数鍵WM(ek)を用いて損失落とし戸関数LTFの計算アルゴリズムEvalを実行することで、計算結果である情報y:=(y1,…,yγ,y'γ+1)を出力する。
【０２６２】
まず、計算アルゴリズムEvalは、x:=(x1,…,xγ)=x→として、i,j=1,…,γについて、次式に示すようにy1,…,yγ+1を計算する。
【０２６３】
【数８２】
0005975961.tif 000083
【０２６４】
ただし、s→1:=(s1,1,…,s1,γ)及びs→2:=(s2,1,…,s2,γ)である。次に、計算アルゴリズムEvalは、次式に示すように値y'γ+1を計算する。
【０２６５】
【数８３】
0005975961.tif 000084
【０２６６】
そして、関数実行部５１０は、情報y:=(y1,…,yγ,y'γ+1)を出力する。
【０２６７】
＜逆関数実行処理＞
図１０に示すステップＳ５２０において、関数実行装置５０の備える逆関数実行部５２０は、逆計算対象の情報y:=(y1,…,yγ,y'γ+1)を入力として、関数鍵記憶部５９０に記憶されている逆関数鍵ikを用いて損失落とし戸関数LTFの逆計算アルゴリズムInvertを実行することで、逆計算結果である情報x:=(x1,…,xγ)を出力する。
【０２６８】
逆計算アルゴリズムInvertは、i,j:=1,…,γについて、次式に示すようにx'jを計算する。
【０２６９】
【数８４】
0005975961.tif 000085
【０２７０】
次に、j=1,…,γについて、x'j=g^Tx_jを満たす値となるように、xj∈{0,1}を設定する。
【０２７１】
そして、逆関数実行部５２０は、情報x:=(x1,…,xγ)を出力する。
【０２７２】
［この発明と従来技術との比較］
図１２に、この発明の電子透かし技術と従来技術との比較を示す。“方式”列は、この明細書における文献の名称を表す。“タイプ”列は、それぞれの方式が目的としている技術の種類を表す。“対象”列は、それぞれの方式で著作権や電子透かしを処理する対象となる関数の種類を表す。“仮定”列は、それぞれの方式が安全性の根拠とする暗号学的な仮定を表す。“安全性”列は、それぞれの方式の安全性における特徴を表す。
【０２７３】
非特許文献１及び非特許文献２は関数に対する著作権付与の方式であり、付与回数が限定されている。非特許文献３は関数に対する電子透かしの方式であるが、暗号学的に証明可能な安全性を有していない。このように、付与回数の限定がなく暗号学的に証明可能な安全性を有している電子透かし方式は、この発明のみが実現していることがわかる。
【０２７４】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０２７５】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０２７６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなど、周知のどのような記録媒体であってもよい。
【０２７７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体を販売、譲渡、貸与などすることによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２７８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラム若しくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータなど）を含むものとする。
【０２７９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０２８０】
１  電子透かしシステム
９  ネットワーク
１０  電子透かし鍵生成装置
２０  電子透かし埋込装置
３０  電子透かし検出装置
４０  電子透かし除去装置
５０  関数実行装置
１１０  双線形写像パラメータ生成部
１１５  ベクトル空間パラメータ生成部
１２０  双対直交基底生成部
１２５  鍵ペア生成部
１３０  埋込鍵生成部
１３５  検出鍵生成部
１４０  除去鍵生成部
１４５  透かし鍵配信部
１５０  単射鍵生成部
１５５  損失鍵生成部
１６０  関数鍵配信部
２１０  電子透かし埋込部
２９０  埋込鍵記憶部
３１０  電子透かし検出部
３９０  検出鍵記憶部
４１０  電子透かし除去部
４９０  除去鍵記憶部
５１０  関数実行部
５２０  逆関数実行部
５９０  関数鍵記憶部
【図１】
0005975961.tif 000117
【図２】
0005975961.tif 000118
【図３】
0005975961.tif 000119
【図４】
0005975961.tif 000120
【図５】
0005975961.tif 000121
【図６】
0005975961.tif 000122
【図７】
0005975961.tif 000123
【図８】
0005975961.tif 000124
【図９】
0005975961.tif 000125
【図１０】
0005975961.tif 000126
【図１１】
0005975961.tif 000127
【図１２】
0005975961.tif 000128