(57)【要約】【課題】格子問題ベースの公開鍵暗号方式に適用するプロキシ再暗号化方式において、変換鍵が漏洩しない安全性の高い方式を実現する。【解決手段】復号権限委譲者であるユーザｉの公開鍵(Ａi,Ｐi)と秘密鍵Ｓi、復号権限被委譲者であるユーザｊの公開鍵(Ａj，Ｐj)と秘密鍵Ｓj、Ｚqn×gからランダムに選ばれたＲ、及びＢ＝Ｒ＋Ｓi、Ｃ＝Ｓj＋Ｒの計算から得られた(Ａi,Ｐi,Ｂ)と(Ａj,Ｐj,Ｃ)からＴ＝Ｃ−Ｂを計算して、変換鍵 ((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を生成し、当該変換鍵を用い、ユーザｉの公開鍵(Ａi,Ｐi)により暗号化された暗号文Ｃi＝(ｕi,ｃi)からｃi´＝ｃi−ｕiＴを計算し、マスク暗号文Ｃj´＝(ｕj´、ｃj´)を計算し、ｕj＝ｕi＋ｕj´、ｃj＝ｃi´＋ｃj´を計算して、(ｕj,ｃj)をユーザｊ向けの暗号文Ｃjとして出力する。【選択図】図２
2012150399.tif 000002
【特許請求の範囲】
【請求項１】
実数ｘについて、一番近い整数に丸める操作を
【数９】
2012150399.tif 000011
と定義し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記するとき、自然数ｍ、ｑ、実数α∈(０,１)における分布χm,q,αが、ガウス分布Ｎ(０,α2／２π)上のサンプルｘについて、ｘ´＝ｑ・ｘ、
【数１０】
2012150399.tif 000012
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）をｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）として得られるベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmであると定義され、
セキュリティパラメータが（ｎ,ｍ,ｑ,α,ｇ）であるとき、
鍵生成アルゴリズムが、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムであり、
暗号化アルゴリズムが、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【数１１】
2012150399.tif 000013
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムであり、
復号アルゴリズムが、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【数１２】
2012150399.tif 000014
により計算して出力するアルゴリズムである、
公開鍵暗号方式に対して適用するプロキシ再暗号化システムであって、
前記鍵生成アルゴリズムに基づき生成された、復号権限委譲者であるユーザｉの公開鍵(Ａi,Ｐi)、秘密鍵Ｓiを予め保有し、ＲをＺqn×gからランダムに選び、Ｂ＝Ｒ＋Ｓiを計算して(Ａi,Ｐi,Ｂ)とＲを出力する委譲情報生成装置と、
前記鍵生成アルゴリズムに基づき生成された、復号権限被委譲者であるユーザｊの公開鍵(Ａj，Ｐj)、秘密鍵Ｓjを予め保有し、Ｒが入力され、Ｃ＝Ｓj＋Ｒを計算して(Ａj,Ｐj,Ｃ)を出力する被委譲情報生成装置と、
(Ａi,Ｐi,Ｂ)と(Ａj,Ｐj,Ｃ)とが入力され、Ｔ＝Ｃ−Ｂを計算して、ユーザのインデックスの組(ｉ,ｊ)に対応する変換鍵として((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を生成して保管する変換鍵生成装置と、
ユーザｉの公開鍵(Ａi,Ｐi)を用いて前記暗号化アルゴリズムにより暗号化された暗号文Ｃi＝(ｕi,ｃi)と、ユーザのインデックスの組(ｉ,ｊ)と、が入力され、当該インデックスの組に対応する変換鍵((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を変換鍵生成装置から入手し、ｃi´＝ｃi−ｕiＴを計算し、前記暗号化アルゴリズムに、公開鍵pk＝(Ａj,Ｐj)、ｋ＝０g、及び{０，１}mから新たにランダムに選んだｒを適用することにより、マスク暗号文Ｃj´＝(ｕj´、ｃj´)を計算し、ｕj＝ｕi＋ｕj´、ｃj＝ｃi´＋ｃj´を計算して、(ｕj,ｃj)をユーザｊ向けの暗号文Ｃjとして出力する暗号文変換装置と、
を備えるプロキシ再暗号化システム。
【請求項２】
実数ｘについて、一番近い整数に丸める操作を
【数１３】
2012150399.tif 000015
と定義し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記するとき、自然数ｍ、ｑ、実数α∈(０,１)における分布χm,q,αが、ガウス分布Ｎ(０,α2／２π)上のサンプルｘについて、ｘ´＝ｑ・ｘ、
【数１４】
2012150399.tif 000016
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）をｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）として得られるベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmであると定義され、
セキュリティパラメータが（ｎ,ｍ,ｑ,α,ｇ）であるとき、
鍵生成アルゴリズムが、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムであり、
暗号化アルゴリズムが、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【数１５】
2012150399.tif 000017
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムであり、
復号アルゴリズムが、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【数１６】
2012150399.tif 000018
により計算して出力するアルゴリズムである、
公開鍵暗号方式に対して適用する委譲情報生成装置であって、
前記鍵生成アルゴリズムに基づき生成された、復号権限委譲者であるユーザｉの公開鍵(Ａi,Ｐi)、秘密鍵Ｓiを予め保有し、ＲをＺqn×gからランダムに選び、Ｂ＝Ｒ＋Ｓiを計算して(Ａi,Ｐi,Ｂ)とＲを出力する委譲情報生成装置。
【請求項３】
実数ｘについて、一番近い整数に丸める操作を
【数１７】
2012150399.tif 000019
と定義し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記するとき、自然数ｍ、ｑ、実数α∈(０,１)における分布χm,q,αが、ガウス分布Ｎ(０,α2／２π)上のサンプルｘについて、ｘ´＝ｑ・ｘ、
【数１８】
2012150399.tif 000020
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）をｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）として得られるベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmであると定義され、
セキュリティパラメータが（ｎ,ｍ,ｑ,α,ｇ）であるとき、
鍵生成アルゴリズムが、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムであり、
暗号化アルゴリズムが、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【数１９】
2012150399.tif 000021
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムであり、
復号アルゴリズムが、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【数２０】
2012150399.tif 000022
により計算して出力するアルゴリズムである、
公開鍵暗号方式に対して適用する被委譲情報生成装置あって、
前記鍵生成アルゴリズムに基づき生成された、復号権限被委譲者であるユーザｊの公開鍵(Ａj，Ｐj)、秘密鍵Ｓjを予め保有し、Ｒが入力され、Ｃ＝Ｓj＋Ｒを計算して(Ａj,Ｐj,Ｃ)を出力する被委譲情報生成装置。
【請求項４】
実数ｘについて、一番近い整数に丸める操作を
【数２１】
2012150399.tif 000023
と定義し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記するとき、自然数ｍ、ｑ、実数α∈(０,１)における分布χm,q,αが、ガウス分布Ｎ(０,α2／２π)上のサンプルｘについて、ｘ´＝ｑ・ｘ、
【数２２】
2012150399.tif 000024
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）をｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）として得られるベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmであると定義され、
セキュリティパラメータが（ｎ,ｍ,ｑ,α,ｇ）であるとき、
鍵生成アルゴリズムが、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムであり、
暗号化アルゴリズムが、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【数２３】
2012150399.tif 000025
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムであり、
復号アルゴリズムが、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【数２４】
2012150399.tif 000026
により計算して出力するアルゴリズムである、
公開鍵暗号方式に対して適用する変換鍵生成装置であって、
前記鍵生成アルゴリズムに基づき、復号権限委譲者であるユーザｉの公開鍵(Ａi,Ｐi)と秘密鍵Ｓi、復号権限被委譲者であるユーザｊの公開鍵(Ａj，Ｐj)と秘密鍵Ｓj、Ｚqn×gからランダムに選ばれたＲ、及びＢ＝Ｒ＋Ｓi、Ｃ＝Ｓj＋Ｒの計算から得られた、(Ａi,Ｐi,Ｂ)と(Ａj,Ｐj,Ｃ)とが入力され、Ｔ＝Ｃ−Ｂを計算して、ユーザのインデックスの組(ｉ,ｊ)に対応する変換鍵として((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を生成して保管する変換鍵生成装置。
【請求項５】
実数ｘについて、一番近い整数に丸める操作を
【数２５】
2012150399.tif 000027
と定義し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記するとき、自然数ｍ、ｑ、実数α∈(０,１)における分布χm,q,αが、ガウス分布Ｎ(０,α2／２π)上のサンプルｘについて、ｘ´＝ｑ・ｘ、
【数２６】
2012150399.tif 000028
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）をｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）として得られるベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmであると定義され、
セキュリティパラメータが（ｎ,ｍ,ｑ,α,ｇ）であるとき、
鍵生成アルゴリズムが、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムであり、
暗号化アルゴリズムが、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【数２７】
2012150399.tif 000029
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムであり、
復号アルゴリズムが、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【数２８】
2012150399.tif 000030
により計算して出力するアルゴリズムである、
公開鍵暗号方式に対して適用する暗号文変換装置であって、
ユーザｉの公開鍵(Ａi,Ｐi)を用いて前記暗号化アルゴリズムにより暗号化された暗号文Ｃi＝(ｕi,ｃi)と、ユーザのインデックスの組(ｉ,ｊ)と、が入力され、当該インデックスの組に対応する変換鍵((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を変換鍵生成装置から入手し、ｃi´＝ｃi−ｕiＴを計算し、前記暗号化アルゴリズムに、公開鍵pk＝(Ａj,Ｐj)、ｋ＝０g、及び{０，１}mから新たにランダムに選んだｒを適用することにより、マスク暗号文Ｃj´＝(ｕj´、ｃj´)を計算し、ｕj＝ｕi＋ｕj´、ｃj＝ｃi´＋ｃj´を計算して、(ｕj,ｃj)をユーザｊ向けの暗号文Ｃjとして出力する暗号文変換装置。
【請求項６】
実数ｘについて、一番近い整数に丸める操作を
【数２９】
2012150399.tif 000031
と定義し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記するとき、自然数ｍ、ｑ、実数α∈(０,１)における分布χm,q,αが、ガウス分布Ｎ(０,α2／２π)上のサンプルｘについて、ｘ´＝ｑ・ｘ、
【数３０】
2012150399.tif 000032
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）をｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）として得られるベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmであると定義され、
セキュリティパラメータが（ｎ,ｍ,ｑ,α,ｇ）であるとき、
鍵生成アルゴリズムが、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムであり、
暗号化アルゴリズムが、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【数３１】
2012150399.tif 000033
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムであり、
復号アルゴリズムが、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【数３２】
2012150399.tif 000034
により計算して出力するアルゴリズムである、
公開鍵暗号方式に対して適用するプロキシ再暗号化方法であって、
前記鍵生成アルゴリズムに基づき生成された、復号権限委譲者であるユーザｉの公開鍵(Ａi,Ｐi)、秘密鍵Ｓiを予め保有し、ＲをＺqn×gからランダムに選び、Ｂ＝Ｒ＋Ｓiを計算して(Ａi,Ｐi,Ｂ)とＲを出力する委譲情報生成ステップと、
前記鍵生成アルゴリズムに基づき生成された、復号権限被委譲者であるユーザｊの公開鍵(Ａj，Ｐj)、秘密鍵Ｓjを予め保有し、Ｒが入力され、Ｃ＝Ｓj＋Ｒを計算して(Ａj,Ｐj,Ｃ)を出力する被委譲情報生成ステップと、
(Ａi,Ｐi,Ｂ)と(Ａj,Ｐj,Ｃ)とが入力され、Ｔ＝Ｃ−Ｂを計算して、ユーザのインデックスの組(ｉ,ｊ)に対応する変換鍵として((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を生成して変換鍵生成装置に保管する変換鍵生成ステップと、
ユーザｉの公開鍵(Ａi,Ｐi)を用いて前記暗号化アルゴリズムにより暗号化された暗号文Ｃi＝(ｕi,ｃi)と、ユーザのインデックスの組(ｉ,ｊ)と、が入力され、当該インデックスの組に対応する変換鍵((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を変換鍵生成装置から入手し、ｃi´＝ｃi−ｕiＴを計算し、前記暗号化アルゴリズムに、公開鍵pk＝(Ａj,Ｐj)、ｋ＝０g、及び{０，１}mから新たにランダムに選んだｒを適用することにより、マスク暗号文Ｃj´＝(ｕj´、ｃj´)を計算し、ｕj＝ｕi＋ｕj´、ｃj＝ｃi´＋ｃj´を計算して、(ｕj,ｃj)をユーザｊ向けの暗号文Ｃjとして出力する暗号文変換ステップと、
を実行するプロキシ再暗号化方法。
【請求項７】
請求項１に記載のプロキシ再暗号化システム、請求項２に記載の委譲情報生成装置、請求項３に記載の被委譲情報生成装置、請求項４に記載の変換鍵生成装置、又は請求項５に記載の暗号文変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ある公開鍵で暗号化された暗号文を、その公開鍵に対応する秘密鍵とは異なる秘密鍵を用いて復号することを可能とするプロキシ再暗号化システム、委譲情報生成装置、被委譲情報生成装置、変換鍵生成装置、暗号文変換装置、プロキシ再暗号化方法、及びそれらのプログラムに関する。
【背景技術】
【０００２】
公開鍵暗号方式では、ある公開鍵で暗号化された暗号文を復号できるのは、対応する秘密鍵を有する者に限られる。例えば、ユーザｈからユーザｉにメッセージｍを送信する場合、ユーザｈは図１に示すようにユーザｉの公開鍵pkｉを用いて暗号文Ｃｉを生成して送信し、公開鍵pkｉに対応する秘密鍵skｉを持つユーザｉのみがこの暗号文を復号できる。
【０００３】
しかし、変換鍵rkを用いることによって、その暗号文を異なる秘密鍵を用いて復号可能な暗号文に変換する方式が、プロキシ再暗号化方式である。プロキシ再暗号化方式は、復号権限を委譲するユーザ、復号権限を委譲されるユーザ、暗号文を変換するプロキシから構成される。図１の例では、復号権限を委譲するユーザｉ向けの暗号文Ｃｉを復号権限を委譲されるユーザｊ向けの暗号文Ｃｊに変換する変換鍵rkijを持つプロキシが、入力された暗号文Ｃｉを暗号文Ｃｊに変換して出力する。そのため、その暗号文Ｃｊを受け取ったユーザｊは、自己の秘密鍵skｊでメッセージｍを復号することができる。
【０００４】
プロキシ再暗号化方式は、非特許文献１で初めて提案され、それ以降、離散対数問題や楕円離散対数問題に基づいて様々なプロキシ再暗号化方式が提案されている。また、格子問題に基づく公開鍵暗号方式（例えば、非特許文献２、３）に適用可能なプロキシ再暗号化方式が非特許文献４で提案されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Matt Blaze, Gerrit Bleumer, and Martin Strauss,"Divertible Protocols and Atomic Proxy Cryptography", EUROCRYPT'98, Springer-Verlag, 1998, volume 1403 of Lecture Notes in Computer Science, p.127-144
【非特許文献２】Oded Regev,"On Lattices, Learning with Errors, Random Linear Codes, and Cryptography", Journal of the ACM, 2009, 56(6), article 34, p.1-37
【非特許文献３】Chris Peikert, Vinod Vaikuntanathan, and Brent Waters,"A Framework for Efficient and Composable Oblivious Transfer", CRYPTO 2008, Springer-Verlag, 2008, volume 5157 of Lecture Notes in Computer Science, p.554-571
【非特許文献４】Keita Xagawa, Keisuke Tanaka,"Proxy Re-Encryption based on Learning with Errors", SCIS 2010, 2010
【発明の概要】
【発明が解決しようとする課題】
【０００６】
格子問題に基づく公開鍵暗号方式に適用可能な非特許文献４のプロキシ再暗号化方式は、変換前の暗号文と変換後の暗号文を監視すると、変換鍵が漏洩するという問題がある。
【０００７】
本発明の目的は、格子問題に基づく公開鍵暗号方式において、プロキシ再暗号化処理を行う際に変換鍵が漏洩しない安全性の高いプロキシ再暗号化システム、委譲情報生成装置、被委譲情報生成装置、変換鍵生成装置、暗号文変換装置、プロキシ再暗号化方法、及びそれらのプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明のプロキシ暗号化システムは、以下のような公開鍵暗号方式に適用される。
当該公開鍵暗号方式は、実数ｘについて、一番近い整数に丸める操作を
【０００９】
【数１】
2012150399.tif 000003
【００１０】
と表記し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記するとき、自然数ｍ、ｑ、実数α∈(０,１)における分布χm,q,αが、ガウス分布Ｎ(０,α2／２π)上のサンプルｘについて、ｘ´＝ｑ・ｘ、
【００１１】
【数２】
2012150399.tif 000004
【００１２】
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）をｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）として得られるベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmであると定義され、セキュリティパラメータが（ｎ,ｍ,ｑ,α,ｇ）であるとき、鍵生成アルゴリズムが、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムであり、暗号化アルゴリズムが、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【００１３】
【数３】
2012150399.tif 000005
【００１４】
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムであり、復号アルゴリズムが、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【００１５】
【数４】
2012150399.tif 000006
【００１６】
により計算して出力するアルゴリズムである公開鍵暗号方式である。
本発明のプロキシ暗号化システムは、このような公開鍵暗号方式に対して適用するプロキシ再暗号化システムであり、委譲情報生成装置、被委譲情報生成装置、変換鍵生成装置、及び暗号文変換装置を備える。
【００１７】
委譲情報生成装置は、前記鍵生成アルゴリズムに基づき生成された、復号権限委譲者であるユーザｉの公開鍵(Ａi,Ｐi)、秘密鍵Ｓiを予め保有し、ＲをＺqn×gからランダムに選び、Ｂ＝Ｒ＋Ｓiを計算して(Ａi,Ｐi,Ｂ)とＲを出力する。
【００１８】
被委譲情報生成装置は、前記鍵生成アルゴリズムに基づき生成された、復号権限被委譲者であるユーザｊの公開鍵(Ａj，Ｐj)、秘密鍵Ｓjを予め保有し、Ｒが入力され、Ｃ＝Ｓj＋Ｒを計算して(Ａj,Ｐj,Ｃ)を出力する。
【００１９】
変換鍵生成装置は、(Ａi,Ｐi,Ｂ)と(Ａj,Ｐj,Ｃ)とが入力され、Ｔ＝Ｃ−Ｂを計算して、ユーザのインデックスの組(ｉ,ｊ)に対応する変換鍵として((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を生成して保管する。
【００２０】
暗号文変換装置は、ユーザｉの公開鍵(Ａi,Ｐi)を用いて前記暗号化アルゴリズムにより暗号化された暗号文Ｃi＝(ｕi,ｃi)と、ユーザのインデックスの組(ｉ,ｊ)と、が入力され、当該インデックスの組に対応する変換鍵((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を変換鍵生成装置から入手し、ｃi´＝ｃi−ｕiＴを計算し、前記暗号化アルゴリズムに、公開鍵pk＝(Ａj,Ｐj)、ｋ＝０g、及び{０，１}mから新たにランダムに選んだｒを適用することにより、マスク暗号文Ｃj´＝(ｕj´、ｃj´)を計算し、ｕj＝ｕi＋ｕj´、ｃj＝ｃi´＋ｃj´を計算して、(ｕj,ｃj)をユーザｊ向けの暗号文Ｃjとして出力する。
【発明の効果】
【００２１】
本発明によれば、格子問題に基づく公開鍵暗号方式において、従来技術の暗号文変換処理に加えて、マスク用暗号文の作成及びマスク処理を行うことで、変換鍵の漏洩を防ぐことができるため、変換鍵が漏洩しない安全性の高いプロキシ再暗号化システム、委譲情報生成装置、被委譲情報生成装置、変換鍵生成装置、暗号文変換装置、プロキシ再暗号化方法、及びそれらのプログラムを提供することができる。
【図面の簡単な説明】
【００２２】
【図１】プロキシ再暗号化のイメージを示す図。
【図２】プロキシ再暗号化システム１００の構成例を示す図。
【図３】プロキシ再暗号化システム１００の処理フロー例を示す図。
【図４】プロキシ再暗号化システム１００を構成する各装置のハードウェア構成例を示す図。
【発明を実施するための形態】
【００２３】
本発明のプロキシ再暗号化システム１００は、格子問題に基づく公開鍵暗号方式に暗号文変換機能を付加するものである。本発明を適用する格子問題に基づく公開鍵暗号方式は、Regev暗号（非特許文献２）の拡張である非特許文献３の方式である。そのため、本発明のプロキシ再暗号化システム１００を適用する当該公開鍵暗号方式に係る定義・アルゴリズムをまず説明する。
実数ｘについて、一番近い整数に丸める操作を
【００２４】
【数５】
2012150399.tif 000007
【００２５】
と定義し、平均０、分散σ2のガウス分布をＮ(０,σ2)と表記する。そして、自然数ｍ、ｑ、実数α∈(０,１)について、分布χm,q,αを定義する。具体的には、ガウス分布Ｎ(０,α2／２π)からサンプルｘをとって、ｘ´＝ｑ・ｘを計算し、
【００２６】
【数６】
2012150399.tif 000008
【００２７】
とし、ｘi∈Ｚq（＝{０，１，・・・，ｑ−１}）を、ｘi＝ｘ´´ mod q（ｉ＝１,・・・,ｍ）により計算して得られたベクトルvx＝(ｘ1,・・・,ｘm)∈Ｚqmとして、これを分布χm,q,αとして定義する。
【００２８】
当該公開鍵暗号方式は、このような定義の下、次の３つのアルゴリズムから構成される。なお、セキュリティパラメータは（ｎ,ｍ,ｑ,α,ｇ）であるとする。
【００２９】
鍵生成アルゴリズムは、ＡをＺqm×nからランダムに選び、ＳをＺqn×gからランダムに選び、vx1、vx2、・・・、vxgを前記分布χm,q,αに従い選んでＸ＝[vx1,vx2,・・・,vxg] ∈Ｚqm×gとして、Ｐ＝ＡＳ＋Ｘを計算し、公開鍵をpk＝(Ａ,Ｐ)とし、秘密鍵をsk＝Ｓとして出力する確率的アルゴリズムである。
【００３０】
暗号化アルゴリズムは、公開鍵pkと平文ｋ∈{０，１}gを入力にとり、ｒを{０，１}mからランダムに選び、ｕ＝ｒＡを計算し、ｖ＝ｒＰを計算し、
【００３１】
【数７】
2012150399.tif 000009
【００３２】
を計算し、ｃ＝ｖ＋ｔを計算して、暗号文としてＣ＝(ｕ,ｃ)を出力する確率的アルゴリズムである。
復号アルゴリズムは、秘密鍵skと暗号文Ｃ＝(ｕ,ｃ)を入力にとり、ｄ＝ｃ−ｕＳを計算し、平文ｋを
【００３３】
【数８】
2012150399.tif 000010
【００３４】
により計算して出力するアルゴリズムである。
本発明のプロキシ再暗号化システム１００は、以上のような定義・アルゴリズムに基づく公開鍵暗号方式に対して適用するプロキシ再暗号化システムである。図２にプロキシ再暗号化システム１００の機能構成例を、図３にその処理フロー例をそれぞれ示す。プロキシ再暗号化システム１００は、委譲情報生成装置１１０、被委譲情報生成装置１２０、変換鍵生成装置１３０、及び暗号文変換装置１４０を備える。
【００３５】
委譲情報生成装置１１０は、一般には復号権限委譲者であるユーザｉのところに設けられ、前記鍵生成アルゴリズムに基づき生成されたユーザｉの公開鍵(Ａi,Ｐi)、秘密鍵Ｓiを予め保有し、ＲをＺqn×gからランダムに選び、Ｂ＝Ｒ＋Ｓiを計算して(Ａi,Ｐi,Ｂ)とＲを出力する（Ｓ１）。
【００３６】
被委譲情報生成装置１２０は、一般には復号権限被委譲者であるユーザｊのところに設けられ、前記鍵生成アルゴリズムに基づき生成されたユーザｊの公開鍵(Ａj，Ｐj)、秘密鍵Ｓjを予め保有し、委譲情報生成装置１１０で生成されたＲが入力され、Ｃ＝Ｓj＋Ｒを計算して(Ａj,Ｐj,Ｃ)を出力する（Ｓ２）。
【００３７】
変換鍵生成装置１３０と暗号文変換装置１４０はプロキシ装置を構成し、任意の場所に設けられる。
【００３８】
変換鍵生成装置１３０は、委譲情報生成装置１１０で生成された(Ａi,Ｐi,Ｂ)と被委譲情報生成装置１３０で生成された(Ａj,Ｐj,Ｃ)とが入力され、Ｔ＝Ｃ−Ｂを計算して、ユーザのインデックスの組(ｉ,ｊ)に対応する変換鍵として((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を生成し保管する（Ｓ３）。なお、この変換鍵は、ユーザｉの公開鍵による暗号文をユーザｊの秘密鍵で復号できる暗号文に変換することができるだけでなく、その逆、すなわちユーザｊの公開鍵による暗号文をユーザｉの秘密鍵で復号できる暗号文に変換することも可能である。
【００３９】
暗号文変換装置１４０は、ユーザｉの公開鍵(Ａi,Ｐi)を用いて前記暗号化アルゴリズムにより暗号化された暗号文Ｃi＝(ｕi,ｃi)と、復号権限を委譲するユーザのインデックスｉと復号権限を委譲されるユーザのインデックスｊとの組(ｉ,ｊ)と、が入力され、まず、当該インデックスの組に対応する変換鍵((ｉ,Ａi,Ｐi),(ｊ,Ａj,Ｐj),Ｔ)を変換鍵生成装置から入手し、ｃi´＝ｃi−ｕiＴを計算する。続いて、前記暗号化アルゴリズムに、公開鍵pk＝(Ａj,Ｐj)、ｋ＝０g、及び{０，１}mから新たにランダムに選んだｒを適用することにより、マスク暗号文Ｃj´＝(ｕj´、ｃj´)を計算する。そして、ｕj＝ｕi＋ｕj´、ｃj＝ｃi´＋ｃj´を計算してマスク処理を行った上で、(ｕj,ｃj)をユーザｊ向けの暗号文Ｃjとして出力する（Ｓ４）。このように、マスク用暗号文の作成及びマスク処理を行うことで、変換鍵の漏洩を防ぐことができる。
【００４０】
以上のように、本発明のプロキシ再暗号化システム１００によれば、格子問題に基づく公開鍵暗号方式において、変換鍵が漏洩しない安全性の高いプロキシ再暗号化処理を実現することができる。
【００４１】
本発明のプロキシ再暗号化システム及びプロキシ再暗号化方法における各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本発明の訓練データ獲得装置の各機能は必要に応じ、併合・分割しても構わない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００４２】
本発明のプロキシ再暗号化システムを構成する各装置をコンピュータによって実現する場合、各装置が担う機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれて、そのプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。図４に各装置のハードウェア構成例を示す。主な機能部として記憶部１と演算処理部２が設けられる。記憶部１は、ハードディスクやメモリなどの記憶装置からなり、演算処理部２で実行するプログラム１０が記憶されるとともに、公開鍵や秘密鍵や生成した変換鍵などが記憶される。プログラム１０は、ハードウェアを、委譲情報生成装置１１０、被委譲情報生成装置１２０、変換鍵生成装置１３０、又は暗号文変換装置１４０として機能させるのに応じ、委譲情報生成機能、被委譲情報生成機能、変換鍵生成機能、又は暗号文変換機能機能の処理内容がそれぞれ記述されたものである。演算処理部２は、ＣＰＵなどのマイクロプロセッサとその周辺回路からなり、記憶部１に格納されているプログラム１０を読み出して実行し、ハードウェアとプログラムとを協働させることにより、各装置が有する機能が具体的に実現される。入出力ＩＦ部３、通信ＩＦ部４、操作入力部５及び画面表示部６は、他の装置での生成データや暗号文の入力、生成したデータや変換した暗号文の出力を始め、各種データやプログラムを入出力する機能を有する。入出力ＩＦ部３は、専用のデータ入出力回路からなり、ＣＤやＨＤＤ、ＤＶＤ、さらにはメモリカードや外部ディスクなどの記録媒体との間で、演算処理部２からの指示に応じて、各種データやプログラムの入出力を行う。通信ＩＦ部４は、専用のデータ入出力回路からなり、ＬＡＮなどの通信回線を介して接続されたサーバなどの外部装置との間で、演算処理部２からの指示に応じて、各種データやプログラムの入出力を行う。操作入力部５は、キーボードやマウスなどの操作入力装置からなり、オペレータによる操作があったときに、その操作を検出して演算処理部２へ出力する。画面表示部６は、ＬＤＣやＰＣＰなどの画面表示装置からなり、演算処理部２からの指示に応じて各種データや操作画面を表示する。
【図１】
2012150399.tif 000035
【図２】
2012150399.tif 000036
【図３】
2012150399.tif 000037
【図４】
2012150399.tif 000038