(57)【特許請求の範囲】
【請求項１】
送信者装置，委託装置，受託装置，プロキシ装置を含むプロキシ暗号システムであって，
（１）共通パラメータ生成アルゴリズムSetup：
セキュリティパラメータκを入力として，共通パラメータppを出力する確率的アルゴリズム，
（２）鍵生成アルゴリズムGen：
セキュリティパラメータκと共通パラメータppを入力として，暗号化鍵と復号鍵の組(ek，dk)を出力する確率的アルゴリズム，
（３）暗号化アルゴリズムEnc：
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek，平文mを入力として，乱数rを任意に選択し，暗号文cを出力する確率的アルゴリズム，
（４）復号アルゴリズムDec：
セキュリティパラメータκ，共通パラメータpp，復号鍵dk，暗号文cを入力として，平文mを得るアルゴリズム，
（５）変換鍵生成アルゴリズムReKeyGen：
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA，受託装置の暗号化鍵ekBを入力として，変換鍵rkA→Bを出力する確率的アルゴリズム，
（６）変換アルゴリズムReEnc：
セキュリティパラメータκ，共通パラメータpp，変換鍵rkA→B，委託装置の公開鍵ekAを用いて生成された暗号文cAを入力として，受託装置の復号鍵dkBで復号可能な暗号文cBを出力する確率的アルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に基づくプロキシ暗号アルゴリズムπ=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を，
（１）SETUP:
セキュリティパラメータκを入力として，pp←Setup(κ)を求め，Hを変換回数の最大として，PP=(pp，H)を出力するアルゴリズム，
（２）GEN:
セキュリティパラメータκとPP=(pp，H)を入力として，η=0，…，Hについて，(ek(η)，dk(η))←Gen(κ，pp)を求め，暗号化鍵の組EK=(ek(0)，…，ek(H))と復号鍵の組DK=(dk(0)，…，dk(H))を出力するアルゴリズム，
（３）ENC:
セキュリティパラメータκ，PP=(pp，H)，暗号化鍵の組EK=(ek(0)，…，ek(H))，レベルη，平文mを入力として，c←Enc(κ，pp，ek(η)，m)を求め，ct=(η，c)を暗号文として出力するアルゴリズム，
（４）DEC:
セキュリティパラメータκ，PP=(pp，H)，復号鍵の組DK=(dk(0)，…，dk(H))，暗号文(η，c)を入力として，m’←Dec(κ，pp，dk(η)，c)を求め，復号された平文としてm’を出力するアルゴリズム，
（５）REKEYGEN:
セキュリティパラメータκ，PP=(pp，H)，委託装置の復号鍵の組DKA=(dkA(0)，…，dkA(H))，受託装置の暗号化鍵の組EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，rk(A,h)→(B,h+1)←ReKeyGen(κ，pp，dkA(h)，ekB(h+1))を計算し，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力するアルゴリズム，
（６）REENC:
セキュリティパラメータκ，PP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，暗号文ct=(η，c)を入力として，c’←ReEnc(κ，pp，rk(A,η)→(B,η+1)，c)を求め，(η+1，c’)を変換済暗号文として出力するアルゴリズム，
として，
送信者装置は，
上記SETUPアルゴリズムを実行する設定部と，
EK=(ek(0)，…，ek(H))として委託装置の暗号化鍵の組EKA=(ekA(0)，…，ekA(H))を用いて上記ENCアルゴリズムを実行する暗号化部と
を含み，
委託装置は，
上記GENアルゴリズムを実行して，暗号化鍵の組EKA=(ekA(0)，…，ekA(H))と復号鍵の組DKA=(dkA(0)，…，dkA(H))を得る鍵生成部と，
上記REKEYGENを実行する変換鍵生成部と
を含み，
受託装置は，
上記GENアルゴリズムを実行して，暗号化鍵の組EKB=(ekB(0)，…，ekB(H))と復号鍵の組DKB=(dkB(0)，…，dkB(H))を得る鍵生成部と，
DK=(dk(0)，…，dk(H))として受託装置の復号鍵の組DKB=(dkB(0)，…，dkB(H))用い，暗号文(η，c)として変換済暗号文(η+1，c’)を用いて上記DECを実行する復号部とを含み，
プロキシ装置は，
上記REENCを実行する変換暗号文生成部
を含むプロキシ暗号システム。
【請求項２】
請求項１に記載のプロキシ暗号システムにおいて，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，（１）Setup：
セキュリティパラメータκを入力として，共通パラメータppを出力する確率的アルゴリズム，
（２）Gen：
セキュリティパラメータκと共通パラメータppを入力として，暗号化鍵と復号鍵の組(ek，dk)を出力する確率的アルゴリズム，
（３）Enc：
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek，平文mを入力として，乱数rを任意に選択し，暗号文cを出力する確率的アルゴリズム，
（４）Dec：
セキュリティパラメータκ，共通パラメータpp，復号鍵dk，暗号文cを入力として，平文mを得るアルゴリズム，
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA，平文mとしての受託装置の暗号化鍵ekBを入力として，cA→B←Enc(κ，pp，ekB，dkA)を求め，rkA→B=(cA→B，ekB)を出力するアルゴリズム，
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，rkA→B，暗号文cを入力として，c”←Eval(κ，pp，ekB，Dec，(cA→B，Enc(κ，pp，ekB，c)))を求め，c”を暗号文として出力するアルゴリズム（ただし，アルゴリズムEvalは，κ，pp，ek，論理回路C，任意のｎ個の暗号文の組c→=(c1，…，cn)を入力として，完全準同型公開鍵暗号アルゴリズムに基づく暗号文を求めるアルゴリズムである），
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号システム。
【請求項３】
請求項１に記載のプロキシ暗号システムにおいて，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，
アルゴリズムBDを，x→∈Zqnを入力として，k=1，…，δについて，u→k∈{0，1}nを，x→=Σk=1δ2k-1u→kを満たすように求め，(u→1，…，u→δ)∈{0，1}nδを出力するアルゴリズム，
アルゴリズムP2を，s→∈Znqを入力とする場合には，[1，2，…，2δ-1]T(×)s→∈Zqnδを出力するアルゴリズムPを実行し（(×)は行列のクロネッカー積を表す），行列S=[s→1，…，s→g]を入力とする場合には，[P(s→1)，…，P(s→g)]∈Zqnδ×gなる行列を出力するアルゴリズム，
として，
（１）Setup:
AをZqm×nからランダムに選び，共通パラメータpp=(1κ，n，q，m，DΧ，A)を出力するアルゴリズム，
（２）Gen:
セキュリティパラメータκ，共通パラメータppを入力として，SをZqn×nからランダムに選び，E∈Zqm×nを分布DΧnに従って選び，B=A・S+2Eを求め，暗号化鍵ek=Bと復号鍵dk=(S，B)を出力するアルゴリズム(以下，M=[A|B]∈Zqm×2n，S^=(-S|I)∈Zq2n×nと表記する)，
（３）Enc:
セキュリティパラメータκ，共通パラメータpp，ek=B，m→∈{0，1}nを入力として，r→←{-1，+1}mをランダムに選び，(u→，v→)=(r→A，r→B)を求め，さらに(u→，c→)=(u→，v→+m→)を求め，(u→，c→)を暗号文として出力するアルゴリズム，
（４）Dec:
セキュリティパラメータκ，共通パラメータpp，dk=(S，B)，暗号文(u→，c→)を入力として，d→←(u→，c→)S^ mod qを求め，さらにm→←d→ mod 2によって平文m→を出力するアルゴリズム，
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，dkA=(SA，BA)とekB=BBを入力として，R←{-1，+1}nδ×mをランダムに選び，MB=[A|BB]として，MA→B←RMB+[O|-P2(SA)]を求め，変換鍵rkA→B=(MA→B，BB)を出力するアルゴリズム，
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，rkA→B=(MA→B，BB)，暗号文(u→，c→)を入力として，(u→’，c→’)←BD(u→)・MA→Bを求め，r→~←{-1，+1}mをランダムに選び，(u→~，v→~)←r→~・[A|BB]を求め，(u→-，c→-)←(u→’+u→~，c→+c→’+v→~)を求め，変換済暗号文として(u→-，c→-)を出力するアルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号システム。
【請求項４】
請求項１に記載のプロキシ暗号システムにおいて，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，
k(κ)を整数関数，n(κ)=2k(κ)，f(x)=xn+1，q=q(κ)を素数，環R=Z[x]/(f(x))とし，Rq=R/qR，δを2δ-1<q<2δを満たす整数とし，
アルゴリズムBDを，x∈Rqを入力とし，k=1，…，δについて，uk∈{0，1}n⊆Rqを，x=Σk=1δ2k-1ukを満たすように求め，(u1，…，uδ)∈{0，1}nδ⊆Rqδを出力するアルゴリズム，
アルゴリズムP2を，s∈Rqを入力として，[1，2s，…，2δ-1s]T∈Rqδを出力するアルゴリズム，
として，
（１）Setup:
a→をRqmからランダムに選び，共通パラメータpp=(1κ，n，q，m，DΧ，a→)を出力するアルゴリズム，
（２）Gen:
セキュリティパラメータκ，共通パラメータppを入力として，sをRqからランダムに選び，e→←DΧmを選び，b→←sa→+2e→∈Rqmを求め，暗号化鍵ek=b→と復号鍵dk=(s，b→)を出力するアルゴリズム(以下，M=[a→|b→]∈Rqm×2，s→^=(-s，1)∈Rq2と表記する)，
（３）Enc:
セキュリティパラメータκ，共通パラメータpp，ek=b→，m∈{0，1}n⊆Rqを入力として，r→←({-1，+1}n)mをランダムに選び，(u，v)=(r→・a→，r→・b→)を求め，さらに(u，c)=(u，v+m)を求め，(u，c)を暗号文として出力するアルゴリズム，
（４）Dec:
セキュリティパラメータκ，共通パラメータpp，dk=(s，b→)，(u，c)を入力として，d←(u，c) s→^ mod q を求め，m←d mod 2によって平文mを出力するアルゴリズム，
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，dkA=(sA，b→A)とekB=b→Bを入力として，R←({-1，+1}n)δ×mをランダムに選び，MB=[a→|b→B]として，MA→B←RMB+[0→|-P2(sA)]を求め，変換鍵rkA→B=(MA→B，b→B)を出力するアルゴリズム，
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，rkA→B=(MA→B，b→B)，暗号文(u，c)を入力として，(u’，c’)←BD(u)・MA→Bを求め，r→~←({-1，+1}n)mをランダムに選び，(u~，v~)←r→~・[a→|b→B]を求め，(u-，c-)←(u’+u~，c+c’+v~)を求め，変換済暗号文として(u-，c-)を出力するアルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号システム。
【請求項５】
請求項１に記載のプロキシ暗号システムにおいて，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，
k(κ)を整数関数，n(κ)=2k(κ)，f(x)=xn+1，q=q(κ)を素数，環R=Z[x]/(f(x))とし，Rq=R/qR，δを2δ-1<q<2δを満たす整数とし，
アルゴリズムBDを，x∈Rqを入力とし，k=1，…，δについて，uk∈{0，1}n⊆Rqを，x=Σk=1δ2k-1ukを満たすように求め，(u1，…，uδ)∈{0，1}nδ⊆Rqδを出力するアルゴリズム，
アルゴリズムP2を，s∈Rqを入力として，[1，2s，…，2δ-1s]T∈Rqδを出力するアルゴリズム，
として，
（１）Setup:
a←Rq，共通パラメータpp=(κ，n，q，DΧ，a)を出力するアルゴリズム，
（２）Gen:
共通パラメータppを入力として，s，e←DΧとし，b←as+2eを求め，ek=b，dk=(s，b)を出力するアルゴリズム，
（３）Enc:
共通パラメータpp，ek=b，m∈{0，1}n∈Rqを入力として，t，e’，e”←DΧを選び，(u，c)←(at+2e’，bt+2e”+m)として暗号文(u，c)を出力するアルゴリズム，
（４）Dec:
共通パラメータpp，暗号文(u，c)を入力として，d=c-us mod qを求め，m=d mod 2によって平文mを出力するアルゴリズム，
（５）ReKeyGen:
共通パラメータpp，ekB=bB，dkA=(sA，bA)を入力として，r→，h→，h→’←DΧδを選び，f→←ar→+2h→，g→←br→+2h→’+P2(sA)として，変換鍵rkA→B=(f→，g→，bB)を出力するアルゴリズム，
（６）ReEnc:
pp，rkA→B=(f→，g→，bB)，暗号文(u，c)を入力として，(u’，c’)=BD(u)・[f→，g→]を求め，t’，f’，f”←DΧを選び，(u~，v~)=(at’+2f’，bBt’+2f”)を求め，(u-，c-)=(u’+u~，c+c’+v~)を求め，(u-，c-)を暗号文として出力するアルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号システム。
【請求項６】
送信者装置，委託装置，受託装置，プロキシ装置を含むプロキシ暗号システムにおけるプロキシ暗号方法であって，
（１）共通パラメータ生成アルゴリズムSetup：
セキュリティパラメータκを入力として，共通パラメータppを出力する確率的アルゴリズム，
（２）鍵生成アルゴリズムGen：
セキュリティパラメータκと共通パラメータppを入力として，暗号化鍵と復号鍵の組(ek，dk)を出力する確率的アルゴリズム，
（３）暗号化アルゴリズムEnc：
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek，平文mを入力として，乱数rを任意に選択し，暗号文cを出力する確率的アルゴリズム，
（４）復号アルゴリズムDec：
セキュリティパラメータκ，共通パラメータpp，復号鍵dk，暗号文cを入力として，平文mを得るアルゴリズム，
（５）変換鍵生成アルゴリズムReKeyGen：
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA，受託装置の暗号化鍵ekBを入力として，変換鍵rkA→Bを出力する確率的アルゴリズム，
（６）変換アルゴリズムReEnc：
セキュリティパラメータκ，共通パラメータpp，変換鍵rkA→B，委託装置の公開鍵ekAを用いて生成された暗号文cAを入力として，受託装置の復号鍵dkBで復号可能な暗号文cBを出力する確率的アルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に基づくプロキシ暗号アルゴリズムπ=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を，
（１）SETUP:
セキュリティパラメータκを入力として，pp←Setup(κ)を求め，Hを変換回数の最大として，PP=(pp，H)を出力するアルゴリズム，
（２）GEN:
セキュリティパラメータκとPP=(pp，H)を入力として，η=0，…，Hについて，(ek(η)，dk(η))←Gen(κ，pp)を求め，暗号化鍵の組EK=(ek(0)，…，ek(H))と復号鍵の組DK=(dk(0)，…，dk(H))を出力するアルゴリズム，
（３）ENC:
セキュリティパラメータκ，PP=(pp，H)，暗号化鍵の組EK=(ek(0)，…，ek(H))，レベルη，平文mを入力として，c←Enc(κ，pp，ek(η)，m)を求め，ct=(η，c)を暗号文として出力するアルゴリズム，
（４）DEC:
セキュリティパラメータκ，PP=(pp，H)，復号鍵の組DK=(dk(0)，…，dk(H))，暗号文(η，c)を入力として，m’←Dec(κ，pp，dk(η)，c)を求め，復号された平文としてm’を出力するアルゴリズム，
（５）REKEYGEN:
セキュリティパラメータκ，PP=(pp，H)，委託装置の復号鍵の組DKA=(dkA(0)，…，dkA(H))，受託装置の暗号化鍵の組EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，rk(A,h)→(B,h+1)←ReKeyGen(κ，pp，dkA(h)，ekB(h+1))を計算し，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力するアルゴリズム，
（６）REENC:
セキュリティパラメータκ，PP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，暗号文ct=(η，c)を入力として，c’←ReEnc(κ，pp，rk(A,η)→(B,η+1)，c)を求め，(η+1，c’)を変換済暗号文として出力するアルゴリズム，
として，
送信者装置の設定部が，上記SETUPアルゴリズムを実行するステップと，
委託装置の鍵生成部が，上記GENアルゴリズムを実行して，暗号化鍵の組EKA=(ekA(0)，…，ekA(H))と復号鍵の組DKA=(dkA(0)，…，dkA(H))を得るステップと，
受託装置の鍵生成部が，上記GENアルゴリズムを実行して，暗号化鍵の組EKB=(ekB(0)，…，ekB(H))と復号鍵の組DKB=(dkB(0)，…，dkB(H))を得るステップと，
送信者装置の暗号化部が，EK=(ek(0)，…，ek(H))として委託装置の暗号化鍵の組EKA=(ekA(0)，…，ekA(H))を用いて上記ENCアルゴリズムを実行するステップと，
委託装置の変換鍵生成部が，上記REKEYGENを実行するステップと，
プロキシ装置の変換暗号文生成部が，上記REENCを実行するステップと，
受託装置の復号部が，DK=(dk(0)，…，dk(H))として受託装置の復号鍵の組DKB=(dkB(0)，…，dkB(H))用い，暗号文(η，c)として変換済暗号文(η+1，c’)を用いて上記DECを実行するステップと
を有するプロキシ暗号方法。
【請求項７】
請求項６に記載のプロキシ暗号方法において，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，（１）Setup：
セキュリティパラメータκを入力として，共通パラメータppを出力する確率的アルゴリズム，
（２）Gen：
セキュリティパラメータκと共通パラメータppを入力として，暗号化鍵と復号鍵の組(ek，dk)を出力する確率的アルゴリズム，
（３）Enc：
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek，平文mを入力として，乱数rを任意に選択し，暗号文cを出力する確率的アルゴリズム，
（４）Dec：
セキュリティパラメータκ，共通パラメータpp，復号鍵dk，暗号文cを入力として，平文mを得るアルゴリズム，
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA，平文mとしての受託装置の暗号化鍵ekBを入力として，cA→B←Enc(κ，pp，ekB，dkA)を求め，rkA→B=(cA→B，ekB)を出力するアルゴリズム，
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，rkA→B，暗号文cを入力として，c”←Eval(κ，pp，ekB，Dec，(cA→B，Enc(κ，pp，ekB，c)))を求め，c”を暗号文として出力するアルゴリズム（ただし，アルゴリズムEvalは，κ，pp，ek，論理回路C，任意のｎ個の暗号文の組c→=(c1，…，cn)を入力として，完全準同型公開鍵暗号アルゴリズムに基づく暗号文を求めるアルゴリズムである），
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号方法。
【請求項８】
請求項６に記載のプロキシ暗号方法において，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，
アルゴリズムBDを，x→∈Zqnを入力として，k=1，…，δについて，u→k∈{0，1}nを，x→=Σk=1δ2k-1u→kを満たすように求め，(u→1，…，u→δ)∈{0，1}nδを出力するアルゴリズム，
アルゴリズムP2を，s→∈Znqを入力とする場合には，[1，2，…，2δ-1]T(×)s→∈Zqnδを出力するアルゴリズムPを実行し（(×)は行列のクロネッカー積を表す），行列S=[s→1，…，s→g]を入力とする場合には，[P(s→1)，…，P(s→g)]∈Zqnδ×gなる行列を出力するアルゴリズム，
として，
（１）Setup:
AをZqm×nからランダムに選び，共通パラメータpp=(1κ，n，q，m，DΧ，A)を出力するアルゴリズム，
（２）Gen:
セキュリティパラメータκ，共通パラメータppを入力として，SをZqn×nからランダムに選び，E∈Zqm×nを分布DΧnに従って選び，B=A・S+2Eを求め，暗号化鍵ek=Bと復号鍵dk=(S，B)を出力するアルゴリズム(以下，M=[A|B]∈Zqm×2n，S^=(-S|I)∈Zq2n×nと表記する)，
（３）Enc:
セキュリティパラメータκ，共通パラメータpp，ek=B，m→∈{0，1}nを入力として，r→←{-1，+1}mをランダムに選び，(u→，v→)=(r→A，r→B)を求め，さらに(u→，c→)=(u→，v→+m→)を求め，(u→，c→)を暗号文として出力するアルゴリズム，
（４）Dec:
セキュリティパラメータκ，共通パラメータpp，dk=(S，B)，暗号文(u→，c→)を入力として，d→←(u→，c→)S^ mod qを求め，さらにm→←d→ mod 2によって平文m→を出力するアルゴリズム，
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，dkA=(SA，BA)とekB=BBを入力として，R←{-1，+1}nδ×mをランダムに選び，MB=[A|BB]として，MA→B←RMB+[O|-P2(SA)]を求め，変換鍵rkA→B=(MA→B，BB)を出力するアルゴリズム，
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，rkA→B=(MA→B，BB)，暗号文(u→，c→)を入力として，(u→’，c→’)←BD(u→)・MA→Bを求め，r→~←{-1，+1}mをランダムに
選び，(u→~，v→~)←r→~・[A|BB]を求め，(u→-，c→-)←(u→’+u→~，c→+c→’+v→~)を求め，変換済暗号文として(u→-，c→-)を出力するアルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号方法。
【請求項９】
請求項６に記載のプロキシ暗号方法において，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，
k(κ)を整数関数，n(κ)=2k(κ)，f(x)=xn+1，q=q(κ)を素数，環R=Z[x]/(f(x))とし，Rq=R/qR，δを2δ-1<q<2δを満たす整数とし，
アルゴリズムBDを，x∈Rqを入力とし，k=1，…，δについて，uk∈{0，1}n⊆Rqを，x=Σk=1δ2k-1ukを満たすように求め，(u1，…，uδ)∈{0，1}nδ⊆Rqδを出力するアルゴリズム，
アルゴリズムP2を，s∈Rqを入力として，[1，2s，…，2δ-1s]T∈Rqδを出力するアルゴリズム，
として，
（１）Setup:
a→をRqmからランダムに選び，共通パラメータpp=(1κ，n，q，m，DΧ，a→)を出力するアルゴリズム，
（２）Gen:
セキュリティパラメータκ，共通パラメータppを入力として，sをRqからランダムに選び，e→←DΧmを選び，b→←sa→+2e→∈Rqmを求め，暗号化鍵ek=b→と復号鍵dk=(s，b→)を出力するアルゴリズム(以下，M=[a→|b→]∈Rqm×2，s→^=(-s，1)∈Rq2と表記する)，
（３）Enc:
セキュリティパラメータκ，共通パラメータpp，ek=b→，m∈{0，1}n⊆Rqを入力として，r→←({-1，+1}n)mをランダムに選び，(u，v)=(r→・a→，r→・b→)を求め，さらに(u，c)=(u，v+m)を求め，(u，c)を暗号文として出力するアルゴリズム，
（４）Dec:
セキュリティパラメータκ，共通パラメータpp，dk=(s，b→)，(u，c)を入力として，d←(u，c) s→^ mod q を求め，m←d mod 2によって平文mを出力するアルゴリズム，
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，dkA=(sA，b→A)とekB=b→Bを入力として，R←({-1，+1}n)δ×mをランダムに選び，MB=[a→|b→B]として，MA→B←RMB+[0→|-P2(sA)]を求め，変換鍵rkA→B=(MA→B，b→B)を出力するアルゴリズム，
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，rkA→B=(MA→B，b→B)，暗号文(u，c)を入力として，(u’，c’)←BD(u)・MA→Bを求め，r→~←({-1，+1}n)mをランダムに選び，(u~，v~)←r→~・[a→|b→B]を求め，(u-，c-)←(u’+u~，c+c’+v~)を求め，変換済暗号文として(u-，c-)を出力するアルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号システム。
【請求項１０】
請求項６に記載のプロキシ暗号方法において，
上記再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)に替えて，再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を，
k(κ)を整数関数，n(κ)=2k(κ)，f(x)=xn+1，q=q(κ)を素数，環R=Z[x]/(f(x))とし，Rq=R/qR，δを2δ-1<q<2δを満たす整数とし，
アルゴリズムBDを，x∈Rqを入力とし，k=1，…，δについて，uk∈{0，1}n⊆Rqを，x=Σk=1δ2k-1ukを満たすように求め，(u1，…，uδ)∈{0，1}nδ⊆Rqδを出力するアルゴリズム，
アルゴリズムP2を，s∈Rqを入力として，[1，2s，…，2δ-1s]T∈Rqδを出力するアルゴリズム，
として，
（１）Setup:
a←Rq，共通パラメータpp=(κ，n，q，DΧ，a)を出力するアルゴリズム，
（２）Gen:
共通パラメータppを入力として，s，e←DΧとし，b←as+2eを求め，ek=b，dk=(s，b)を出力するアルゴリズム，
（３）Enc:
共通パラメータpp，ek=b，m∈{0，1}n∈Rqを入力として，t，e’，e”←DΧを選び，(u，c)←(at+2e’，bt+2e”+m)として暗号文(u，c)を出力するアルゴリズム，
（４）Dec:
共通パラメータpp，暗号文(u，c)を入力として，d=c-us mod qを求め，m=d mod 2によって平文mを出力するアルゴリズム，
（５）ReKeyGen:
共通パラメータpp，ekB=bB，dkA=(sA，bA)を入力として，r→，h→，h→’←DΧδを選び，f→←ar→+2h→，g→←br→+2h→’+P2(sA)として，変換鍵rkA→B=(f→，g→，bB)を出力するアルゴリズム，
（６）ReEnc:
共通パラメータpp，rkA→B=(f→，g→，bB)，暗号文(u，c)を入力として，(u’，c’)=BD(u)・[f→，g→]を求め，t’，f’，f”←DΧを選び，(u~，v~)=(at’+2f’，bBt’+2f”)を求め，(u-，c-)=(u’+u~，c+c’+v~)を求め，(u-，c-)を暗号文として出力するアルゴリズム，
で構成される再変換可能暗号アルゴリズムΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)とすることを特徴とするプロキシ暗号方法。
【請求項１１】
請求項１から請求項５のいずれかに記載のプロキシ暗号システムに含まれる委託装置。
【請求項１２】
請求項１から請求項５のいずれかに記載のプロキシ暗号システムに含まれるプロキシ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，或る公開鍵で暗号化された暗号文を，その公開鍵に対応する秘密鍵とは異なる秘密鍵を用いて復号することを可能とするプロキシ暗号技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式では，或る公開鍵で暗号化された暗号文を復号できるのは，対応する秘密鍵を有する者にのみ限られる。例えば，ユーザ装置hからユーザ装置iに平文mを送信する場合，ユーザ装置hはユーザ装置iの暗号化鍵ekiを用いて，暗号文ciを生成し，ユーザ装置iに暗号文ciを送信する。暗号化鍵ekiに対応する復号鍵dkiを持つユーザ装置のみがこの暗号文ciを復号できる。
【０００３】
加えて，変換鍵を用いて，その暗号文を，当該暗号文を生成したときに用いた秘密鍵とは異なる秘密鍵を用いて復号可能となる暗号文に変換する方式が，プロキシ暗号方式である。この方式は，復号権限を委譲するユーザ装置（delegator；委託装置），復号権限を委譲されるユーザ装置（delegatee；受託装置），委託装置で復号可能な暗号文を受託装置で復号可能な暗号文（変換済暗号文）に変換するプロキシ装置から構成される。例えば，ユーザ装置iがユーザ装置jに復号権限を委譲する場合，変換鍵rki,jを作成し，変換鍵rki,jによる再暗号化をプロキシ装置に委託する。変換鍵rki,jを持つプロキシ装置は，入力された暗号文ciを，変換鍵rki,jを用いて暗号文cjに変換して出力する。これによって，暗号化鍵ekjに対応する復号鍵dkjを持つユーザ装置は，この暗号文cjを復号し，平文mを得ることができる。変換鍵rki,jが，ユーザ装置iからユーザ装置jへの変換および，ユーザ装置jからユーザ装置iへの変換を許すとき，変換鍵は双方向であるという。変換鍵rki,jが，ユーザ装置iからユーザ装置jへの変換のみを許すとき，変換鍵は単方向であるという。
【０００４】
プロキシ暗号方式は，非特許文献１で初めて提案された。それ以降，離散対数問題や楕円離散対数問題に基づいて様々なプロキシ暗号方式が提案されている。格子問題に基づくプロキシ暗号方式として，非特許文献２および非特許文献３がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Matt Blaze, Gerrit Bleumer, and Martin Strauss. Divertible protocols and atomic proxy cryptography. In Kaisa Nyberg, editor, EUROCRYPT ’98, volume 1403 of Lecture Notes in Computer Science, pages 127-144. Springer-Verlag, 1998.
【非特許文献２】Keita Xagawa. 関連鍵攻撃に対する識別不可能性と双方向代理人再暗号化. SCIS 2011, 2011.
【非特許文献３】Keita Xagawa and Keisuke Tanaka. Proxy re-encryption based on learning with errors. SCIS 2010, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
変換鍵が単方向なプロキシ暗号方式では，一般に送信者が再暗号化の回数を制限できない。多くの方式は，一度のみの変換を許すものである。また，参考文献（Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. Available at http://crypto.stanford.edu/craig/）にある完全準同型暗号を用いた方式や，参考文献（Jun Shao, Peng Liu, Zhenfu Cao, and Guiyi Wei. Multi-use unidirectional proxy re-encryption. In ICC 2011, pages 1-5. IEEE, 2011.）の双線形写像を用いた方式は無制限の変換を許すため，送信者（装置）は変換回数を制限出来ない。
【０００７】
本発明は，送信者（装置）が再暗号化の回数を指定できるプロキシ暗号技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明のプロキシ暗号技術は，変換済暗号文を再び変換可能な暗号方式を用いることで，複数回の暗号化を実現し，この際，委託装置と受託装置のそれぞれが暗号化鍵と復号鍵の組を複数用意し，送信者装置が暗号文に変換回数に応じたラベルを付けることで，送信者装置が変換回数を指定できるようにした。
【発明の効果】
【０００９】
このため，本発明に拠れば，詳細は後述の実施形態に譲るが，送信者装置が再暗号化の回数を指定できる。
【図面の簡単な説明】
【００１０】
【図１】実施形態のプロキシ暗号システムを示す図。
【図２】実施形態に関わるプロキシ暗号システムの構成要素である送信者装置，委託装置，受託装置，プロキシ装置の機能構成を示す図。
【発明を実施するための形態】
【００１１】
[実施例1]
＜準備：再変換可能暗号＞
まず，再変換可能暗号方式Π=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を以下のとおり構成する。このΠ=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)は単一鍵変換可能暗号である。
（１）共通パラメータ生成アルゴリズムSetup：
セキュリティパラメータκを入力として，共通パラメータppを出力する確率的アルゴリズムである。
（２）鍵生成アルゴリズムGen：
セキュリティパラメータκと共通パラメータppを入力として，暗号化鍵と復号鍵の組(ek，dk)を出力する確率的アルゴリズムである。
（３）暗号化アルゴリズムEnc：
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek，平文mを入力として，乱数rを任意に選択し，暗号文cを出力する確率的アルゴリズムである。
（４）復号アルゴリズムDec：
セキュリティパラメータκ，共通パラメータpp，復号鍵dk，暗号文cを入力として，平文mを得るアルゴリズムである。
（５）変換鍵生成アルゴリズムReKeyGen：
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA，受託装置の暗号化鍵ekBを入力として，変換鍵rkA→Bを出力する確率的アルゴリズムである。
（６）変換アルゴリズムReEnc：
セキュリティパラメータκ，共通パラメータpp，変換鍵rkA→B，委託装置の公開鍵ekAを用いて生成された暗号文cAを入力として，受託装置の復号鍵dkBで復号可能な暗号文cBを出力する確率的アルゴリズムである。
【００１２】
この暗号方式Π=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)は，既に或る変換鍵を用いて変換された暗号文であっても，再び当該暗号文を別の変換鍵で変換できるという特徴を有している。
【００１３】
＜複数回変換可能プロキシ暗号方式の構成＞
本発明による実施形態では，再変換可能暗号方式Π=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)から，複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を構成する。
【００１４】
複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)は，下記のとおりである。
（１）SETUP:
セキュリティパラメータκを入力として，pp←Setup(κ)を求め，Hを変換回数の最大として，PP=(pp，H)を出力するアルゴリズムである。
（２）GEN:
セキュリティパラメータκとPP=(pp，H)を入力として，η=0，…，Hについて，(ek(η)，dk(η))←Gen(κ，pp)を求め，暗号化鍵EK=(ek(0)，…，ek(H))と復号鍵DK=(dk(0)，…，dk(H))を出力するアルゴリズムである。
（３）ENC:
セキュリティパラメータκ，PP=(pp，H)，EK=(ek(0)，…，ek(H))，レベルη，平文mを入力として，c←Enc(κ，pp，ek(η)，m)を求め，ct=(η，c)を暗号文として出力するアルゴリズムである。
（４）DEC:
セキュリティパラメータκ，PP=(pp，H)，DK=(dk(0)，…，dk(H))，暗号文(η，c)を入力として，m’←Dec(κ，pp，dk(η)，c)を求め，復号された平文としてm’を出力するアルゴリズムである。
（５）REKEYGEN:
セキュリティパラメータκ，PP=(pp，H)，委託装置の復号鍵DKA=(dkA(0)，…，dkA(H))，受託装置の暗号化鍵EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，rk(A,h)→(B,h+1)←ReKeyGen(κ，pp，dkA(h)，ekB(h+1))を計算し，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力するアルゴリズムである。
（６）REENC:
セキュリティパラメータκ，PP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，暗号文ct=(η，c)を入力として，c’←ReEnc(κ，pp，rk(A,η)→(B,η+1)，c)を求め，(η+1，c’)を変換済暗号文として出力するアルゴリズムである。
【００１５】
この複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)に基づくプロキシ暗号システム１は，元の暗号文を送信するユーザ装置（送信者装置）１００，復号権限を委譲するユーザ装置（delegator；委託装置）２００，復号権限を委譲されるユーザ装置（delegatee；受託装置）３００，プロキシ装置４００を含む。
【００１６】
実施例1のプロキシ暗号システム１における機能および処理手順を叙述する。
（１）SETUP:
送信者装置１００の設定部１０１は，セキュリティパラメータκを入力として，共通パラメータpp←Setup(κ)を計算する。そして，設定部１０１は，Hを変換回数の最大として，変換回数上限付き共通パラメータPP=(pp，H)を出力する。Hは，送信者装置を用いるユーザによってH≧1を満たす予め定められた整数値であるが，好ましくはH≧2を満たす整数値である。
【００１７】
（２）GEN:
委託装置２００の鍵生成部２０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，(ekA(η)，dkA(η))←Gen(κ，pp)を計算する。鍵生成部２０１は，暗号化鍵の組EKA=(ekA(0)，…，ekA(H))と復号鍵の組DKA=(dkA(0)，…，dkA(H))を出力する。
受託装置３００の鍵生成部３０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，(ekB(η)，dkB(η))←Gen(κ，pp)を計算する。鍵生成部３０１は，暗号化鍵の組EKB=(ekB(0)，…，ekB(H))と復号鍵の組DKB=(dkB(0)，…，dkB(H))を出力する。
【００１８】
（３）ENC:
送信者装置１００の暗号化部１０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の暗号化鍵の組EKA=(ekA(0)，…，ekA(H))，変換回数の指定を表すレベルη，平文mを入力として，c←Enc(κ，pp，ekA(η)，m)を計算する。暗号化部１０２は，ct=(η，c)を委託装置２００に向けた暗号文として出力する。
【００１９】
（４）REKEYGEN:
委託装置２００の変換鍵生成部２０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の復号鍵の組DKA=(dkA(0)，…，dkA(H))，受託装置３００の暗号化鍵の組EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，rk(A,h)→(B,h+1)←ReKeyGen(κ，pp，dkA(h)，ekB(h+1))を計算する。変換鍵生成部２０２は，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力する。
【００２０】
（５）REENC:
プロキシ装置４００の変換暗号文生成部４０１は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，委託装置２００に向けた暗号文ct=(η，c)を入力として，c’←ReEnc(κ，pp，rk(A,η)→(B,η+1)，c)を計算する。変換暗号文生成部４０１は，(η+1，c’)を変換済暗号文として出力する。
【００２１】
（６）DEC:
受託装置３００の復号部３０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，受託装置３００の復号鍵の組DKB=(dkB(0)，…，dkB(H))，変換済暗号文(η+1，c’)を入力として，m’←Dec(κ，pp，dkB(η+1)，c’)を計算する。復号部３０２は，平文としてm’を出力する。
【００２２】
[実施例2]
実施例1の変形例として，完全準同型公開鍵暗号に二つのアルゴリズムを加えたものを，複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を構成するための再変換可能暗号方式とする。
＜準備：完全準同型公開鍵暗号＞
ΠFHE=(Setup; Gen; Enc; Dec; Eval)を完全準同型公開鍵暗号とする。具体的には，ΠFHEは五つのアルゴリズムの組であり，各アルゴリズムは次の性質を満たす。
（１）共通パラメータ生成アルゴリズムSetup：
セキュリティパラメータκを入力として，共通パラメータppを出力する確率的アルゴリズムである。
（２）鍵生成アルゴリズムGen：
セキュリティパラメータκと共通パラメータppを入力として，暗号化鍵と復号鍵の組(ek，dk)を出力する確率的アルゴリズムである。
（３）暗号化アルゴリズムEnc：
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek，平文mを入力として，乱数rを任意に選択し，暗号文cを出力する確率的アルゴリズムである。
（４）復号アルゴリズムDec：
セキュリティパラメータκ，共通パラメータpp，復号鍵dk，暗号文cを入力として，平文mを計算するアルゴリズムである。
（５）評価アルゴリズムEval：
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek，論理回路C，暗号文の組c→=(c1，…，cn)を入力として，新しい暗号文c”を計算するアルゴリズムである。このとき，論理回路Cは，Dec(κ，pp，dk，c”)=C(Dec(κ，pp，dk，c1)，…，Dec(κ，pp，dk，cn))の関係が成立するバイナリ回路であり，新しい暗号文c”に対する復号アルゴリズムDecに相当する。
【００２３】
＜再変換可能暗号方式の構成＞
完全準同型公開鍵暗号ΠFHE=(Setup; Gen; Enc; Dec; Eval)から再変換可能暗号Π’=(Setup’; Gen’; Enc’; Dec’; ReKeyGen’; ReEnc’)を構成する。
（１）Setup’:
ΠFHEのSetupと同じアルゴリズムである。
（２）Gen’:
ΠFHEのGenと同じアルゴリズムである。
（３）Enc’:
ΠFHEのEncと同じアルゴリズムである。
（４）Dec’:
ΠFHEのDecと同じアルゴリズムである。
（５）ReKeyGen’:
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA，受託装置の暗号化鍵ekBを入力として，cA→B←Enc(κ，pp，ekB，dkA)を計算し，変換鍵rkA→B=(cA→B，ekB)を出力するアルゴリズムである。
（６）ReEnc’:
セキュリティパラメータκ，共通パラメータpp，変換鍵rkA→B，委託装置に向けた暗号文cを入力として，(cA→B，ekB)=rkA→Bとパース（parse）し（つまり，入力された変換鍵rkA→BからcA→BとekBを得る），c’←Enc(κ，pp，ekB，c)を計算し，c”←Eval(κ，pp，ekB，Dec，(cA→B，c’))を計算し，c”を出力するアルゴリズムである。
【００２４】
この再変換可能暗号Π’を実施例１の再変換可能暗号Π=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)と見立てて，実施例１と同様にして，複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を構成すればよい。
【００２５】
実施例2のプロキシ暗号システム１における機能および処理手順を叙述する。
（１）SETUP:
送信者装置１００の設定部１０１は，セキュリティパラメータκを入力として，共通パラメータpp←Setup(κ)を計算する。そして，設定部１０１は，Hを変換回数の最大として，変換回数上限付き共通パラメータPP=(pp，H)を出力する。Hは，送信者装置を用いるユーザによってH≧1を満たす予め定められた整数値であるが，好ましくはH≧2を満たす整数値である。
【００２６】
（２）GEN:
委託装置２００の鍵生成部２０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，(ekA(η)，dkA(η))←Gen(κ，pp)を計算する。鍵生成部２０１は，暗号化鍵の組EKA=(ekA(0)，…，ekA(H))と復号鍵の組DKA=(dkA(0)，…，dkA(H))を出力する。
受託装置３００の鍵生成部３０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，(ekB(η)，dkB(η))←Gen(κ，pp)を計算する。鍵生成部３０１は，暗号化鍵の組EKB=(ekB(0)，…，ekB(H))と復号鍵の組DKB=(dkB(0)，…，dkB(H))を出力する。
【００２７】
（３）ENC:
送信者装置１００の暗号化部１０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の暗号化鍵の組EKA=(ekA(0)，…，ekA(H))，変換回数の指定を表すレベルη，平文mを入力として，c←Enc(κ，pp，ekA(η)，m)を計算する。暗号化部１０２は，ct=(η，c)を委託装置２００に向けた暗号文として出力する。
【００２８】
（４）REKEYGEN:
委託装置２００の変換鍵生成部２０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の復号鍵の組DKA=(dkA(0)，…，dkA(H))，受託装置３００の暗号化鍵の組EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，c(A,h)→(B,h+1)←ReKeyGen(κ，pp，dkA(h)，ekB(h+1))=Enc(κ，pp，ekB(h+1)，dkA(h))を計算する。そして，変換鍵生成部２０２は，h=0，…，H-1についてrk(A,h)→(B,h+1)=(c(A,h)→(B,h+1)，ekB(h+1))として，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力する。
【００２９】
（５）REENC:
プロキシ装置４００の変換暗号文生成部４０１は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，委託装置２００に向けた暗号文ct=(η，c)を入力として，h=0，…，H-1について，(c(A,h)→(B,h+1)，ekB(h+1))←rk(A,h)→(B,h+1)とパース（parse）し，c’(h+1)←Enc(κ，pp，ekB(h+1)，c)を計算する。そして，変換暗号文生成部４０１は，c”←Eval(κ，pp，ekB(η+1)，Dec，(c(A,0)→(B,1)，c’(h+1))，…，(c(A,H-1)→(B,H)，c’(H)))を計算し，(η+1，c”)を変換済暗号文として出力する。
【００３０】
（６）DEC:
受託装置３００の復号部３０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，受託装置３００の復号鍵の組DKB=(dkB(0)，…，dkB(H))，変換済暗号文(η+1，c”)を入力として，m’←Dec(κ，pp，dkB(η+1)，c”)を計算する。復号部３０２は，平文としてm’を出力する。
【００３１】
[実施例3]
＜準備＞
アルゴリズムBDとアルゴリズムP2を下記の確定的アルゴリズムとする（参考文献：Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully homomorphic encryption without bootstrapping. In ITCS 2012, 2012）。2δ-1<q<2δとする。
（１）アルゴリズムBD：
x→∈Zqnを入力とする。1)k=1，…，δについて，u→k∈{0，1}nを，x→=Σk=1δ2k-1u→kを満たすように計算する。2)(u→1，…，u→δ)∈{0，1}nδを出力する。
（２）アルゴリズムP2：
s→∈Znqを入力とする場合には，[1，2，…，2δ-1]T(×)s→∈Zqnδを出力するアルゴリズムPを実行し（ただし，(×)は行列のクロネッカー積を表す），行列S=[s→1，…，s→g]を入力とする場合には，[P(s→1)，…，P(s→g)]∈Zqnδ×gなる行列を出力する。
【００３２】
これらのアルゴリズムは定義より，任意のx→∈Zqn，S∈Zqn×gについて，BD(x→)・P2(S)=x→・S∈Zqgを満たす。
【００３３】
＜再変換可能暗号の構成＞
参考文献（Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully homomorphic encryption without bootstrapping. In ITCS 2012, 2012）を参考にして，下記の再変換可能暗号Π’=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を構成する。
（１）Setup:
AをZqm×nからランダムに選び，共通パラメータpp=(1κ，n，q，m，DΧ，A)を出力する。DΧは，Zqm上の分布を表す。分布DΧは，必ずまたは圧倒的な確率でサンプルXの絶対値があるパラメータB以下（X∈[-B,B]⊆Zq）な分布である。
（２）Gen:
セキュリティパラメータκ，共通パラメータppを入力とする。SをZqn×nからランダムに選ぶ。E∈Zqm×nを分布DΧnに従ってランダムに選ぶ。B=A・S+2Eを計算する。暗号化鍵ek=Bと復号鍵dk=(S，B)を出力する。以下，簡単のためにM=[A|B]∈Zqm×2n（1≦i≦m，1≦j≦nのとき，行列Mの(i，j)成分は行列Aの(i，j)成分に一致し，1≦i≦m，n+1≦j≦2nのとき，行列Mの(i，j)成分は行列Bの(i，j-n)成分に一致する），S^=(-S|I)∈Zq2n×n（1≦i≦n，1≦j≦nのとき，行列S^の(i，j)成分は行列-Sの(i，j)成分に一致し，n+1≦i≦2n，1≦j≦nのとき，行列S^の(i，j)成分は単位行列Iの(i-n，j)成分に一致する）とおく。このときM・S^=-AS+B=2Eである。
（３）Enc:
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek=B，平文m→∈{0，1}nを入力とする。r→←{-1，+1}mをランダムに選ぶ。(u→，v→)=(r→A，r→B)を計算する。(u→，v→)を1行2n列の行列とみなす。つまり，1≦j≦nのとき，行列(u→，v→)の(1，j)成分はベクトルu→の(1，j)成分に一致し，n+1≦j≦2nのとき，行列(u→，v→)の(1，j)成分はベクトルv→の(1，j-n)成分に一致する。(u→，c→)=(u→，v→+m→)を計算する。暗号文(u→，c→)を出力する。
（４）Dec:
セキュリティパラメータκ，共通パラメータpp，復号鍵dk=(S，B)，暗号文(u→，c→)を入力とする。d→←(u→，c→)S^ mod qを計算する。m→←d→ mod 2を計算して，m→を平文として出力する。
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA=(SA，BA)，受託装置の暗号化鍵ekB=BBを入力とする。R←{-1，+1}nδ×mをランダムに選ぶ。MB=[A|BB]とする。MA→B←RMB+[O|-P2(SA)]を計算する（Oはnδ×nのゼロ行列である）。変換鍵rkA→B=(MA→B，BB)を出力する。
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，変換鍵rkA→B=(MA→B，BB)，暗号文(u→，c→)を入力とする。(u→’，c→’)←BD(u→)・MA→Bを計算する。r→~←{-1，+1}mをランダムに選ぶ。(u→~，v→~)←r→~・[A|BB]を計算する。(u→-，c→-)←(u→’+u→~，c→+c→’+v→~)を計算する。変換済暗号文として(u→-，c→-)を出力する。
【００３４】
この再変換可能暗号Π’を実施例１の再変換可能暗号Π=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)と見立てて，実施例１と同様にして，複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を構成すればよい。
【００３５】
実施例3のプロキシ暗号システム１における機能および処理手順を叙述する。
（１）SETUP:
送信者装置１００の設定部１０１は，AをZqm×nからランダムに選び，共通パラメータpp=(1κ，n，q，m，DΧ，A)と，変換回数の最大値Hとの組である変換回数上限付き共通パラメータPP=(pp，H)を出力する。Hは，送信者装置を用いるユーザによってH≧1を満たす予め定められた整数値であるが，好ましくはH≧2を満たす整数値である。
【００３６】
（２）GEN:
委託装置２００の鍵生成部２０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，S(η)をZqn×nからランダムに選び，E(η)∈Zqm×nを分布DΧnに従ってランダムに選び，B(η)=A・S(η)+2E(η)を計算して，暗号化鍵ekA(η)=B(η)と復号鍵dkA(η)=(S(η)，B(η))を求める。そして，鍵生成部２０１は，暗号化鍵の組EKA=(ekA(0)，…，ekA(H))と復号鍵の組DKA=(dkA(0)，…，dkA(H))を出力する。
受託装置３００の鍵生成部３０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，S(η)をZqn×nからランダムに選び，E(η)∈Zqm×nを分布DΧnに従ってランダムに選び，B(η)=A・S(η)+2E(η)を計算して，暗号化鍵ekB(η)=B(η)と復号鍵dkB(η)=(S(η)，B(η))を求める。そして，鍵生成部３０１は，暗号化鍵の組EKB=(ekB(0)，…，ekB(H))と復号鍵の組DKB=(dkB(0)，…，dkB(H))を出力する。
【００３７】
（３）ENC:
送信者装置１００の暗号化部１０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の暗号化鍵の組EKA=(ekA(0)，…，ekA(H))，変換回数の指定を表すレベルη，平文m→∈{0，1}nを入力として，r→←{-1，+1}mをランダムに選び，(u→，v→)=(r→A，r→B)を計算し，(u→，c→)=(u→，v→+m→)を求める。暗号化部１０２は，ct=(η，(u→，c→))を委託装置２００に向けた暗号文として出力する。
【００３８】
（４）REKEYGEN:
委託装置２００の変換鍵生成部２０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の復号鍵の組DKA=(dkA(0)，…，dkA(H))，受託装置３００の暗号化鍵の組EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，R←{-1，+1}nδ×mをランダムに選び，B(B,h)=ekB(h)，M(B,h+1)=[A|B(B,h+1)]として，M(A,h)→(B,h+1)←RM(B,h+1)+[O|-P2(S(A,h))]を計算し，rk(A,h)→(B,h+1)=(M(A,h)→(B,h+1)，B(B,h+1))を求める。変換鍵生成部２０２は，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力する。
【００３９】
（５）REENC:
プロキシ装置４００の変換暗号文生成部４０１は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，委託装置２００に向けた暗号文ct=(η，(u→，c→))を入力として，h=0，…，H-1について，(u→’，c→’)←BD(u→)・M(A,η)→(B,η+1)を計算し，r→~←{-1，+1}mをランダムに選び，(u→~，v→~)←r→~・[A|B(B,η+1)]を計算し，(u→-，c→-)←(u→’+u→~，c→+c→’+v→~)を計算する。変換暗号文生成部４０１は，変換済暗号文として(η+1，(u→-，c→-))を出力する。
【００４０】
（６）DEC:
受託装置３００の復号部３０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，受託装置３００の復号鍵の組DKB=(dkB(0)，…，dkB(H))，変換済暗号文(η+1，(u→-，c→-))を入力として，d→←(u→-，c→-)S^(η+1) mod qを計算し，m→←d→ mod 2を計算して，m→を平文として出力する。
【００４１】
[実施例4]
＜準備＞
κをセキュリティパラメータとし，k(κ)を整数関数とし，n(κ)=2k(κ)とする。f(x)=xn+1とする。q=q(κ)を素数とする。環R=Z[x]/(f(x))とし，Rq=R/qRとする。δを2δ-1<q<2δを満たす整数とする。
アルゴリズムBDとアルゴリズムP2を下記の確定的アルゴリズムとする（参考文献：Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully homomorphic encryption without bootstrapping. ITCS 2012, 2012）。
【００４２】
（１）アルゴリズムBD：
x∈Rqを入力にとる。1)k=1，…，δについて，uk∈{0，1}n⊆Rqを，x=Σk=1δ2k-1ukを満たすように計算する。2)(u1，…，uδ)∈{0，1}nδ⊆Rqδを出力する。
（２）アルゴリズムP2：
s∈Rqを入力にとり，[1，2s，…，2δ-1s]T∈Rqδを出力する。
【００４３】
これらのアルゴリズムは定義より，任意のx，s∈Rqについて，BD(x)・P2(s)=xs∈Rqを満たす。
【００４４】
＜再変換可能暗号の構成＞
参考文献（Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully homomorphic encryption without bootstrapping. In ITCS 2012, 2012）や参考文献（Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 1-23. Springer-Verlag, 2010.）を参考にして，下記の再変換可能暗号Π’=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を構成する。
（１）Setup:
a→をRqmからランダムに選び，pp=(1κ，n，q，m，DΧ，a→)を出力する。DΧは，Rq上の分布を表す。分布DΧは，必ずまたは圧倒的な確率で，サンプルとして取った多項式aaの各係数aiの絶対値があるパラメータB以下（aa=a0+…+an-1Xn-1としてai∈[-B,B]⊆Zq）な分布である。
（２）Gen:
セキュリティパラメータκ，共通パラメータppを入力とする。sをRqからランダムに選ぶ。e→←DΧmをランダムに選ぶ。b→←sa→+2e→∈Rqmを計算する。暗号化鍵ek=b→と復号鍵dk=(s，b→)を出力する。以下，簡単のためにM=[a→|b→]∈Rqm×2，s→^=(-s，1)T∈Rq2とおく。このときM・s^=-a→s+b→=2e→となる。
（３）Enc:
セキュリティパラメータκ，共通パラメータpp，暗号化鍵ek=b→，平文m∈{0，1}n⊆Rqを入力とする。r→←({-1，+1}n)mをランダムに選ぶ。(u，v)=(r→・a→，r→・b→)を計算する。(u，c)=(u，v+m)を計算して，ベクトル(u，c)を暗号文として出力する。
（４）Dec:
セキュリティパラメータκ，共通パラメータpp，復号鍵dk=(s，b→)，暗号文(u，c)を入力とする。d←(u，c)・s→^ mod qを計算する。m←d mod 2を計算する。平文mを出力する。
（５）ReKeyGen:
セキュリティパラメータκ，共通パラメータpp，委託装置の復号鍵dkA=(sA，b→A)と受託装置の暗号化鍵ekB=b→Bを入力とする。R←({-1，+1}n)δ×mをランダムに選ぶ。MB=[a→|b→B]とする。MA→B←RMB+[0→|-P2(sA)]を計算する。変換鍵rkA→B=(MA→B，b→B)を出力する。
（６）ReEnc:
セキュリティパラメータκ，共通パラメータpp，変換鍵rkA→B=(MA→B，b→B)，暗号文(u，c)を入力とする。(u’，c’)←BD(u)・MA→Bを計算する。r→~←({-1，+1}n)mをランダムに選ぶ。(u~，v~)←r→~・[a→|b→B]を計算する。(u-，c-)←(u’+u~，c+c’+v~)を計算する。変換済暗号文として(u-，c-)を出力する。
【００４５】
この再変換可能暗号Π’を実施例１の再変換可能暗号Π=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)と見立てて，実施例１と同様にして，複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を構成すればよい。
【００４６】
実施例4のプロキシ暗号システム１における機能および処理手順を叙述する。
（１）SETUP:
送信者装置１００の設定部１０１は，a→をRqmからランダムに選び，共通パラメータpp=(1κ，n，q，m，DΧ，a→)と，変換回数の最大値Hとの組である変換回数上限付き共通パラメータPP=(pp，H)を出力する。Hは，送信者装置を用いるユーザによってH≧1を満たす予め定められた整数値であるが，好ましくはH≧2を満たす整数値である。
【００４７】
（２）GEN:
委託装置２００の鍵生成部２０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，s(η)をZqからランダムに選び，e→(η)←DΧmに従ってランダムに選び，b→(η)=s(η)a→+2e→(η)∈Rqmを計算して，暗号化鍵ekA(η)=b→(η)と復号鍵dkA(η)=(s(η)，b→(η))を求める。そして，鍵生成部２０１は，暗号化鍵の組EKA=(ekA(0)，…，ekA(H))と復号鍵の組DKA=(dkA(0)，…，dkA(H))を出力する。
受託装置３００の鍵生成部３０１は，セキュリティパラメータκと変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，s(η)をZqからランダムに選び，e→(η)←DΧmに従ってランダムに選び，b→(η)=s(η)a→+2e→(η)∈Rqmを計算して，暗号化鍵ekB(η)=b→(η)と復号鍵dkB(η)=(s(η)，b→(η))を求める。そして，鍵生成部３０１は，暗号化鍵の組EKB=(ekB(0)，…，ekB(H))と復号鍵の組DKB=(dkB(0)，…，dkB(H))を出力する。
【００４８】
（３）ENC:
送信者装置１００の暗号化部１０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の暗号化鍵の組EKA=(ekA(0)，…，ekA(H))，変換回数の指定を表すレベルη，平文m→∈{0，1}n⊆Rqを入力として，r→←({-1，+1}n)mをランダムに選び，(u，v)=(r→・a→，r→・b→)を計算し，(u，c)=(u，v+m)を求める。暗号化部１０２は，レベルηとベクトル(u，c)との組ct=(η，(u，c))を委託装置２００に向けた暗号文として出力する。
【００４９】
（４）REKEYGEN:
委託装置２００の変換鍵生成部２０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の復号鍵の組DKA=(dkA(0)，…，dkA(H))，受託装置３００の暗号化鍵の組EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，R←({-1，+1}n)δ×mをランダムに選び，b→(B,h)=ekB(h)，M(B,h+1)=[a→|b→(B,h+1)]として，M(A,h)→(B,h+1)←RM(B,h+1)+[0→|-P2(s(A,h))]を計算し，rk(A,h)→(B,h+1)=(M(A,h)→(B,h+1)，b→(B,h+1))を求める。変換鍵生成部２０２は，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力する。
【００５０】
（５）REENC:
プロキシ装置４００の変換暗号文生成部４０１は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，委託装置２００に向けた暗号文ct=(η，(u，c))を入力として，h=0，…，H-1について，(u’，c’)←BD(u)・M(A,η)→(B,η+1)を計算し，r→~←({-1，+1}n)mをランダムに選び，(u~，v~)←r→~・[a→|b→(B,η+1)]を計算し，(u-，c-)←(u’+u~，c+c’+v~)を計算する。変換暗号文生成部４０１は，変換済暗号文として(η+1，(u-，c-))を出力する。
【００５１】
（６）DEC:
受託装置３００の復号部３０２は，セキュリティパラメータκ，変換回数上限付き共通パラメータPP=(pp，H)，受託装置３００の復号鍵の組DKB=(dkB(0)，…，dkB(H))，変換済暗号文(η+1，(u-，c-))を入力として，d←(u，c)・s→^ mod qを計算し，m←d mod 2を計算して，mを平文として出力する。
【００５２】
[実施例5]
＜準備＞
κをセキュリティパラメータとし，k(κ)を整数関数とし，n(κ)=2k(κ)とする。f(x)=xn+1とする。q=q(κ)を素数とする。環R=Z[x]/(f(x))とし，Rq=R/qRとする。δを2δ-1<q<2δを満たす整数とする。
アルゴリズムBDとアルゴリズムP2を下記の確定的アルゴリズムとする（参考文献：Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. Fully homomorphic encryption without bootstrapping. ITCS 2012, 2012）。
【００５３】
（１）アルゴリズムBD：
x∈Rqを入力にとる。1)k=1，…，δについて，uk∈{0，1}n⊆Rqを，x=Σk=1δ2k-1ukを満たすように計算する。2)(u1，…，uδ)∈{0，1}nδ⊆Rqδを出力する。
（２）アルゴリズムP2：
s∈Rqを入力にとり，[1，2s，…，2δ-1s]T∈Rqδを出力する。
【００５４】
これらのアルゴリズムは定義より，任意のx，s∈Rqについて，BD(x)・P2(s)=xs∈Rqを満たす。
【００５５】
＜再変換可能暗号の構成＞
参考文献（Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 505-524. Springer-Verlag, 2011.）や参考文献（Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 1-23. Springer-Verlag, 2010.）を参考にして，下記の再変換可能暗号Π’=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)を構成する。
（１）Setup:
a←Rqをランダムに選択し，共通パラメータpp=(κ，n，q，DΧ，a)を出力する。DΧは，Rq上の分布を表す。分布DΧは，必ずまたは圧倒的な確率で、サンプルとして取った多項式aaの各係数aiの絶対値があるパラメータB以下（aa=a0+…+an-1Xn-1としてai∈[-B,B]⊆Zq）な分布である。
（２）Gen:
共通パラメータppを入力とする。s，e←DΧをランダムに選択し，b←as+2eを計算し，暗号化鍵ek=b，復号鍵dk=(s，b)を出力する。
（３）Enc:
共通パラメータpp，暗号化鍵ek=b，平文m∈{0，1}n⊆Rqを入力とする。t，e’，e”←DΧをランダムに選択し，(u，c)←(at+2e’，bt+2e”+m)とする。暗号文(u，c)を出力する。
（４）Dec:
共通パラメータppと暗号文(u，c)を入力とする。d=c-us mod qを計算する。m=d mod 2を計算する。mを平文として出力する。
（５）ReKeyGen:
共通パラメータpp，受託装置の暗号化鍵ekB=bB，委託装置の復号鍵dkA=(sA，bA)を入力とする。r→，h→，h→’←DΧδをランダムに選び，f→←ar→+2h→，g→←br→+2h→’+P2(sA)とする。変換鍵rkA→B=(f→，g→，bB)を出力する。
（６）ReEnc:
共通パラメータpp，変換鍵rkA→B=(f→，g→，bB)，暗号文(u，c)を入力とする。(u’，c’)=BD(u)・[f→，g→]を計算する。t’，f’，f”←DΧをランダムに選び，(u~，v~)=(at’+2f’，bBt’+2f”)を計算する。(u-，c-)=(u’+u~，c+c’+v~)を計算する。変換済暗号文(u-，c-)を出力する。
【００５６】
この再変換可能暗号Π’を実施例１の再変換可能暗号Π=(Setup; Gen; Enc; Dec; ReKeyGen; ReEnc)と見立てて，実施例１と同様にして，複数回変換可能プロキシ暗号方式π=(SETUP; GEN; ENC; DEC; REKEYGEN; REENC)を構成すればよい。
【００５７】
実施例5のプロキシ暗号システム１における機能および処理手順を叙述する。
（１）SETUP:
送信者装置１００の設定部１０１は，a←Rqをランダムに選択し，共通パラメータpp=(κ，n，q，DΧ，a)と，変換回数の最大値Hとの組である変換回数上限付き共通パラメータPP=(pp，H)を出力する。Hは，送信者装置を用いるユーザによってH≧1を満たす予め定められた整数値であるが，好ましくはH≧2を満たす整数値である。
【００５８】
（２）GEN:
委託装置２００の鍵生成部２０１は，変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，s(η)，e(η)←DΧをランダムに選択し，b(η)←as(η)+2e(η)を計算し，暗号化鍵ekA(η)=b(η)，復号鍵dkA(η)=(s(η)，b(η))を出力する。そして，鍵生成部２０１は，暗号化鍵の組EKA=(ekA(0)，…，ekA(H))と復号鍵の組DKA=(dkA(0)，…，dkA(H))を出力する。
受託装置３００の鍵生成部３０１は，変換回数上限付き共通パラメータPP=(pp，H)を入力として，η=0，…，Hについて，s(η)，e(η)←DΧをランダムに選択し，b(η)←as(η)+2e(η)を計算し，暗号化鍵ekB(η)=b(η)，復号鍵dkB(η)=(s(η)，b(η))を出力する。そして，鍵生成部２０１は，暗号化鍵の組EKB=(ekB(0)，…，ekB(H))と復号鍵の組DKB=(dkB(0)，…，dkB(H))を出力する。
【００５９】
（３）ENC:
送信者装置１００の暗号化部１０２は，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の暗号化鍵の組EKA=(ekA(0)，…，ekA(H))，変換回数の指定を表すレベルη，平文m∈{0，1}n⊆Rqを入力として，t，e’，e”←DΧをランダムに選択し，(u，c)←(at+2e’，bt+2e”+m)を求める。暗号化部１０２は，レベルηとベクトル(u，c)との組ct=(η，(u，c))を委託装置２００に向けた暗号文として出力する。
【００６０】
（４）REKEYGEN:
委託装置２００の変換鍵生成部２０２は，変換回数上限付き共通パラメータPP=(pp，H)，委託装置２００の復号鍵の組DKA=(dkA(0)，…，dkA(H))，受託装置３００の暗号化鍵の組EKB=(ekB(0)，…，ekB(H))を入力として，h=0，…，H-1について，r→，h→，h→’←DΧδをランダムに選び，s(A,h)=sA(h)として，f→←ar→+2h→，g→←br→+2h→’+P2(s(A,h))を計算し，rk(A,h)→(B,h+1)=(f→，g→，b(B,h+1))を求める。変換鍵生成部２０２は，RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))を変換鍵として出力する。
【００６１】
（５）REENC:
プロキシ装置４００の変換暗号文生成部４０１は，変換回数上限付き共通パラメータPP=(pp，H)，変換鍵RKA→B=(rk(A,0)→(B,1)，…，rk(A,H-1)→(B,H))，委託装置２００に向けた暗号文ct=(η，(u，c))を入力として，h=0，…，H-1について，(u’，c’)=BD(u)・[f→，g→]を計算し，t’，f’，f”←DΧをランダムに選び，(u~，v~)=(at’+2f’，b(B,η+1)t’+2f”)を計算し，(u-，c-)=(u’+u~，c+c’+v~)を計算する。変換暗号文生成部４０１は，変換済暗号文として(η+1，(u-，c-))を出力する。
【００６２】
（６）DEC:
受託装置３００の復号部３０２は，変換回数上限付き共通パラメータPP=(pp，H)，受託装置３００の復号鍵の組DKB=(dkB(0)，…，dkB(H))，変換済暗号文(η+1，(u-，c-))を入力として，d=c-us mod qを計算し，m=d mod 2を計算して，mを平文として出力する。
【００６３】
＜補記＞
プロキシ暗号システムに含まれうるハードウェアエンティティ（送信者装置，委託装置，受託装置，プロキシ装置）は，キーボードなどが接続可能な入力部，液晶ディスプレイなどが接続可能な出力部，ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部，ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい。〕，メモリであるＲＡＭやＲＯＭ，ハードディスクである外部記憶装置並びにこれらの入力部，出力部，通信部，ＣＰＵ，ＲＡＭ，ＲＯＭ，外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて，ハードウェアエンティティに，ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては，汎用コンピュータなどがある。
【００６４】
ハードウェアエンティティの外部記憶装置には，上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず，例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい）。また，これらのプログラムの処理によって得られるデータなどは，ＲＡＭや外部記憶装置などに適宜に記憶される。
【００６５】
ハードウェアエンティティでは，外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて，適宜にＣＰＵで解釈実行・処理される。その結果，ＣＰＵが所定の機能（例えば，設定部，鍵生成部，暗号化部，変換鍵生成部，変換暗号文生成部，復号部など）を実現する。
【００６６】
各実施形態で説明したハードウェアエンティティの細部においては，数論における数値計算処理が必要となる場合があるが，数論における数値計算処理自体は，周知技術と同様にして達成されるので，その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては，例えばＰＡＲＩ／ＧＰ，ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては，例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成24年3月21日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては，例えばインターネット〈URL: http://page.math.tu-berlin.de/~kant/kash.html〉［平成24年3月21日検索］を参照のこと。）。
また，この点に関する文献として，参考文献Ａを挙げることができる。
（参考文献Ａ）H. Cohen，"A Course in Computational Algebraic Number Theory"，GTM 138，Springer-Verlag，1993.
【００６７】
本発明は上述の実施形態に限定されるものではなく，本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また，上記実施形態において説明した処理は，記載の順に従って時系列に実行されるのみならず，処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。上述の各実施例では，情報処理に用いられるデータ等の情報の装置間での送受信に関わる説明を省略したが，当然のこととして，或る装置Xにおける或る情報処理に用いられる情報Yは，当該装置Xが当該情報Yを保有していない場合，当該情報処理の実行前に，当該装置Xによって当該情報Yを保有する装置から取得されていることに留意されたい。なお，データ等の情報の装置間での送受信は周知技術を利用して実施される。
【００６８】
また，上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合，ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして，このプログラムをコンピュータで実行することにより，上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００６９】
この処理内容を記述したプログラムは，コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては，例えば，磁気記録装置，光ディスク，光磁気記録媒体，半導体メモリ等どのようなものでもよい。具体的には，例えば，磁気記録装置として，ハードディスク装置，フレキシブルディスク，磁気テープ等を，光ディスクとして，ＤＶＤ（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）型のサービスによって，上述の処理を実行する構成としてもよい。なお，本形態におけるプログラムには，電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７２】
また，この形態では，コンピュータ上で所定のプログラムを実行させることにより，ハードウェアエンティティを構成することとしたが，これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005713947.tif 000002
【図２】
0005713947.tif 000003