(57)【要約】  正しい計算を行う確率が低い計算装置を用いて関数ｆ（ｘ）の計算をする。Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２として、整数計算部が、互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する。第一乱数化可能標本器は、ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとする。第一べき乗計算部は、ｕ’＝ｕａを計算する。第二乱数化可能標本器は、ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとする。第二べき乗計算部は、ｖ’＝ｖｂを計算する。判定部は、ｕ’＝ｖ’であるか判定する。最終計算部は、ｕ’＝ｖ’であると判定された場合には、ｕｂ’ｖａ’を計算する。
2011086992.tif 000002
【特許請求の範囲】
【請求項１】
Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２として、
互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算部と、
ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとする第一乱数化可能標本器と、
ｕ’＝ｕａを計算する第一べき乗計算部と、
ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとする第二乱数化可能標本器と、
ｖ’＝ｖｂを計算する第二べき乗計算部と、
ｕ’＝ｖ’であるか判定する判定部と、
ｕ’＝ｖ’であると判定された場合には、ｕｂ’ｖａ’を計算する最終計算部と、
を含む代理計算システム。
【請求項２】
請求項１の代理計算システムにおいて、
Ｘ３を群Ｇに値を持つ確率変数、確率変数Ｘ３の実現値をｘ３として、ｆ（ｘ）ｘ３を計算可能であり、ａ＝１あれば上記第二乱数化可能標本器に代わりその計算結果を上記ｖとし、ｂ＝１であれば上記第一乱数化可能標本器に代わりその計算結果を上記ｕとする標本器を更に含む、
代理計算システム。
【請求項３】
請求項１の代理計算システムにおいて、
上記ｆを準同型写像、群Ｈの生成元をμｈ、群Ｈの位数をＫＨ、ν＝ｆ（μｈ）として、
上記第一乱数化可能標本器は、０以上ＫＨ未満の整数の乱数ｒ１を生成する第一乱数生成部と、第一入力情報μｈｒ１ｘｂを計算する第一入力情報計算部と、上記第一入力情報μｈｒ１ｘｂを用いてｆ（μｈｒ１ｘｂ）を計算可能でありその計算結果を第一出力情報ｚ１とする第一出力情報計算部と、ｚ１ν−ｒ１を計算してその計算結果を上記ｕとする第一計算部とを含み、
上記第二乱数化可能標本器は、０以上ＫＨ未満の整数の乱数ｒ２を生成する第二乱数生成部と、第二入力情報μｈｒ２ｘａを計算する第二入力情報計算部と、上記第二入力情報μｈｒ２ｘａを用いてｆ（μｈｒ２ｘａ）を計算可能でありその計算結果を第二出力情報ｚ２とする第二出力情報計算部と、ｚ２ν−ｒ２を計算してその計算結果を上記ｖとする第二計算部とを含む、
代理計算システム。
【請求項４】
請求項３の代理計算システムにおいて、
０以上ＫＨ未満の整数の乱数ｒ３を生成する第三乱数生成部と、第三入力情報ｘｒ３を計算する第三入力情報計算部と、上記第三入力情報ｘｒ３を用いてｆ（ｘｒ３）を計算可能でありその計算結果を第三出力情報ｚ３とする第三出力情報計算部と、ｚ３１／ｒ３を計算してａ＝１あれば上記第二乱数化可能標本器に代わりその計算結果を上記ｖとしｂ＝１であれば上記第一乱数化可能標本器に代わりその計算結果を上記ｕとする第三計算部とを含む標本器を更に含む、
代理計算システム。
【請求項５】
請求項１の代理計算システムにおいて、
群Ｈ＝Ｇ×Ｇ、上記ｆを準同型写像、群Ｇの生成元をμｇ、群Ｇの位数をＫＧ、ｘ＝（ｃ１，ｃ２），（Ｖ，Ｗ）を群Ｈの元、ｆ（Ｖ，Ｗ）＝Ｙとして、
上記第一乱数化可能標本器は、０以上ＫＧ未満の整数の乱数ｒ４を生成する第四乱数生成部と、０以上ＫＧ未満の整数の乱数ｒ５を生成する第五乱数生成部と、第四入力情報ｃ１ｂＶｒ４μｇｒ５を計算する第四入力情報計算部と、第五入力情報ｃ２ｂＷｒ４を計算する第五入力情報計算部と、上記第四入力情報ｃ１ｂＶｒ４μｇｒ５及び上記第五入力情報ｃ２ｂＷｒ４を用いてｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）を計算可能でありその計算結果を第四出力情報ｚ４とする第四出力情報計算部と、ｚ４Ｙ−ｒ４μｇ−ｒ５を計算してその計算結果を上記ｕとする第四計算部とを含み、
上記第二乱数化可能標本器は、０以上ＫＧ未満の整数の乱数ｒ６を生成する第六乱数生成部と、０以上ＫＧ未満の整数の乱数ｒ７を生成する第七乱数生成部と、第六入力情報ｃ１ａＶｒ６μｇｒ７を計算する第六入力情報計算部と、第七入力情報ｃ２ａＷｒ６を計算する第七入力情報計算部と、上記第六入力情報ｃ１ａＶｒ６μｇｒ７及び上記第七入力情報ｃ２ａＷｒ６を用いてｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）を計算可能でありその計算結果を第五出力情報ｚ５とする第五出力情報計算部と、ｚ５Ｙ−ｒ６μｇ−ｒ７を計算してその計算結果を上記ｖとする第五計算部とを含む、
代理計算システム。
【請求項６】
Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２として、
整数計算部が、互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算ステップと、
第一乱数化可能標本器が、ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとする第一乱数化可能標本抽出ステップと、
第一べき乗計算部が、ｕ’＝ｕａを計算する第一べき乗計算ステップと、
第二乱数化可能標本器が、ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとする第二乱数化可能標本抽出ステップと、
第二べき乗計算部が、ｖ’＝ｖｂを計算する第二べき乗計算ステップと、
判定部が、ｕ’＝ｖ’であるか判定する判定ステップと、
最終計算部が、ｕ’＝ｖ’であると判定された場合には、ｕｂ’ｖａ’を計算する最終計算ステップと、
を含む代理計算方法。
【請求項７】
Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２として、
互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算部と、
ｆ（ｘ）ｂｘ１を計算可能な第一乱数化可能標本器による計算結果ｕを用いてｕ’＝ｕａを計算する第一べき乗計算部と、
ｆ（ｘ）ａｘ２を計算可能な第二乱数化可能標本器による計算結果ｖを用いてｖ’＝ｖｂを計算する第二べき乗計算部と、
ｕ’＝ｖ’であるか判定する判定部と、
ｕ’＝ｖ’であると判定された場合には、ｕｂ’ｖａ’を計算する最終計算部と、
を含む依頼装置。
【請求項８】
依頼装置が計算装置に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算する代理計算システムにおいて、
Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、ＫＧを群Ｇの位数とし、ＫＨを群Ｈの位数とし、μｇを群Ｇの生成元とし、μｈを群Ｈの生成元とし、ν＝θ（μｇ，μｇ）とし、ｋを自然数のセキュリティパラメータとし、Ｋ＝２ｋとして、
上記依頼装置は、
０以上ＫＧ未満の整数の乱数ｒ１を生成する第一乱数生成部と、
０以上ＫＨ未満の整数の乱数ｒ２を生成する第二乱数生成部と、
第一入力情報ｇ１＝μｇｒ１ｇを計算する第一入力情報計算部と、
第二入力情報ｈ１＝μｈｒ２を計算する第二入力情報計算部と、
上記計算装置から受信したｚ１∈Ｆを用いて、ｚ１ν−ｒ１ｒ２を計算する第一リスト情報計算部と、
上記乱数ｒ２と上記計算されたｚ１ν−ｒ１ｒ２とから構成される情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）が記憶される第一リスト記憶部と、
０以上Ｋ未満の整数の一様乱数であるｄ１を生成する第三乱数生成部と、
０以上ＫＧ未満の整数の一様乱数であるｒ４を生成する第四乱数生成部と、
０以上ＫＨ未満の整数の一様乱数であるｒ５を生成する第五乱数生成部と、
第三入力情報ｇ２＝μｇｒ４ｇｄ１を計算する第三入力情報計算部と、
第四入力情報ｈ２＝μｈｒ５を計算する第四入力情報計算部と、
上記計算装置から受信したｚ２∈Ｆを用いて、ｚ２ν−ｒ４ｒ５を計算する第二リスト情報計算部と、
上記ｄ１と上記ｒ５と上記計算されたｚ２ν−ｒ４ｒ５とから構成される情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）が記憶される第二リスト記憶部と、
上記第一リスト記憶部から読み込んだ情報の組の第一成分をｓ１とし、第二成分をｗ１とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をｔ２とし、第二成分をｓ２とし、第三成分をｗ２として、これらの情報の組が（ｗ１）＾（ｔ２ｓ２ｓ１−１）＝ｗ２の関係を満たすかを判定し、その関係を満たす場合には、ｓ１をσに代入し、ｗ１をν’に代入する第一判定部と、
０以上ＫＧ未満の整数の一様乱数であるｒ６を生成する第六乱数生成部と、
０以上ＫＨ未満の整数の一様乱数であるｒ７を生成する第七乱数生成部と、
第五入力情報ｇ３＝ｇｒ６を計算する第五入力情報計算部と、
第六入力情報ｈ３＝μｈｒ７σｈを計算する第六入力情報計算部と、
上記計算装置から受信したｚ３∈Ｆを用いて、ｚ３ν’−ｒ６ｒ７を計算する第三リスト情報計算部と、
上記ｒ６と上記計算されたｚ３ν’−ｒ６ｒ７とから構成される情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）が記憶される第三リスト記憶部と、
０以上Ｋ未満の整数の一様乱数であるｄ２を生成する第八乱数生成部と、
０以上ＫＧ未満の整数の一様乱数であるｒ９を生成する第九乱数生成部と、
０以上ＫＨ未満の整数の一様乱数であるｒ１０を生成する第十乱数生成部と、
第七入力情報ｇ４＝μｇｒ９を計算する第七入力情報計算部と、
第八入力情報ｈ４＝μｈｒ１０σｈｄ２を計算する第八入力情報計算部と、
上記計算装置から受信したｚ４∈Ｆを用いて、ｚ４ν’−ｒ９ｒ１０を計算する第四リスト情報計算部と、
上記ｄ２と上記ｒ９と上記計算されたｚ４ν’−ｒ９ｒ１０とから構成される情報の組（ｄ２，ｒ９，ｚ４ν’−ｒ９ｒ１０）が記憶される第四リスト記憶部と、
上記第三リスト記憶部から読み込んだ情報の組の第一成分をｓ３とし、第二成分をｗ３とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をｔ４とし、第二成分をｓ４とし、第三成分をｗ４として、これらの情報の組が（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ３）＾（ｓ３−１）を出力する第二判定部と、
を含み、
上記計算装置は、
上記依頼装置から受信したｇ１及びｈ１を用いてθ（ｇ１，ｈ１）を計算可能であり、その計算結果を上記ｚ１として出力する第一出力情報計算部と、
上記依頼装置から受信したｇ２及びｈ２を用いてθ（ｇ２，ｈ２）を計算可能であり、その計算結果を上記ｚ２として出力する第二出力情報計算部と、
上記依頼装置から受信したｇ３及びｈ３を用いてθ（ｇ３，ｈ３）を計算可能であり、その計算結果を上記ｚ３として出力する第三出力情報計算部と、
上記依頼装置から受信したｇ４及びｈ４を用いてθ（ｇ４，ｈ４）を計算可能であり、その計算結果を上記ｚ４として出力する第四出力情報計算部と、
を含む、
代理計算システム。
【請求項９】
請求項８の代理計算システムにおいて、
上記第一入力情報計算部は、第一入力情報ｇ１＝ｇｒ１を計算し、
上記第一リスト情報計算部は、上記ｒ１及び上記ｒ２を用いてｒ１ｒ２を計算し、
上記第一リスト記憶部には、上記計算されたｒ１ｒ２と上記計算装置から受信したｚ１∈Ｆとから構成される情報の組（ｒ１ｒ２，ｚ１）が記憶される、
ことを特徴とする代理計算システム。
【請求項１０】
請求項８又は９に記載の代理計算システムにおいて、
上記第六入力情報計算部は、第六入力情報ｈ３＝ｈｒ７を計算し、
上記第三リスト情報計算部は、上記ｒ６及び上記ｒ７を用いてｒ６ｒ７を計算し、
上記第三リスト記憶部には、上記計算されたｒ６ｒ７と上記計算装置から受信したｚ３∈Ｆとから構成される情報の組（ｒ６ｒ７，ｚ３）が記憶される、
ことを特徴とする代理計算システム。
【請求項１１】
請求項８から１０の何れかに記載の代理計算システムにおいて、
上記第一判定部は、上記の関係を満たす場合には、ｔ１ｓ２をσに代入し、ｗ２をν’に代入し、
上記第十乱数生成部は、上記ｒ９を用いて−ｒ９−１を計算してｒ１０とする、
ことを特徴とする代理計算システム。
【請求項１２】
請求項１１に記載の代理計算システムにおいて、
上記第七乱数生成部は、上記ｒ６を用いて−ｒ６−１を計算してｒ７とし、
上記第三リスト記憶部には、１と上記計算されたｚ３ν’−ｒ６ｒ７とから構成される情報の組（１，ｚ３ν’−ｒ６ｒ７）が記憶される、
ことを特徴とする代理計算システム。
【請求項１３】
請求項８から１２の何れかに記載の代理計算システムにおいて、
上記第四乱数生成部は、上記ｒ５を用いて−ｒ５−１を計算してｒ４とする、
ことを特徴とする代理計算システム。
【請求項１４】
請求項８から１３の何れかに記載の代理計算システムにおいて、
上記ｄ１を用いてｇｄ１を計算する事前計算部を更に含み、
上記第三入力情報計算部は、上記事前計算されたｇｄ１を用いて、上記ｇ２の計算を行う、  ことを特徴とする代理計算システム。
【請求項１５】
請求項８から１４の何れかに記載の代理計算システムにおいて、
上記ｄ２を用いてｈｄ２を計算する事前計算部を更に含み、
上記第八入力情報計算部は、上記事前計算されたｈｄ２を用いて、上記ｈ４の計算を行う、
ことを特徴とする代理計算システム。
【請求項１６】
依頼装置が計算装置に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算する代理計算方法において、
Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、ＫＧを群Ｇの位数とし、ＫＨを群Ｈの位数とし、μｇを群Ｇの生成元とし、μｈを群Ｈの生成元とし、ν＝θ（μｇ，μｇ）とし、ｋを整数のセキュリティパラメータとし、Ｋ＝２ｋとして、
上記依頼装置の第一乱数生成部が、０以上ＫＧ未満の整数の乱数ｒ１を生成する第一乱数生成ステップと、
上記依頼装置の第二乱数生成部が、０以上ＫＨ未満の整数の乱数ｒ２を生成する第二乱数生成ステップと、
上記依頼装置の第一入力情報計算部が、第一入力情報ｇ１＝μｇｒ１ｇを計算する第一入力情報計算ステップと、
上記依頼装置の第二入力情報計算部が、第二入力情報ｈ１＝μｈｒ２を計算する第二入力情報計算ステップと、
上記計算装置の第一出力情報計算部が、上記依頼装置から受信したｇ１及びｈ１を用いてθ（ｇ１，ｈ１）を計算可能であり、その計算結果を上記ｚ１として出力する第一出力情報計算ステップと、
上記依頼装置の第一リスト情報計算部が、上記計算装置から受信したｚ１∈Ｆを用いて、ｚ１ν−ｒ１ｒ２を計算する第一リスト情報計算ステップと、
上記依頼装置の第一リスト記憶部に、上記乱数ｒ２と上記計算されたｚ１ν−ｒ１ｒ２とから構成される情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）が記憶されるステップと、
上記依頼装置の第三乱数生成部が、０以上Ｋ未満の整数の一様乱数であるｄ１を生成する第三乱数生成ステップと、
上記依頼装置の第四乱数生成部が、０以上ＫＧ未満の整数の一様乱数であるｒ４を生成する第四乱数生成ステップと、
上記依頼装置の第五乱数生成部が、０以上ＫＨ未満の整数の一様乱数であるｒ５を生成する第五乱数生成ステップと、
上記依頼装置の第三入力情報計算部が、第三入力情報ｇ２＝μｇｒ４ｇｄ１を計算する第三入力情報計算ステップと、
上記依頼装置の第四入力情報計算部が、第四入力情報ｈ２＝μｈｒ５を計算する第四入力情報計算ステップと、
上記計算装置の第二出力情報計算部が、上記依頼装置から受信したｇ２及びｈ２を用いてθ（ｇ２，ｈ２）を計算可能であり、その計算結果を上記ｚ２として出力する第二出力情報計算ステップと、
上記依頼装置の第二リスト情報計算部が、上記計算装置から受信したｚ２∈Ｆを用いて、ｚ２ν−ｒ４ｒ５を計算する第二リスト情報計算ステップと、
上記依頼装置の第二リスト記憶部に、上記ｄ１と上記ｒ５と上記計算されたｚ２ν−ｒ４ｒ５とから構成される情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）が記憶されるステップと、
上記依頼装置の第一判定部が、上記第一リスト記憶部から読み込んだ情報の組の第一成分をｓ１とし、第二成分をｗ１とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をｔ２とし、第二成分をｓ２とし、第三成分をｗ２として、これらの情報の組が（ｗ１）＾（ｔ２ｓ２ｓ１−１）＝ｗ２の関係を満たすかを判定し、その関係を満たす場合には、ｓ１をσに代入し、ｗ１をν’に代入する第一判定ステップと、
上記依頼装置の第六乱数生成部が、０以上ＫＧ未満の整数の一様乱数であるｒ６を生成する第六乱数生成ステップと、
上記依頼装置の第七乱数生成部が、０以上ＫＨ未満の整数の一様乱数であるｒ７を生成する第七乱数生成ステップと、
上記依頼装置の第五入力情報計算部が、第五入力情報ｇ３＝ｇｒ６を計算する第五入力情報計算ステップと、
上記依頼装置の第六入力情報計算部が、第六入力情報ｈ３＝μｈｒ７σｈを計算する第六入力情報計算ステップと、
上記計算装置の第三出力情報計算部が、上記依頼装置から受信したｇ３及びｈ３を用いてθ（ｇ３，ｈ３）を計算可能であり、その計算結果を上記ｚ３として出力する第三出力情報計算ステップと、
上記依頼装置の第三リスト情報計算部が、上記計算装置から受信したｚ３∈Ｆを用いて、ｚ３ν’−ｒ６ｒ７を計算する第三リスト情報計算ステップと、
上記依頼装置の第三リスト記憶部に、上記ｒ６と上記計算されたｚ３ν’−ｒ６ｒ７とから構成される情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）が記憶されるステップと、
上記依頼装置の第八乱数生成部が、０以上Ｋ未満の整数の一様乱数であるｄ２を生成する第八乱数生成ステップと、
上記依頼装置の第九乱数生成部が、０以上ＫＧ未満の整数の一様乱数であるｒ９を生成する第九乱数生成ステップと、
上記依頼装置の第十乱数生成部が、０以上ＫＨ未満の整数の一様乱数であるｒ１０を生成する第十乱数生成ステップと、
上記依頼装置の第七入力情報計算部が、第七入力情報ｇ４＝μｇｒ９を計算する第七入力情報計算ステップと、
上記依頼装置の第八入力情報計算部が、第八入力情報ｈ４＝μｈｒ１０σｈｄ２を計算する第八入力情報計算ステップと、
上記計算装置の第四出力情報計算部が、上記依頼装置から受信したｇ４及びｈ４を用いてθ（ｇ４，ｈ４）を計算可能であり、その計算結果を上記ｚ４として出力する第四出力情報計算ステップと、
上記依頼装置の第四リスト情報計算部が、上記計算装置から受信したｚ４∈Ｆを用いて、ｚ４ν’−ｒ９ｒ１０を計算する第四リスト情報計算ステップと、
上記依頼装置の第四リスト記憶部に、上記ｄ２と上記ｒ９と上記計算されたｚ４ν’−ｒ９ｒ１０とから構成される情報の組（ｄ２，ｒ９，ｚ４ν’−ｒ９ｒ１０）が記憶されるステップと、
上記依頼装置の第二判定部が、上記第三リスト記憶部から読み込んだ情報の組の第一成分をｓ３とし、第二成分をｗ３とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をｔ４とし、第二成分をｓ４とし、第三成分をｗ４として、これらの情報の組が（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ３）＾（ｓ３−１）を出力する第二判定ステップと、
を含む代理計算方法。
【請求項１７】
依頼装置が計算装置に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算する代理計算システムの依頼装置において、
Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、ＫＧを群Ｇの位数とし、ＫＨを群Ｈの位数とし、μｇを群Ｇの生成元とし、μｈを群Ｈの生成元とし、ν＝θ（μｇ，μｇ）とし、ｋを自然数のセキュリティパラメータとし、Ｋ＝２ｋとして、
０以上ＫＧ未満の整数の乱数ｒ１を生成する第一乱数生成部と、
０以上ＫＨ未満の整数の乱数ｒ２を生成する第二乱数生成部と、
第一入力情報ｇ１＝μｇｒ１ｇを計算する第一入力情報計算部と、
第二入力情報ｈ１＝μｈｒ２を計算する第二入力情報計算部と、
上記計算装置から受信したｚ１∈Ｆを用いて、ｚ１ν−ｒ１ｒ２を計算する第一リスト情報計算部と、
上記乱数ｒ２と上記計算されたｚ１ν−ｒ１ｒ２とから構成される情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）が記憶される第一リスト記憶部と、
０以上Ｋ未満の整数の一様乱数であるｄ１を生成する第三乱数生成部と、
０以上ＫＧ未満の整数の一様乱数であるｒ４を生成する第四乱数生成部と、
０以上ＫＨ未満の整数の一様乱数であるｒ５を生成する第五乱数生成部と、
第三入力情報ｇ２＝μｇｒ４ｇｄ１を計算する第三入力情報計算部と、
第四入力情報ｈ２＝μｈｒ５を計算する第四入力情報計算部と、
上記計算装置から受信したｚ２∈Ｆを用いて、ｚ２ν−ｒ４ｒ５を計算する第二リスト情報計算部と、
上記ｄ１と上記ｒ５と上記計算されたｚ２ν−ｒ４ｒ５とから構成される情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）が記憶される第二リスト記憶部と、
上記第一リスト記憶部から読み込んだ情報の組の第一成分をｓ１とし、第二成分をｗ１とし、上記第二リスト記憶部から読み込んだ情報の組の第一成分をｔ２とし、第二成分をｓ２とし、第三成分をｗ２として、これらの情報の組が（ｗ１）＾（ｔ２ｓ２ｓ１−１）＝ｗ２の関係を満たすかを判定し、その関係を満たす場合には、ｓ１をσに代入し、ｗ１をν’に代入する第一判定部と、
０以上ＫＧ未満の整数の一様乱数であるｒ６を生成する第六乱数生成部と、
０以上ＫＨ未満の整数の一様乱数であるｒ７を生成する第七乱数生成部と、
第五入力情報ｇ３＝ｇｒ６を計算する第五入力情報計算部と、
第六入力情報ｈ３＝μｈｒ７σｈを計算する第六入力情報計算部と、
上記計算装置から受信したｚ３∈Ｆを用いて、ｚ３ν’−ｒ６ｒ７を計算する第三リスト情報計算部と、
上記ｒ６と上記計算されたｚ３ν’−ｒ６ｒ７とから構成される情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）が記憶される第三リスト記憶部と、
０以上Ｋ未満の整数の一様乱数であるｄ２を生成する第八乱数生成部と、
０以上ＫＧ未満の整数の一様乱数であるｒ９を生成する第九乱数生成部と、
０以上ＫＨ未満の整数の一様乱数であるｒ１０を生成する第十乱数生成部と、
第七入力情報ｇ４＝μｇｒ９を計算する第七入力情報計算部と、
第八入力情報ｈ４＝μｈｒ１０σｈｄ２を計算する第八入力情報計算部と、
上記計算装置から受信したｚ４∈Ｆを用いて、ｚ４ν’−ｒ９ｒ１０を計算する第四リスト情報計算部と、
上記ｄ２と上記ｒ９と上記計算されたｚ４ν’−ｒ９ｒ１０とから構成される情報の組（ｄ２，ｒ９，ｚ４ν’−ｒ９ｒ１０）が記憶される第四リスト記憶部と、
上記第三リスト記憶部から読み込んだ情報の組の第一成分をｓ３とし、第二成分をｗ３とし、上記第四リスト記憶部から読み込んだ情報の組の第一成分をｔ４とし、第二成分をｓ４とし、第三成分をｗ４として、これらの情報の組が（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ３）＾（ｓ３−１）を出力する第二判定部と、
を含む依頼装置。
【請求項１８】
請求項７又は請求項１７の依頼装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１９】
請求項１８の依頼装置プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータによる計算技術に関する。特に、他の計算機に行わせた計算結果を用いて計算を行う技術に関する。
【背景技術】
【０００２】
正しい計算をするとは限らない計算装置に依頼した計算の結果を用いて依頼装置が関数ｆの計算を行う技術が、非特許文献１に記載されている。非特許文献１に記載された自己訂正器は、計算装置に計算を複数回依頼しその計算結果の多数決を採ることで関数ｆの計算を行う（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】M. Blum, M. Luby, and R. Rubinfeld, “Self-Testing/Correcting with Applications to Numerical Problems”， STOC 1990, pp. 73-83.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１の自己訂正器が正常に動作するためには、計算装置は一定以上の確率で正しい計算をする必要があり、正しい計算を行う確率が低い計算装置を用いて関数ｆの計算をする技術は知られていないという課題がある。
【課題を解決するための手段】
【０００５】
この発明の第一の態様である代理計算システムは、Ｇ，Ｈを巡回群、ｆを群Ｈの元ｘを群Ｇへ写す関数、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２として、互いに素である２つの自然数ａ，ｂを用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する整数計算部と、ｆ（ｘ）ｂｘ１を計算可能であり、その計算結果をｕとする第一乱数化可能標本器と、ｕ’＝ｕａを計算する第一べき乗計算部と、ｆ（ｘ）ａｘ２を計算可能であり、その計算結果をｖとする第二乱数化可能標本器と、ｖ’＝ｖｂを計算する第二べき乗計算部と、ｕ’＝ｖ’であるか判定する判定部と、ｕ’＝ｖ’であると判定された場合には、ｕｂ’ｖａ’を計算する最終計算部とを含む。【０００６】
この発明の第二の態様である代理計算システムは、Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双同型準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、ＫＧを群Ｇの位数とし、ＫＨを群Ｈの位数とし、μｇを群Ｇの生成元とし、μｈを群Ｈの生成元とし、ν＝θ（μｇ，μｇ）とし、ｋを自然数のセキュリティパラメータとし、Ｋ＝２ｋとして、依頼装置は、０以上ＫＧ未満の整数の乱数ｒ１を生成する第一乱数生成部と、０以上ＫＨ未満の整数の乱数ｒ２を生成する第二乱数生成部と、第一入力情報ｇ１＝μｇｒ１ｇを計算する第一入力情報計算部と、第二入力情報ｈ１＝μｈｒ２を計算する第二入力情報計算部と、計算装置から受信したｚ１∈Ｆを用いて、ｚ１ν−ｒ１ｒ２を計算する第一リスト情報計算部と、乱数ｒ２と計算されたｚ１ν−ｒ１ｒ２とから構成される情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）が記憶される第一リスト記憶部と、０以上Ｋ未満の整数の一様乱数であるｄ１を生成する第三乱数生成部と、０以上ＫＧ未満の整数の一様乱数であるｒ４を生成する第四乱数生成部と、０以上ＫＨ未満の整数の一様乱数であるｒ５を生成する第五乱数生成部と、第三入力情報ｇ２＝μｇｒ４ｇｄ１を計算する第三入力情報計算部と、第四入力情報ｈ２＝μｈｒ５を計算する第四入力情報計算部と、計算装置から受信したｚ２∈Ｆを用いて、ｚ２ν−ｒ４ｒ５を計算する第二リスト情報計算部と、ｄ１とｒ５と計算されたｚ２ν−ｒ４ｒ５とから構成される情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）が記憶される第二リスト記憶部と、第一リスト記憶部から読み込んだ情報の組の第一成分をｓ１とし、第二成分をｗ１とし、第二リスト記憶部から読み込んだ情報の組の第一成分をｔ２とし、第二成分をｓ２とし、第三成分をｗ２として、これらの情報の組が（ｗ１）＾（ｔ２ｓ２ｓ１−１）＝ｗ２の関係を満たすかを判定し、その関係を満たす場合には、ｓ１をσに代入し、ｗ１をν’に代入する第一判定部と、０以上ＫＧ未満の整数の一様乱数であるｒ６を生成する第六乱数生成部と、０以上ＫＨ未満の整数の一様乱数であるｒ７を生成する第七乱数生成部と、第五入力情報ｇ３＝ｇｒ６を計算する第五入力情報計算部と、第六入力情報ｈ３＝μｈｒ７σｈを計算する第六入力情報計算部と、計算装置から受信したｚ３∈Ｆを用いて、ｚ３ν’−ｒ６ｒ７を計算する第三リスト情報計算部と、ｒ６と計算されたｚ３ν’−ｒ６ｒ７とから構成される情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）が記憶される第三リスト記憶部と、０以上Ｋ未満の整数の一様乱数であるｄ２を生成する第八乱数生成部と、０以上ＫＧ未満の整数の一様乱数であるｒ９を生成する第九乱数生成部と、０以上ＫＨ未満の整数の一様乱数であるｒ１０を生成する第十乱数生成部と、第七入力情報ｇ４＝μｇｒ９を計算する第七入力情報計算部と、第八入力情報ｈ４＝μｈｒ１０σｈｄ２を計算する第八入力情報計算部と、計算装置から受信したｚ４∈Ｆを用いて、ｚ４ν’−ｒ９ｒ１０を計算する第四リスト情報計算部と、ｄ２とｒ９と計算されたｚ４ν’−ｒ９ｒ１０とから構成される情報の組（ｄ２，ｒ９，ｚ４ν’−ｒ９ｒ１０）が記憶される第四リスト記憶部と、第三リスト記憶部から読み込んだ情報の組の第一成分をｓ３とし、第二成分をｗ３とし���第四リスト記憶部から読み込んだ情報の組の第一成分をｔ４とし、第二成分をｓ４とし、第三成分をｗ４として、これらの情報の組が（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４の関係を満たすかを判定し、その関係を満たす場合には、（ｗ３）＾（ｓ３−１）を出力する第二判定部と、を含む。計算装置は、依頼装置から受信したｇ１及びｈ１を用いてθ（ｇ１，ｈ１）を計算可能であり、その計算結果をｚ１として出力する第一出力情報計算部と、依頼装置から受信したｇ２及びｈ２を用いてθ（ｇ２，ｈ２）を計算可能であり、その計算結果をｚ２として出力する第二出力情報計算部と、依頼装置から受信したｇ３及びｈ３を用いてθ（ｇ３，ｈ３）を計算可能であり、その計算結果をｚ３として出力する第三出力情報計算部と、依頼装置から受信したｇ４及びｈ４を用いてθ（ｇ４，ｈ４）を計算可能であり、その計算結果をｚ４として出力する第四出力情報計算部とを含む。
【発明の効果】
【０００７】
正しい計算を行う確率が低い計算装置を用いて関数ｆの計算をすることができる。
【図面の簡単な説明】
【０００８】
【図１】第一実施形態から第三実施形態の代理計算システムの例の機能ブロック図。
【図２】第一実施形態から第三実施形態の依頼装置及び計算装置の例の機能ブロック図。
【図３】第一実施形態から第三実施形態の標本器の例の機能ブロック図。
【図４】第一実施形態から第三実施形態の第一乱数化可能標本器及び第二乱数化可能標本器の例の機能ブロック図。
【図５】第一実施形態から第三実施形態の第一乱数化可能標本器及び第二乱数化可能標本器の他の例の機能ブロック図。
【図６】第一実施形態から第三実施形態の代理計算方法の例の流れ図。
【図７】ステップＳ３の例を示す流れ図。
【図８】ステップＳ６の例を示す流れ図。
【図９】ステップＳ３の他の例を示す流れ図。
【図１０】ステップＳ６の他の例を示す流れ図。
【図１１】第四実施形態から第十実施形態の代理計算システムの例の機能ブロック図。
【図１２】第四実施形態から第十実施形態の依頼装置の例の機能ブロック図。
【図１３】第四実施形態から第十実施形態の依頼装置の例の機能ブロック図。
【図１４】第四実施形態から第十実施形態の計算装置の例の機能ブロック図。
【図１５】第四実施形態から第十実施形態の代理計算方法の例の流れ図。
【図１６】第四実施形態から第十実施形態の代理計算方法の例の流れ図。
【図１７】代理計算システムの変形例の機能ブロック図。
【発明を実施するための形態】
【０００９】
以下、この発明による代理計算システム、代理計算方法の実施形態を詳細に説明する。
第一実施形態から第二実施形態は、依頼装置１が計算装置２に依頼した計算の結果を用いてｆ（ｘ）を計算するものである。
【００１０】
［第一実施形態］
第一実施形態の代理計算システムは、図１に例示するように依頼装置１及び計算装置２を含み、依頼装置１が計算装置２に依頼した計算の結果を用いてｆ（ｘ）を計算する。
【００１１】
依頼装置１は、図２に示すように、自然数記憶部１１、整数計算部１２、第一べき乗計算部１３、第一リスト記憶部１４、判定部１５、第二べき乗計算部１６、第二リスト記憶部１７、制御部１８及び最終計算部１９を例えば含む。計算装置２は、第一乱数化可能標本器２１及び第二乱数化可能標本器２２を例えば含む。第一実施形態においては、第一乱数化可能標本器２１及び第二乱数化可能標本器２２が計算装置２に対応する。
【００１２】
Ｇ，Ｈを巡回群、関数ｆ：Ｈ→Ｇを群Ｈの元ｘを群Ｇへ写す関数、群Ｇ，Ｈの生成元をそれぞれμｇ，μｈ、Ｘ１，Ｘ２を群Ｇに値を持つ確率変数、確率変数Ｘ１の実現値をｘ１、確率変数Ｘ２の実現値をｘ２とする。
【００１３】
自然数記憶部１１には、互いに素である２つの自然数ａ，ｂの組（ａ，ｂ）が複数記憶されているものとする。Ｉを群Ｇの位数未満の２つの自然数の組で互いに素なものの集合とすると、自然数記憶部１１にはＩの部分集合Ｓに対応する自然数ａ，ｂの組（ａ，ｂ）が記憶されていると考えることができる。
【００１４】
整数計算部１２は、自然数記憶部１１に記憶された複数の自然数の組（ａ，ｂ）から、１つの自然数の組（ａ，ｂ）をランダムに読み込み、その読み込んだ自然数の組（ａ，ｂ）を用いて、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’を計算する（ステップＳ１）。自然数ａ，ｂは互いに素であるため、ａ’ａ＋ｂ’ｂ＝１の関係を満たす整数ａ’，ｂ’は必ず存在する。自然数の組（ａ，ｂ）についての情報は、第一べき乗計算部１３、第二べき乗計算部１６、第一乱数化可能標本器２１及び第二乱数化可能標本器２２に送られる。自然数の組（ａ’，ｂ’）についての情報は、最終計算部１９に送られる。
【００１５】
制御部１８は、ｔ＝１とする（ステップＳ２）。
第一乱数化可能標本器２１は、ｆ（ｘ）ｂｘ１を計算可能であり、ｘ及びｂを用いて計算を行い、その計算結果をｕとする（ステップＳ３）。計算結果ｕは、第一べき乗計算部１３に送られる。
【００１６】
この出願において、計算可能とは、無視することができない確率以上の確率で計算することができることを意味する。無視することができない確率とは、セキュリティパラメータｋについての広義単調関数である多項式を多項式Ｆ（ｋ）として、１／Ｆ（ｋ）以上の確率である。
【００１７】
ここで、ｆ（ｘ）ｂｘ１を計算するとは、ｆ（ｘ）ｂｘ１と定義される式の値を計算することである。式ｆ（ｘ）ｂｘ１の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。
【００１８】
第一べき乗計算部１３は、ｕ’＝ｕａを計算する（ステップＳ４）。計算結果ｕとその計算結果に基づいて計算されたｕ’との組（ｕ，ｕ’）は、第一リスト記憶部１４に記憶される。
【００１９】
判定部１５は、第一リスト記憶部１４に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１７に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ５）。もし、第二リスト記憶部１７に組（ｖ，ｖ’）が記憶されていない場合には、このステップＳ５の処理を行わずに、次のステップＳ６の処理を行う。ｕ’＝ｖ’となるものがあった場合には、ステップ１２に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ６に進む。
【００２０】
第二乱数化可能標本器２２は、ｆ（ｘ）ａｘ２を計算可能であり、ｘ及びａを用いて計算を行い、その計算結果をｖとする（ステップＳ６）。計算結果ｖは、第二べき乗計算部１６に送られる。
【００２１】
第二べき乗計算部１６は、ｖ’＝ｖｂを計算する（ステップＳ７）。計算結果ｖとその計算結果に基づいて計算されたｖ’との組（ｖ，ｖ’）は、第二リスト記憶部１７に記憶される。
【００２２】
判定部１５は、第一リスト記憶部１４に記憶された組（ｕ，ｕ’）及び第二リスト記憶部１７に記憶された組（ｖ，ｖ’）の中で、ｕ’＝ｖ’となるものがあるか判定する（ステップＳ８）。ｕ’＝ｖ’となるものがあった場合には、ステップ１２に進む。ｕ’＝ｖ’となるものがなかった場合には、ステップＳ９に進む。
【００２３】
制御部１８は、ｔ＝Ｔであるか判定する（ステップＳ９）。Ｔは予め定められた自然数である。ｔ＝Ｔであれば、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して（ステップＳ１１）、処理を終える。ｔ＝Ｔでない場合には、制御部１８は、ｔを１だけインクリメント、すなわちｔ＝ｔ＋１として（ステップＳ１０）、ステップＳ３に戻る。
【００２４】
計算をすることができなかった旨の情報（この例では記号「⊥」）は、計算装置２が正しく計算を行う信頼性がＴで定められる基準を下回るということを意味する。言い換えれば、Ｔ回の繰り返しで正しい演算を行うことができなかったということを意味する。
【００２５】
最終計算部１９は、ｕ’＝ｖ’であると判定された場合には、そのｕ’及びｖ’に対応するｕ及びｖを用いてｕｂ’ｖａ’を計算して、出力する（ステップＳ１２）。計算されたｕｂ’ｖａ’＝ｆ（ｘ）となる。ｕｂ’ｖａ’＝ｆ（ｘ）となる理由については、後述する。
【００２６】
≪ｕｂ’ｖａ’＝ｆ（ｘ）となる理由について≫
Ｘを群Ｇに値を持つ確率変数とする。ｗ∈Ｇについて、ある計算装置で要求を受けるたびに確率変数Ｒに従って標本ｘ’を抽出しｗｘ’を返信するものを、ｗについて誤差Ｘを持つ標本器（ｓａｍｐｌｅｒ）と呼ぶ。
【００２７】
ｗ∈Ｇについて、ある計算装置で自然数ａの入力を受けるたびに確率変数Ｘに従って標本ｘ’を抽出しｗａｘ’を返信するものを、ｗについて誤差Ｘを持つ乱数化可能標本器（ｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒ）と呼ぶ。乱数化可能標本器はａ＝１として用いられれば標本器として機能する。
【００２８】
上記実施形態の代理計算システムは、ｘを入力としてｆ（ｘ）を出力する代理計算システムを構成するに当たり、ｆ（ｘ）について誤差Ｘ１を持つ第一乱数化可能標本器２１、ｆ（ｘ）について誤差Ｘ２を持つ第二乱数化可能標本器２２を用いている。
【００２９】
ｕ’＝ｖ’が成立するのは、すなわちｕａ＝ｖｂが成立するのは、第一乱数化可能標本器２１がｕ＝ｆ（ｘ）ｂｘ１を正しく計算しており、第二乱数化可能標本器２２がｖ＝ｆ（ｘ）ａｘ２を正しく計算しており、さらにｘ１及びｘ２が群Ｇの単位元ｅｇである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。
【００３０】
第一乱数化可能標本器２１がｕ＝ｆ（ｘ）ｂｘ１を正しく計算しており、第二乱数化可能標本器２２がｖ＝ｆ（ｘ）ａｘ２を正しく計算しており、ｘ１及びｘ２が群Ｇの単位元ｅｇであるとき、ｕｂ’ｖａ’＝（ｆ（ｘ）ｂｘ１）ｂ’（ｆ（ｘ）ａｘ２）ａ’＝（ｆ（ｘ）ｂｅｇ）ｂ’（ｆ（ｘ）ａｅｇ）ａ’＝ｆ（ｘ）ｂｂ’ｅｇｂ’ｆ（ｘ）ａａ’ｅｇａ’＝ｆ（ｘ）（ｂｂ’＋ａａ’）＝ｆ（ｘ）となる。
【００３１】
（ｑ１，ｑ２）∈Ｉについて、ｉ＝１，２の各々について関数πｉをπｉ（ｑ１，ｑ２）＝ｑｉで定義する。また、Ｌ＝ｍｉｎ（♯π１（Ｓ），♯π２（Ｓ））とする。♯・は、集合・の位数である。群Ｇが巡回群や位数の計算が困難な群であるときには、上記代理計算システムが「⊥」以外を出力するときの出力がｆ（ｘ）ではない確率は、無視できる程度の誤差の範囲で高々Ｔ２Ｌ／♯Ｓ程度と期待することができる。もしＬ／♯Ｓが無視できる量でＴが多項式オーダー程度の量であれば、上記代理計算システムは圧倒的な確率でｆ（ｘ）を出力する。
Ｌ／♯Ｓが無視できる量になるようなＳの例には、例えばＳ＝｛（１，ｄ）｜ｄ∈［２，｜Ｇ｜−１］｝がある。
【００３２】
なお、図２に破線で示すように、計算装置２に標本器２３を設けてもよい。標本器２３は、Ｘ３を群Ｇに値を持つ確率変数、確率変数Ｘ３の実現値をｘ３として、ｆ（ｘ）ｘ３を計算可能であり、ａ＝１あれば第二乱数化可能標本器２２に代わりその計算結果を上記ｖとし、ｂ＝１であれば第一乱数化可能標本器２１に代わりその計算結果を上記ｕとする。
【００３３】
一般に乱数化可能標本器よりも標本器の計算量は小さい。ａ＝１，ｂ＝１のときに第一乱数化可能標本器２１、第二乱数化可能標本器２２に代わり、標本器２３が計算を行うことで、計算装置２の計算量を小さくすることができる。
【００３４】
［第二実施形態］
第二実施形態の代理計算システムは、第一乱数化可能標本器２１及び第二乱数化可能標本器２２の一例、言い換えればステップＳ３及びステップＳ６の一例を具体化したものである。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【００３５】
第二実施形態の第一乱数化可能標本器２１は、図３に示すように、第一乱数生成部１１０、第一入力情報計算部１１１、第一出力情報計算部２４及び第一計算部１１２を例えば含む。また、第二実施形態の第二乱数化可能標本器２２は、図３に示すように、第二乱数生成部１１３、第二入力情報計算部１１４、第二出力情報計算部２５及び第二計算部１１５を例えば含む。
【００３６】
第二実施形態においては、第一乱数生成部１１０、第一入力情報計算部１１１、第一計算部１１２、第二乱数生成部１１３、第二入力情報計算部１１４及び第二計算部１１５は、依頼装置１に含まれる。また、第一出力情報計算部２４及び第二出力情報計算部２５は、計算装置２に含まれる。第二実施形態においては、第一出力情報計算部２４及び第二出力情報計算部２５が計算装置２に対応する。
【００３７】
第二実施形態の関数ｆは準同型写像であるとする。また、群Ｈの生成元をμｈ、群Ｈの位数をＫＨ、ν＝ｆ（μｈ）とする。
【００３８】
ステップＳ３は、図７に例示するステップＳ３１からステップＳ３４で構成される。
【００３９】
第一乱数生成部１１０は、０以上ＫＨ未満の整数の一様乱数ｒ１を生成する（ステップＳ３１）。生成された乱数ｒ１は、第一入力情報計算部１１１に送られる。
第一入力情報計算部１１１は、第一入力情報μｈｒ１ｘｂを計算する（ステップＳ３２）。計算された第一入力情報μｈｒ１ｘｂは、第一出力情報計算部２４に送られる。
第一出力情報計算部２４は、第一入力情報μｈｒ１ｘｂを用いて計算を行い、その計算結果を第一出力情報ｚ１とする（ステップＳ３３）。計算された第一出力情報ｚ１は、第一計算部１１２に送られる。
第一出力情報計算部２４は、ｆ（μｈｒ１ｘｂ）を計算可能である。第一出力情報計算部２４による計算の結果がｆ（μｈｒ１ｘｂ）であることもあれば、ｆ（μｈｒ１ｘｂ）でないこともある。
【００４０】
ここで、μｈの右肩のｒ１は、ｒ１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。
第一計算部１１２は、ｚ１ν−ｒ１を計算してその計算結果をｕとする（ステップＳ３４）。計算結果ｕは、第一べき乗計算部１３に送られる。ここで、ｕ＝ｚ１ν−ｒ１＝ｆ（ｘ）ｂｘ１となる。すなわち、ｚ１ν−ｒ１は、ｆ（ｘ）について誤差Ｘ１を持つ乱数化可能標本器となる。その理由については後述する。
【００４１】
ステップＳ６は、図８に例示するステップＳ６１からステップＳ６４で構成される。
【００４２】
第二乱数生成部１１３は、０以上ＫＨ未満の整数の一様乱数ｒ２を生成する（ステップＳ６１）。生成された乱数ｒ２は、第二入力情報計算部１１４に送られる。
第二入力情報計算部１１４は、第二入力情報μｈｒ２ｘａを計算する（ステップＳ６２）。計算された第二入力情報μｈｒ２ｘａは、第二出力情報計算部２５に送られる。
第二出力情報計算部２５は、第二入力情報μｈｒ２ｘａを用いて計算を行い、その計算結果を第二出力情報ｚ２とする（ステップＳ６３）。計算された第二出力情報ｚ２は、第二計算部１１５に送られる。
【００４３】
第二出力情報計算部２５は、ｆ（μｈｒ２ｘａ）を計算可能である。第二出力情報計算部２５による計算の結果がｆ（μｈｒ２ｘａ）であることもあれば、ｆ（μｈｒ２ｘａ）でないこともある。
第二計算部１１５は、ｚ２ν−ｒ２を計算してその計算結果をｖとする（ステップＳ６４）。計算結果ｖは、第二べき乗計算部１６に送られる。ここで、ｖ＝ｚ２ν−ｒ２＝ｆ（ｘ）ａｘ２となる。すなわち、ｚ２ν−ｒ２は、ｆ（ｘ）について誤差Ｘ２を持つ乱数化可能標本器となる。その理由については後述する。
【００４４】
第二実施形態においても、ａ＝１，ｂ＝１のときは、第一乱数化可能標本器２１又は第二乱数化可能標本器２２に代わり、標本器２３がｕ又はｖの値を計算することにより、計算量を削減してもよい。
【００４５】
第二実施形態の標本器２３は、図４に示すように、第三乱数生成部１１６、第三入力情報計算部１１７、第三出力情報計算部２６、第三計算部１１８を例えば含む。第三乱数生成部１１６、第三入力情報計算部１１７及び第三計算部１１８は依頼装置１に含まれる。第三出力情報計算部２６は計算装置２に含まれる。
【００４６】
ａ＝１，ｂ＝１であれば、第一乱数化可能標本器２１、第二乱数化可能標本器２２に代わり標本器２３の各部は以下の処理を行う。
第三乱数生成部１１６は、０以上ＫＨ未満の整数の乱数ｒ３を生成する。生成された乱数ｒ３は第三入力情報計算部１１７に送られる。
第三入力情報計算部１１７は、第三入力情報ｘｒ３を計算する。計算された第三入力情報ｘｒ３は、第三出力情報計算部２６に送られる。
【００４７】
第三出力情報計算部２６は、第三入力情報ｘｒ３を用いて計算を行い、その計算結果を第三出力情報ｚ３とする。計算された第三出力情報ｚ３は、第三計算部１１８に送られる。
第三出力情報計算部２６は、ｆ（ｘｒ３）を計算可能である。第三出力情報計算部２６による計算の結果がｆ（ｘｒ３）であることもあれば、ｆ（ｘｒ３）でないこともある。
【００４８】
第三計算部１１８は、ｚ３１／ｒ３を計算してその計算結果を、ａ＝１であればｖとし、ｂ＝１であればｕとする。計算結果ｖは第二べき乗計算部１６に送られる。計算結果ｕは第一べき乗計算部１３に送られる。ここで、ｕ＝ｖ＝ｚ３１／ｒ３＝ｆ（ｘ）ｘ３となる。すなわち、ｚ３１／ｒ３は、ｆ（ｘ）について誤差Ｘ３を持つ標本器となる。ｚ３１／ｒ３は、ｆ（ｘ）について誤差Ｘ３を持つ標本器となる。その理由については後述する。
【００４９】
ｚ３１／ｒ３の計算、すなわちｚ３のべき乗根の計算が困難な場合には、次のようにしてｕ及び／又はｖを計算してもよい。第三計算部１１８は、乱数ｒ３とその乱数ｒ３に基づいて計算されたｚ３の組を順次（α１，β１），（α２，β２），…，（αｍ，βｍ），…として図示していない記憶部に記憶する。ｍは自然数である。第三計算部１１８は、α１，α２，…，αｍの最小公倍数が１になれば、γ１，γ２，…，γｍを整数としてγ１α１＋γ２α２＋…＋γｍαｍ＝１となるγ１，γ２，…，γｍを計算して、そのγ，γ２，…，γｍを用いてΠｉ＝１ｍβｉγｉ＝β１γ１β２γ２…βｍγｍを計算して、その計算結果をｕ及び／又はｖとしてもよい。
【００５０】
このように、乱数ｒ１，ｒ２，ｒ３を用いてｘを撹乱した情報を計算装置２に送ることにより、関数ｆの値の計算の対象となるｘ∈Ｈを依頼装置１と計算装置２との間の通信を傍受する第三者、及び、計算装置２に対して秘匿化することができる。
【００５１】
≪ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となる理由について≫
ｃを自然数、Ｒ及びＲ’を乱数として、計算装置２がμｈＲｘｃを用いて行う計算の計算結果をＢ（μｈＲｘｃ）（すなわち、計算装置２が依頼装置１に返す計算結果をｚとすると、ｚ＝Ｂ（μｈＲｘｃ）である。）とし、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１と定義する。
【００５２】
このとき、ｚν−Ｒ＝Ｂ（μｈＲｘｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈＲｘｃ）ｆ（μｈ）−Ｒ＝Ｘｆ（μｈ）Ｒｆ（ｘ）ｃｆ（μｈ）−Ｒ＝ｆ（ｘ）ｃＸとなる。すなわち、ｚν−Ｒは、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器となる。
【００５３】
上記式展開において、Ｘ＝Ｂ（μｈＲ’）ｆ（μｈＲ’）−１＝Ｂ（μｈＲｘｃ）ｆ（μｈＲｘｃ）−１であり、Ｂ（μｈＲｘｃ）＝Ｘｆ（μｈＲｘｃ）であるという性質を用いている。この性質は、関数ｆが準同型写像であり、Ｒ及びＲ’が乱数であることに基づく。
【００５４】
したがって、ａ，ｂが自然数、ｒ１，ｒ２が乱数であることを考慮すると、同様に、ｚ１ν−ｒ１，ｚ２ν−ｒ２がｆ（ｘ）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となるのである。
【００５５】
≪ｚ３１／ｒ３がｆ（ｘ）について誤差Ｘ３を持つ標本器となる理由について≫
Ｒ及びＲ’を乱数として、計算装置２がｘＲを用いて行う計算の計算結果をＢ（ｘＲ）（すなわち、計算装置２が依頼装置１に返す計算結果をｚとすると、ｚ＝Ｂ（ｘＲ）である。）とし、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（ｘＲ）１／Ｒｆ（ｘ）−１と定義する。
このとき、ｚ１／Ｒ＝Ｂ（ｘＲ）１／Ｒ＝Ｘｆ（ｘ）＝ｆ（ｘ）Ｘとなる。すなわち、ｚ１／Ｒは、ｆ（ｘ）について誤差Ｘを持つ標本器となる。
【００５６】
上記式展開において、Ｘ＝Ｂ（ｘＲ）１／Ｒｆ（ｘＲ）−１であり、Ｂ（ｘＲ）１／Ｒ＝Ｘｆ（ｘＲ）であるという性質を用いている。この性質は、Ｒ及びＲ’が乱数であることに基づく。
したがって、ｒ３が乱数であることを考慮すると、ｚ１／Ｒがｆ（ｘ）について誤差Ｘ３を持つ乱数化可能標本器となるのである。
【００５７】
［第三実施形態］
第三実施形態の代理計算システムは、第一乱数化可能標本器２１及び第二乱数化可能標本器２２の他の例、言い換えればステップＳ３及びステップＳ６の他の例を具体化したものである。具体的には、Ｈ＝Ｇ×Ｇで、関数ｆがＥｌＧａｍａｌ暗号の復号関数、すなわち秘密鍵ｓ及び暗号文（ｃ１，ｃ２）に対してｆ（ｃ１，ｃ２）＝ｃ１ｃ２−ｓである場合の第一乱数化可能標本器２１及び第二乱数化可能標本器２２の例を具体化したものである。以下、第一実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【００５８】
第三実施形態の第一乱数化可能標本器２１は、図５に示すように、第四乱数生成部１１９、第五乱数生成部１２０、第四入力情報計算部１２１、第五入力情報計算部１２２、第四出力情報計算部２７及び第四計算部１２３を例えば含む。第二乱数化可能標本器２２は、図５に示すように、第六乱数生成部１２４、第七乱数生成部１２５、第六入力情報計算部１２６、第七入力情報計算部１２７、第五出力情報計算部２８及び第五計算部１２８を例えば含む。
【００５９】
第四乱数生成部１１９、第五乱数生成部１２０、第四入力情報計算部１２１、第五入力情報計算部１２２、第四計算部１２３、第六乱数生成部１２４、第七乱数生成部１２５、第六入力情報計算部１２６、第七入力情報計算部１２７、第五出力情報計算部２８及び第五計算部１２８は、依頼装置１に含まれる。第四出力情報計算部２７及び第五出力情報計算部２８は計算装置２に含まれる。第三実施形態では、第四出力情報計算部２７及び第五出力情報計算部２８が計算装置２に対応する。
【００６０】
第三実施形態では、ｘ＝（ｃ１，ｃ２）であり、ｆ（ｃ１，ｃ２）は直積群Ｇ×ＧからＧへの準同型写像であり、群Ｇの生成元をμｇとし、群Ｇの位数をＫＧとし、同じ秘密鍵ｓに対する暗号文（Ｖ，Ｗ）∈Ｈとその暗号文を復号した復号文ｆ（Ｖ，Ｗ）＝Ｙ∈Ｇとを依頼装置１と計算装置２は事前に知っているとする。
【００６１】
第三実施形態のステップＳ３は、図９に例示するステップＳ３１’からステップＳ３６’で構成される。
【００６２】
第四乱数生成部１１９は、０以上ＫＧ未満の整数の一様乱数ｒ４を生成する（ステップＳ３１’）。生成された乱数ｒ４は、第四入力情報計算部１２１、第五入力情報計算部１２２及び第四計算部１２３に送られる。
第五乱数生成部１２０は、０以上ＫＧ未満の整数の一様乱数ｒ５を生成する（ステップＳ３２’）。生成された乱数ｒ５は、第四入力情報計算部１２１及び第四計算部１２３に送られる。
【００６３】
第四入力情報計算部１２１は、第四入力情報ｃ１ｂＶｒ４μｇｒ５を計算する（ステップＳ３３’）。計算された第四入力情報ｃ１ｂＶｒ４μｇｒ５は、第四出力情報計算部２７に送られる。
第五入力情報計算部１２２は、第五入力情報ｃ２ｂＷｒ４を計算する（ステップＳ３４’）。計算された第五入力情報ｃ２ｂＷｒ４は、第四出力情報計算部２７に送られる。
【００６４】
第四出力情報計算部２７は、第四入力情報ｃ１ｂＶｒ４μｇｒ５及び第五入力情報ｃ２ｂＷｒ４を用いて計算を行い、その計算結果を第四出力情報ｚ４とする（ステップＳ３５’）。
第四出力情報計算部２７は、ｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）を計算可能である。第四出力情報計算部２７による計算の結果がｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）であることもあれば、ｆ（ｃ１ｂＶｒ４μｇｒ５，ｃ２ｂＷｒ４）でないこともある。
【００６５】
第四計算部１２３は、ｚ４Ｙ−ｒ４μｇ−ｒ５を計算してその計算結果をｕとする（ステップＳ３６’）。計算結果ｕは、第一べき乗計算部１３に送られる。ここで、ｕ＝ｚ４Ｙ−ｒ４μｇ−ｒ５＝ｆ（ｃ１，ｃ２）ｂｘ１となる。すなわち、ｚ４Ｙ−ｒ４μｇ−ｒ５は、ｆ（ｃ１，ｃ２）について誤差Ｘ１を持つ乱数化可能標本器となる。その理由については後述する。
【００６６】
第三実施形態のステップＳ６は、図１０に例示するステップＳ６１’からステップＳ６６’で構成される。
【００６７】
第六乱数生成部１２４は、０以上ＫＧ未満の整数の一様乱数ｒ６を生成する（ステップＳ６１’）。生成された乱数ｒ６は、第六入力情報計算部１２６、第七入力情報計算部１２７及び第五計算部１２８に送られる。
第七乱数生成部１２５は、０以上ＫＧ未満の整数の一様乱数ｒ７を生成する（ステップＳ６２’）。生成された乱数ｒ７は、第六入力情報計算部１２６及び第五計算部１２８に送られる。
【００６８】
第六入力情報計算部１２６は、第六入力情報ｃ１ａＶｒ６μｇｒ７を計算する（ステップＳ６３’）。計算された第六入力情報ｃ１ａＶｒ６μｇｒ７は、第五出力情報計算部２８に送られる。
第七入力情報計算部１２７は、第七入力情報ｃ２ａＷｒ６を計算する（ステップＳ６４’）。計算された第七入力情報ｃ２ａＷｒ６は、第五出力情報計算部２８に送られる。
【００６９】
第五出力情報計算部２８は、上記第六入力情報ｃ１ａＶｒ６μｇｒ７及び上記第七入力情報ｃ２ａＷｒ６を用いて計算を行い、その計算結果を第五出力情報ｚ５とする（ステップＳ６５’）。計算された第五出力情報ｚ５は、第五計算部１２８に送られる。
第五出力情報計算部２８は、ｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）を計算可能である。第五出力情報計算部２８による計算の結果がｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）であることもあれば、ｆ（ｃ１ａＶｒ６μｇｒ７，ｃ２ａＷｒ６）でないこともある。
【００７０】
第五計算部１２８は、ｚ５Ｙ−ｒ６μｇ−ｒ７を計算してその計算結果をｖとする（ステップＳ６６’）。計算結果ｖは、第二べき乗計算部１６に送られる。ここで、ｖ＝ｚ５Ｙ−ｒ６μｇ−ｒ７＝ｆ（ｃ１，ｃ２）ａｘ２となる。すなわち、ｚ５Ｙ−ｒ６μｇ−ｒ７は、ｆ（ｃ１，ｃ２）について誤差Ｘ２を持つ乱数化可能標本器となる。その理由については後述する。
【００７１】
≪ｚ４Ｙ−ｒ４μｇ−ｒ５，ｚ５Ｙ−ｒ６μｇ−ｒ７がｆ（ｃ１，ｃ２）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となる理由について≫
ｃを自然数、Ｒ１、Ｒ２、Ｒ１’及びＲ２’を乱数として、計算装置２がｃ１ｃＶＲ１μｇＲ２及びｃ２ｃＷＲ１を用いて行う計算の計算結果をＢ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）（すなわち、計算装置２が依頼装置１に返す計算結果をｚとすると、ｚ＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）である。）とし、群Ｇに値を持つ確率変数ＸをＸ＝Ｂ（ＶＲ１’μｇＲ２’，ＷＲ１’）ｆ（ＶＲ１’μｇＲ２’，ＷＲ１’）−１と定義する。
【００７２】
このとき、ｚＹ−Ｒ１μｇ−Ｒ２＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１，ｃ２）ｃｆ（Ｖ，Ｗ）Ｒ１ｆ（μｇ，ｅｇ）Ｒ２Ｙ−Ｒ１μｇ−Ｒ２＝Ｘｆ（ｃ１，ｃ２）ｃＹＲ１μｇＲ２Ｙ−Ｒ１μｇ−Ｒ２＝ｆ（ｃ１，ｃ２）ｃＸとなる。すなわち、ｚＹ−Ｒ１μｇ−Ｒ２は、ｆ（ｘ）について誤差Ｘを持つ乱数化可能標本器となる。なお、ｅｇは、群Ｇの単位元である。
【００７３】
上記式展開において、Ｘ＝Ｂ（ＶＲ１’μｇＲ２’，ＷＲ１’）ｆ（ＶＲ１’μｇＲ２’，ＷＲ１’）−１＝Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）ｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）であり、Ｂ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）＝Ｘｆ（ｃ１ｃＶＲ１μｇＲ２，ｃ２ｃＷＲ１）であるという性質を用いている。この性質は、Ｒ１、Ｒ２、Ｒ１’及びＲ２’が乱数であることに基づく。
【００７４】
したがって、ａ，ｂが自然数、ｒ４，ｒ５，ｒ６及びｒ７が乱数であることを考慮すると、同様に、ｚ４Ｙ−ｒ４μｇ−ｒ５，ｚ５Ｙ−ｒ６μｇ−ｒ７がｆ（ｃ１，ｃ２）についてそれぞれ誤差Ｘ１，Ｘ２を持つ乱数化可能標本器となるのである。
【００７５】
［第一実施形態から第三実施形態の変形例等］
確率変数Ｘ１、Ｘ２及びＸ３は、同じでも異なっていてもよい。
第一乱数生成部１１０、第二乱数生成部１１３、第三乱数生成部１１６、第四乱数生成部１１９、第五乱数生成部１２０、第六乱数生成部１２４及び第七乱数生成部１２５のそれぞれは、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部１１０、第二乱数生成部１１３、第三乱数生成部１１６、第四乱数生成部１１９、第五乱数生成部１２０、第六乱数生成部１２４及び第七乱数生成部１２５のそれぞれは、一様乱数ではない乱数を生成してもよい。
【００７６】
上記の例では、第一乱数化可能標本器２１、第二乱数化可能標本器２２を一回づつ呼び出しているが、依頼装置１と計算装置２との間の通信回数を減らすために、同一のａ，ｂに対して第一乱数化可能標本器２１、第二乱数化可能標本器２２を複数回呼び出して、依頼装置１が一回の通信で複数のｕ，ｖを取得できるようにしてもよい。
【００７７】
第一乱数化可能標本器２１、第二乱数化可能標本器２２及び標本器２３の各部は、依頼装置１に配置してもよいし、計算装置２に配置してもよい。すなわち、第一実施形態のように各部のすべてを計算装置２に配置してもよいし、例えば第二実施形態及び第三実施形態のように依頼装置１及び計算装置２に分けて配置してもよい。
【００７８】
依頼装置１の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、計算装置２の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００７９】
依頼装置１及び計算装置２のそれぞれはコンピュータによって実現することができる。この場合、この装置が有すべき各機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これ装置における各処理機能が、コンピュータ上で実現される。
【００８０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００８１】
［第四実施形態］
第四実施形態から第十実施形態は、依頼装置１’が計算装置２’に依頼した計算の結果を用いてθ（ｇ，ｈ）を計算するものである。
【００８２】
第四実施形態の代理計算システムは、図１１に例示するように依頼装置１’及び計算装置２’を含み、依頼装置１’が計算装置２’に依頼した計算の結果を用いて双準同型写像θ（ｇ，ｈ）を計算する。
【００８３】
ここで、Ｇ、Ｈ及びＦを巡回群とし、写像θ：Ｇ×Ｈ→Ｆを双準同型写像とし、ｇを群Ｇの元とし、ｈを群Ｈの元とし、ＫＧを群Ｇの位数とし、ＫＨを群Ｈの位数とし、μｇを群Ｇの生成元とし、μｈを群Ｈの生成元とし、ν＝θ（μｇ，μｇ）とし、ｋを１以上の整数のセキュリティパラメータとし、Ｋ＝２ｋとする。
【００８４】
双準同型写像とは、２つの入力のそれぞれに対して準同型である写像を意味する。この例では、写像θ（ｇ，ｈ）は、群Ｇの元ｇに対して準同型であり、かつ、群Ｈの元ｈに対して準同型である。
【００８５】
依頼装置１’と計算装置２’との間には通信路が確立されており、依頼装置１’及び計算装置２’は双方向に通信可能である。この通信路は秘密に保たれている必要はなく、第三者がこの通信路を流れる情報を傍受することができてもよい。
【００８６】
依頼装置１’は信頼できない計算装置２’に乱数によって撹乱した情報を送信し、計算装置２’はその撹乱された情報を用いて一定のアルゴリズムに従って計算を行い、その計算結果を依頼装置１’に返信する。この計算装置２’への情報の送受信を繰り返すことにより、依頼装置１’は最終的にθ（ｇ，ｈ）を計算する。
【００８７】
依頼装置１’は、まずステップＳ１１’からステップＳ１２５’（図１５）の処理によりθ（ｇ，μｈ）と同等の情報（σ，ν’）を計算し、そのθ（ｇ，μｈ）と同等の情報（σ，ν’）を用いてステップＳ２１’からステップS２２５’の処理によりθ（ｇ，μ）を計算する。
【００８８】
依頼装置１’は、図１２及び図１３に例示する、第一乱数生成部１１’、第二乱数生成部１２’、第一入力情報計算部１３’、第二入力情報計算部１４’、第一リスト情報計算部１５’、第一リスト記憶部１６’、受信部１７’、送信部１８’、第四乱数生成部２１’、第五乱数生成部２２’、第三入力情報計算部２３’、第四入力情報計算部２４’、第二リスト情報計算部２５’、第二リスト記憶部２６’、第三乱数生成部２７’、第一判定部２８’、第六乱数生成部３１’、第七乱数生成部３２’、第五入力情報計算部３３’、第六入力情報計算部３４’、第三リスト情報計算部３５’、第三リスト記憶部３６’、第九乱数生成部４１’、第十乱数生成部４２’、第七入力情報計算部４３’、第八入力情報計算部４４’、第四リスト情報計算部４５’、第四リスト計算部４６’、第八乱数生成部４７’及び第二判定部４８’を例えば含む。
【００８９】
計算装置２’は、図１４に例示するように、受信部５１’、送信部５２’、第一出力情報計算部５３’、第二出力情報計算部５４’、第三出力情報計算部５５’及び第四出力情報計算部５６’を例えば含む。
【００９０】
＜ステップＳ１１’（図１５）＞
第一乱数生成部１１’は、０以上ＫＧ未満の整数の一様乱数であるｒ１を生成する（ステップＳ１１’）。生成された乱数ｒ１は、第一入力情報計算部１３’及び第一リスト情報計算部１５’に送られる。
【００９１】
＜ステップＳ１２’＞
第二乱数生成部１２’は、０以上ＫＨ未満の整数の一様乱数であるｒ２を生成する（ステップＳ１２’）。生成された乱数ｒ２は、第二入力情報計算部１４’、第一リスト情報計算部１５’及び第一リスト記憶部１６’に送られる。
【００９２】
＜ステップＳ１３’＞
第一入力情報計算部１３’は、第一入力情報ｇ１＝μｇｒ１ｇを計算する（ステップＳ１３’）。計算されたｇ１は送信部１８’に送られる。
ここで、μｇの右肩のｒ１は、ｒ１のことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。
【００９３】
また、ｇ１＝μｇｒ１ｇを計算するとは、μｇｒ１ｇという式で定義されるｇ１の値を計算することである。式μｇｒ１ｇの値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。
【００９４】
＜ステップＳ１４’＞
第二入力情報計算部１４’は、第二入力情報ｈ１＝μｈｒ２を計算する（ステップＳ１４’）。計算されたｈ１は送信部１８’に送られる。
【００９５】
＜ステップＳ１５’＞
送信部１８’は、第一入力情報ｇ１及び第二入力情報ｈ１を計算装置２’に送信する（ステップＳ１５’）。
【００９６】
＜ステップＳ１６’＞
計算装置２’の受信部５１’（図１４）は、第一入力情報ｇ１及び第二入力情報ｈ１を受信する（ステップＳ１６’）。
【００９７】
＜ステップＳ１７’＞
第一出力情報計算部５３’は、第一入力情報ｇ１及び第二入力情報ｈ１を用いて計算を行い、その計算結果を第一出力情報ｚ１とする（ステップＳ１７’）。ｚ１は、送信部５２’に送られる。
【００９８】
第一出力情報計算部５３’は、θ（ｇ１，ｈ１）を計算可能である。第一出力情報計算部５３’による計算の結果がθ（ｇ１，ｈ１）であることもあれば、θ（ｇ１，ｈ１）でないこともある。
【００９９】
この出願において、計算可能とは、無視することができない確率で計算することができることを意味する。無視することができない確率とは、セキュリティパラメータｋについての広義単調増加関数である多項式を多項式ｆ（ｋ）として、１／ｆ（ｋ）以上の確率である。
【０１００】
＜ステップＳ１８’＞
送信部５２’は、第一出力情報ｚ１を依頼装置１’に送信する（ステップＳ１８’）。
【０１０１】
＜ステップＳ１９’＞
依頼装置１’の受信部１７’（図１２）は、第一出力情報ｚ１を受信する（ステップＳ１９’）。受信した第一出力情報ｚ１は、第一リスト情報計算部１５’に送られる。ここでは、第一出力情報ｚ１は群Ｆの元であるとする。
【０１０２】
＜ステップＳ１１０’＞
第一リスト情報計算部１５’は、乱数ｒ１、乱数ｒ２及び第一出力情報ｚ１を用いて、ｚ１ν−ｒ１ｒ２を計算する（ステップＳ１１０’）。計算されたｚ１ν−ｒ１ｒ２は、第一リスト記憶部１６’に送られる。
【０１０３】
＜ステップＳ１１１’＞
乱数ｒ２と、ｚ１ν−ｒ１ｒ２とから構成される情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）がリストＬ１に追加される。この例では、第一リスト記憶部１６’に、情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）が記憶される（ステップＳ１１１’）。
【０１０４】
＜ステップＳ１１２’＞
第三乱数生成部２７’は、０以上Ｋ未満の整数の一様乱数であるｄ１を生成する（ステップＳ１１２’）。生成された乱数ｄ１は、第三入力情報計算部２３’及び第二リスト記憶部２６’に送られる。
【０１０５】
＜ステップＳ１１３’＞
第四乱数生成部２１’は、０以上ＫＧ未満の整数の一様乱数であるｒ４を生成する（ステップＳ１１３’）。生成された乱数ｒ４は、第三入力情報計算部２３’及び第二リスト情報計算部２５’に送られる。
【０１０６】
＜ステップＳ１１４’＞
第五乱数生成部２２’は、０以上ＫＨ未満の整数の一様乱数であるｒ５を生成する（ステップＳ１１４’）。生成された乱数ｒ５は、第四入力情報計算部２４’、第二リスト情報計算部２５’及び第二リスト記憶部２６’に送られる。
【０１０７】
＜ステップＳ１１５’＞
第三入力情報計算部２３’は、第三入力情報ｇ２＝μｇｒ４ｇｄ１を計算する（ステップＳ１１５’）。計算された第三入力情報ｇ２は、送信部１８’に送られる。
【０１０８】
＜ステップＳ１１６’＞
第四入力情報計算部２４’は、第四入力情報ｈ２＝μｈｒ５を計算する（ステップＳ１１６’）。計算された第四入力情報ｈ２は、送信部１８’に送られる。
【０１０９】
＜ステップＳ１１７’＞
送信部１８’は、第三入力情報ｇ２及び第四入力情報ｈ２を計算装置２’に送信する（ステップＳ１１７’）。
【０１１０】
＜ステップＳ１１８’＞
計算装置２’の受信部５１’（図１４）は、第三入力情報ｇ２及び第四入力情報ｈ２を受信する（ステップＳ１１８’）。
【０１１１】
＜ステップＳ１１９’＞
第二出力情報計算部５４’は、第三入力情報ｇ２及び第三入力情報ｈ２を用いて計算を行い、その計算結果を第二出力情報ｚ２とする（ステップＳ１１９’）。ｚ２は、送信部５２’に送られる。
第二出力情報計算部５４’は、θ（ｇ２，ｈ２）を計算可能である。第二出力情報計算部５４’による計算の結果がθ（ｇ２，ｈ２）であることもあれば、θ（ｇ２，ｈ２）でないこともある。
【０１１２】
＜ステップＳ１２０’＞
送信部５２’は、第二出力情報ｚ２を依頼装置１’に送信する（ステップＳ１２０’）。
【０１１３】
＜ステップＳ１２１’＞
依頼装置１’の受信部１７’（図１２）は、第二出力情報ｚ２を受信する（ステップＳ１２１’）。受信した第二出力情報ｚ２は、第二リスト情報計算部２５’に送られる。ここでは、第二出力情報ｚ２は群Ｆの元であるとする。
【０１１４】
＜ステップＳ１２２’＞
第二リスト情報計算部２５’は、乱数ｒ４、乱数ｒ５及び第二出力情報ｚ２を用いて、ｚ２ν−ｒ４ｒ５を計算する（ステップＳ１２２’）。計算されたｚ２ν−ｒ４ｒ５は、第二リスト記憶部２６’に送られる。
【０１１５】
＜ステップＳ１２３’＞
乱数ｄ１と、乱数ｒ５と、ｚ２ν−ｒ４ｒ５とから構成される情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）が、リストＬ２に追加される。この例では、第二リスト記憶部２６’には、情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）が記憶される（ステップＳ１２３’）。  
【０１１６】
＜ステップＳ１２４’＞
第一判定部２８’は、第一リスト記憶部１６’から読み込んだ情報の組の第一成分をｓ１とし、第二成分をｗ１とし、第二リスト記憶部２６’から読み込んだ情報の組の第一成分をｔ２とし、第二成分をｓ２とし、第三成分をｗ２として、これらの情報の組が（ｗ１）＾（ｔ２ｓ２ｓ１−１）＝ｗ２の関係を満たすかを判定する（ステップＳ１２４’）。
【０１１７】
第一判定部２８’は、第一リスト記憶部１６’及び第二リスト記憶部２６’に複数の情報の組が記憶されている場合には、第一リスト記憶部１６’に記憶された情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）と、第二リスト記憶部２６’に記憶された情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）とから構成されるすべての情報のペアについて、上記関係を満たすかどうかを判定する。もちろん、既に上記関係を満たすかどうかを判定した情報のペアについては、その判定処理を省いてもよい。
【０１１８】
＜ステップＳ１２５’＞
第一判定部２８’は、上記の関係を満たす場合には、ｓ１をσに代入し、ｗ１をν’に代入する（ステップＳ１２５’）。ここで、ν’１／σ＝ｗ１１／σ＝θ（ｇ，μｈ）となる。ν’１／σ＝θ（ｇ，μｈ）となる理由については後述する。
上記の関係を満たさない場合には、ステップＳ１１’に戻る。
【０１１９】
＜ステップＳ２１’（図１６）＞
第六乱数生成部３１’は、０以上ＫＧ未満の整数の一様乱数であるｒ６を生成する（ステップＳ２１’）。生成された乱数ｒ６は、第五入力情報計算部３３’、第三リスト情報計算部３５’及び第三リスト記憶部３６’に送られる。
【０１２０】
＜ステップＳ２２’＞
第七乱数生成部３２’は、０以上ＫＨ未満の整数の一様乱数であるｒ７を生成する（ステップＳ２２’）。生成された乱数ｒ７は、第六入力情報計算部３４’及び第三リスト情報計算部３５’に送られる。
【０１２１】
＜ステップＳ２３’＞
第五入力情報計算部３３’は、第五入力情報ｇ３＝μｇｒ６を計算する（ステップＳ２３’）。計算されたｇ３は送信部１８’に送られる。
【０１２２】
＜ステップＳ２４’＞
第六入力情報計算部３４’は、第六入力情報ｈ３＝μｈｒ７σｈを計算する（ステップＳ２４’）。計算されたｈ３は送信部１８’に送られる。
【０１２３】
＜ステップＳ２５’＞
送信部１８’は、第五入力情報ｇ３及び第六入力情報ｈ３を計算装置２’に送信する（ステップＳ２５’）。
【０１２４】
＜ステップＳ２６’＞
計算装置２’の受信部５１’（図１４）は、第五入力情報ｇ３及び第六入力情報ｈ３を受信する（ステップＳ２６’）。
【０１２５】
＜ステップＳ２７’＞
第三出力情報計算部５５’は、第五入力情報ｇ３及び第六入力情報ｈ３を用いて計算を行い、その計算結果を第三出力情報ｚ３とする（ステップＳ２７’）。ｚ３は、送信部５２’に送られる。
第三出力情報計算部５５’は、θ（ｇ３，ｈ３）を計算可能である。第三出力情報計算部５５’による計算の結果がθ（ｇ３，ｈ３）であることもあれば、θ（ｇ３，ｈ３）でないこともある。
【０１２６】
＜ステップＳ２８’＞
送信部５２’は、第三出力情報ｚ３を依頼装置１’に送信する（ステップＳ２８’）。
【０１２７】
＜ステップＳ２９’＞
依頼装置１’の受信部１７’（図１３）は、第三出力情報ｚ３を受信する（ステップＳ２９’）。受信した第三出力情報ｚ３は、第三リスト情報計算部３５’に送られる。ここでは、第３出力情報ｚ３は群Ｆの元であるとする。
【０１２８】
＜ステップＳ２１０’＞
第三リスト情報計算部３５’は、乱数ｒ６、乱数ｒ７及び第三出力情報ｚ３を用いて、ｚ３ν’−ｒ６ｒ７を計算する（ステップＳ２１０’）。計算されたｚ３ν−ｒ６ｒ７は、第三リスト記憶部３６’に送られる。
【０１２９】
＜ステップＳ２１１’＞
乱数ｒ６と、ｚ３ν’−ｒ６ｒ７とから構成される情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）がリストＬ３に追加される。この例では、第三リスト記憶部３６’に、情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）が記憶される（ステップＳ２１１’）。
【０１３０】
＜ステップＳ２１２’＞
第八乱数生成部４７’は、０以上Ｋ未満の整数の一様乱数であるｄ２を生成する（ステップＳ２１２’）。生成された乱数ｄ２は、第八入力情報計算部４４及び第四リスト記憶部４６’に送られる。
【０１３１】
＜ステップＳ２１３’＞
第九乱数生成部４１’は、０以上ＫＧ未満の整数の一様乱数であるｒ９を生成する（ステップＳ２１３’）。生成された乱数ｒ９は、第七入力情報計算部４３’、第四リスト情報計算部４５’及び第四リスト記憶部４６’に送られる。
【０１３２】
＜ステップＳ２１４’＞
第十乱数生成部４２’は、０以上ＫＨ未満の整数の一様乱数であるｒ１０を生成する（ステップＳ２１４’）。生成された乱数ｒ１０は、第八入力情報計算部４４’、第四リスト情報計算部４５’及び第四リスト記憶部４６’に送られる。
【０１３３】
＜ステップＳ２１５’＞
第七入力情報計算部４３’は、第七入力情報ｇ４＝ｇｒ９を計算する（ステップＳ２１５’）。計算された第七入力情報ｇ４は、送信部１８’に送られる。
【０１３４】
＜ステップＳ２１６’＞
第八入力情報計算部４４’は、第八入力情報ｈ４＝μｈｒ１０σｈｄ２を計算する（ステップＳ２１６’）。計算された第八入力情報ｈ４は、送信部１８’に送られる。
【０１３５】
＜ステップＳ２１７’＞
送信部１８’は、第七入力情報ｇ４及び第八入力情報ｈ４を計算装置２’に送信する（ステップＳ２１７’）。
【０１３６】
＜ステップＳ２１８’＞
計算装置２’の受信部５１’（図１４）は、第七入力情報ｇ４及び第八入力情報ｈ４を受信する（ステップＳ２１８’）。
【０１３７】
＜ステップＳ２１９’＞
第四出力情報計算部５６’は、第七入力情報ｇ４及び第八入力情報ｈ４を用いて計算を行い、その計算結果を第四出力情報ｚ４とする（ステップＳ２１９’）。ｚ４は、送信部５２’に送られる。
第四出力情報計算部５６’は、θ（ｇ４，ｈ４）を計算可能である。第四出力情報計算部５６’による計算の結果がθ（ｇ４，ｈ４）であることもあれば、θ（ｇ４，ｈ４）でないこともある。
【０１３８】
＜ステップＳ２２０’＞
送信部５２’は、第四出力情報ｚ４を依頼装置１’に送信する（ステップＳ２２０’）。
【０１３９】
＜ステップＳ２２１’＞
依頼装置１’の受信部１７’（図１２）は、第四出力情報ｚ４を受信する（ステップＳ２２１）。受信した第四出力情報ｚ４は、第四リスト情報計算部４５’に送られる。ここでは、第四出力情報ｚ４は群Ｆの元であるとする。
【０１４０】
＜ステップＳ２２２’＞
第四リスト情報計算部４５’は、乱数ｒ９、乱数ｒ１０及び第四出力情報ｚ４を用いて、ｚ４ν’−ｒ９ｒ１０を計算する（ステップＳ２２２’）。計算されたｚ４ν’−ｒ９ｒ１０は、第四リスト記憶部４６’に送られる。
【０１４１】
＜ステップＳ２２３’＞
乱数ｄ２と、乱数ｒ９と、ｚ４ν−ｒ９ｒ１０とから構成される情報の組（ｄ２，ｒ９，ｚ４ν’−ｒ９ｒ１０）が、リストＬ４に追加される。この例では、第四リスト記憶部４６’に、情報の組（ｄ２，ｒ９，ｚ４ν−ｒ９ｒ１０）が記憶される（ステップＳ２２３’）。
【０１４２】
＜ステップＳ２２４’＞
第二判定部４８’は、第三リスト記憶部３６’から読み込んだ情報の組の第一成分をｓ３とし、第二成分をｗ３とし、第四リスト記憶部４６’から読み込んだ情報の組の第一成分をｔ４とし、第二成分をｓ４とし、第三成分をｗ４として、これらの情報の組が（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４の関係を満たすかを判定する（ステップＳ２２４’）。
【０１４３】
第二判定部４８’は、第三リスト記憶部３６’及び第四リスト記憶部４６’に複数の情報の組が記憶されている場合には、第三リスト記憶部３６’に記憶された情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）と、第四リスト記憶部４６’に記憶された情報の組（ｄ２，ｒ９，ｚ４ν’−ｒ９ｒ１０）とから構成されるすべての情報のペアについて、上記関係を満たすかどうかを判定する。もちろん、既に上記関係を満たすかどうかを判定した情報のペアについては、その判定処理を省いてもよい。
【０１４４】
＜ステップＳ２２５’＞
第二判定部４８’は、上記の関係を満たす場合には、（ｗ３）＾（ｓ３−１）を出力する（ステップＳ２２５’）。ここで、（ｗ３）＾（ｓ３−１）＝θ（ｇ，ｈ）となる。（ｗ３）＾（ｓ３−１）＝θ（ｇ，ｈ）となる理由については後述する。
上記の関係を満たさない場合には、ステップＳ２１’に戻る。
【０１４５】
（ｗ３）＾（ｓ３−１）の計算、すなわちｗ３のべき乗根の計算が困難な場合には、次のようにしてθ（ｇ，ｈ）を容易に計算することができる。第二判定部４８’は、ステップＳ２１’からステップＳ２２４’の処理を繰り返して（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４の関係を満たすｗ３とｓ３との組（ｗ３，ｓ３）を順次（α１，Ｓ１），（α２，Ｓ２），…，（αｍ，Ｓｍ），…として記憶部４１０’に記憶する。ｍは自然数である。第二判定部４８’は、Ｓ１と互いに素となるＳｍが見つかれば、Ｌ１とＬ２とを整数としてＬ１Ｓ１＋Ｌ２Ｓｍ＝１となるＬ１及びＬ２を計算して、そのＬ１及びＬ２を用いてα１Ｌ１αｍＬ２を計算する。α１Ｌ１αｍＬ２＝θ（ｇ，ｈ）（Ｌ１Ｓ１＋Ｌ２Ｓ２）＝θ（ｇ，ｈ）となる。また、第二判定部４８’は、Ｓ１，Ｓ２，…，Ｓｍの最小公倍数が１になれば、Ｌ１，Ｌ２，…，Ｌｍを整数としてＬ１Ｓ１＋Ｌ２Ｓ２＋…＋ＬｍＳｍ＝１となるＬ１，Ｌ２，…，Ｌｍを計算して、そのＬ１，Ｌ２，…，Ｌｍを用いてα１Ｌ１α２Ｌ２…αｍＬｍを計算してもよい。α１Ｌ１α２Ｌ２…αｍＬｍ＝θ（ｇ，ｈ）（Ｌ１Ｓ１＋Ｌ２Ｓ２＋…＋ＬｍＳｍ）＝θ（ｇ，ｈ）となる。
【０１４６】
依頼装置１’と計算装置２’との間の通信を傍受することができる攻撃者Ｍがいるとしても、依頼装置１’及び計算装置２’との間で通信される情報を、依頼装置１’のみが知る乱数（例えば、ｒ１，ｒ２）で撹乱することにより、攻撃者Ｍから秘匿することができる。
【０１４７】
また、依頼装置１’及び計算装置２’との間で通信される情報は依頼装置１’のみが知るｒ１，ｒ２等の乱数で撹乱されているため、計算装置２’は、依頼装置１’が最終的に計算しようとするθ（ｇ，ｈ）はもちろんのこと、その入力であるｇ及びｈをも知ることはできない。
【０１４８】
したがって、計算装置２’は信頼することができる計算機である必要はなく、双準同型写像を計算するためのシステムの構成要件を緩和することができる。また、信頼することができる計算機は一般に高価であり運用に費用を要するが、計算装置２’が信頼することができる計算機である必要ないため、双準同型写像を計算するためのシステムの構築及び運用のコストを削減することができる。
【０１４９】
≪ν’１／σ＝θ（ｇ，μｈ）となる理由について≫
まず、ｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒと呼ばれる確率変数ＳＸ（ｄ）について説明する。ｗ∈Ｆに関する誤差Ｘのｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒである確率変数ＳＸ（ｄ）は、ＳＸ（ｄ）＝ｗｄＸである。ｄは自然数である。
【０１５０】
ここで、Ｒ１，Ｒ２，Ｒ１’及びＲ２’を乱数として、計算装置がｇｄμｇＲ１及びμｈＲ２を用いて行う計算の計算結果をＢ（ｇｄμｇＲ１，μｈＲ２）（計算装置が依頼装置に返す計算結果をｚとすると、ｚ＝Ｂ（ｇｄμｇＲ１，μｈＲ２）である。）とし、群Ｆに値を持つ確率変数ＸをＸ＝Ｂ（μｇＲ’１，μｈＲ’２）１／Ｒ’２θ（μｇＲ’１，μｈ）−１と定義すると、ＳＸ（ｄ）＝ｚ（１／Ｒ２）ν−Ｒ１は、θ（ｇ，μｈ）に関する誤差Ｘのｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒとなる。
【０１５１】
ＳＸ（ｄ）＝ｚ（１／Ｒ２）ν−Ｒ１＝Ｂ（ｇｄμｇＲ１，μｈＲ２）１／Ｒ２θ（μｇ，μｈ）−Ｒ１＝Ｘθ（ｇｄμｇＲ１，μｈ）θ（μｇＲ１，μｈ）−１＝Ｘθ（ｇｄ，μｈ）θ（μｇＲ１，μｈ）θ（μｇＲ１，μｈ）−１＝θ（ｇ，μｈ）ｄＸであるためである。
【０１５２】
上記式展開において、Ｘ＝Ｂ（μｇＲ’１，μｈＲ’２）１／Ｒ’２θ（μｇＲ’１，μｈ）−１＝Ｂ（ｇｄμｇＲ１，μｈＲ２）１／Ｒ２θ（ｇｄμｇＲ１，μｈ）−１であり、Ｂ（ｇｄμｇＲ１，μｈＲ２）１／Ｒ２＝Ｘθ（ｇｄμｇＲ１，μｈ）であるという性質を用いている。この性質は、Ｒ１，Ｒ２，Ｒ１’及びＲ２’が乱数であることに基づく。
【０１５３】
ここで、ＳＸ（１）の実現値をθ（ｇ，μｈ）１ｘ１と表記し、ＳＸ（ｄ）の実現値をθ（ｇ，μｈ）ｄｘ２と表記するとして、ＳＸ（１）の実現値のｄ乗＝ＳＸ（ｄ）の実現値、すなわち（θ（ｇ，μｈ）１ｘ１）ｄ＝θ（ｇ，μｈ）ｄｘ２となるのは、ｘ１及びｘ２が群Ｆの単位元ｅｆのときである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。ｘ１が群Ｆの単位元ｅｆのとき、ＳＸ（１）の実現値＝θ（ｇ，μｈ）１ｘ１＝θ（ｇ，μｈ）となる。
【０１５４】
上記実施形態の代理計算システムは、このｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒの性質を用いている。
【０１５５】
ステップＳ１１’からステップＳ１１１’の処理がＳＸ（１）の実現値θ（ｇ，μｈ）１ｘ１の計算に対応している。実際には、ＳＸ（１）の実現値自体は計算していないが、同処理により得られる（ｒ２，ｚ１ν−ｒ１ｒ２）を用いて、ｚ１ν−ｒ１ｒ２を１／ｒ２乗すると、（ｚ１ν−ｒ１ｒ２）１／ｒ２＝ｚ１１／ｒ２ν−ｒ１となり、ＳＸ（１）の実現値θ（ｇ，μｈ）１ｘ１となる。同様に、ステップＳ１１２’からステップＳ１２３’の処理がＳＸ（ｄ１）の実現値θ（ｇ，μｈ）ｄ１ｘ２の計算に対応している。
【０１５６】
また、ステップＳ１２４’の処理が、ＳＸ（１）の実現値のｄ１乗＝ＳＸ（ｄ１）、すなわち（θ（ｇ，μｈ）１ｘ１）ｄ１＝θ（ｇ，μｈ）ｄ１ｘ２であるかどうかの判定に対応している。ステップＳ１２４で用いる判定条件（ｗ１）＾（ｔ２ｓ２ｓ１−１）は、（ｗ１）＾（ｔ２ｓ２ｓ１−１）＝ｗ２⇔（ｗ１１／ｓ１）ｔ２＝ｗ２１／ｓ２⇔（ｚ１１／ｒ２ν−ｒ１）ｄ１＝ｚ２１／ｒ５ν−ｒ４⇔（θ（ｇ，μｈ）１ｘ１）ｄ１＝θ（ｇ，μｈ）ｄ１ｘ２⇔ＳＸ（１）の実現値のｄ１乗＝ＳＸ（ｄ１）の実現値であるためである。ここで、定義よりｓ１＝ｒ２、ｗ１＝ｚ１ν−ｒ１ｒ２、ｔ２＝ｄ１、ｓ２＝ｒ５、ｗ２＝ｚ２ν−ｒ４ｒ５である。
【０１５７】
さらに、ステップＳ１２５’におけるσ及びν’が、θ（ｇ，μｈ）に対応している。上記したようにＳＸ（１）の実現値のｄ１乗＝ＳＸ（ｄ１）の実現値のとき、ν’１／σ＝ｗ１１／ｓ１＝ｚ１１／ｒ２ν−ｒ１＝θ（ｇ，μｈ）１ｘ１＝θ（ｇ，μｈ）であるためである。
【０１５８】
≪（ｗ３）＾（ｓ３−１）＝θ（ｇ，ｈ）となる理由について≫
Ｒ１，Ｒ２，Ｒ１’及びＲ２’を乱数として、計算装置がｇＲ１及びｈｄμｈＲ２を用いて行う計算の計算結果をＢ（ｇＲ１，ｈｄμｈＲ２）（計算装置が依頼装置に返す計算結果をｚとすると、ｚ＝Ｂ（ｇＲ１，ｈｄμｈＲ２）である。）とし、群Ｆに値を持つ確率変数ＸをＸ＝Ｂ（ｇＲ’１，μｈＲ’２）１／Ｒ’１θ（ｇ，μｈＲ’２）−１と定義すると、ＳＸ（ｄ）＝ｚ（１／Ｒ１）ν’−Ｒ２は、θ（ｇ，ｈ）に関する誤差Ｘのｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒとなる。
【０１５９】
ＳＸ（ｄ）＝ｚ（１／Ｒ１）ν’−Ｒ２＝Ｂ（ｇＲ１，ｈｄμｈＲ２）１／Ｒ１θ（ｇ，μｈ）−Ｒ２＝Ｘθ（ｇ，ｈｄμｈＲ２）θ（ｇ，μｈＲ２）−１＝Ｘθ（ｇ，ｈｄ）θ（ｇ，μｈＲ２）θ（ｇ，μｈＲ２）−１＝θ（ｇ，ｈ）ｄＸであるためである。
【０１６０】
上記式展開において、Ｘ＝Ｂ（ｇＲ’１，μｈＲ’２）１／Ｒ’１θ（ｇ，μｈＲ’２）−１＝Ｂ（ｇＲ１，μｈＲ２）１／Ｒ１θ（ｇ，ｈｄμｈＲ２）−１であり、Ｂ（ｇＲ１，ｈｄμｈＲ２）１／Ｒ１＝Ｘθ（ｇ，ｈｄμｈＲ２）であるという性質を用いている。この性質は、Ｒ１，Ｒ２，Ｒ１’及びＲ２’が乱数であることに基づく。
【０１６１】
ここで、ＳＸ（１）の実現値をＳＸ（１）＝θ（ｇ，ｈ）１ｘ１と表記し、ＳＸ（ｄ）の実現値をＳＸ（ｄ）＝θ（ｇ，ｈ）ｄｘ２と表記するとして、ＳＸ（１）の実現値のｄ乗＝ＳＸ（ｄ）、すなわち（θ（ｇ，ｈ）１ｘ１）ｄ＝θ（ｇ，ｈ）ｄｘ２となるのは、ｘ１及びｘ２が群Ｆの単位元ｅｆのときである可能性が非常に高いことを発明者は見出した。ここでは、その証明は省略する。ｘ１が群Ｆの単位元ｅｆのとき、ＳＸ（１）の実現値＝θ（ｇ，ｈ）１ｘ１＝θ（ｇ，ｈ）となる。
【０１６２】
上記実施形態の代理計算システムは、このｒａｎｄｏｍｉｚａｂｌｅ  ｓａｍｐｌｅｒの性質を用いている。
【０１６３】
ステップＳ２１’からステップＳ２１１’の処理がＳＸ（１）の実現値θ（ｇ，ｈ）１ｘ１の計算に対応している。実際には、ＳＸ（１）の実現値自体は計算していないが、同処理により得られる（ｒ６，ｚ３ν’−ｒ６ｒ７）を用いて、ｚ３ν’−ｒ６ｒ７を１／ｒ６乗すると、（ｚ３ν’−ｒ６ｒ７）１／ｒ６＝ｚ３１／ｒ６ν’−ｒ７となり、ＳＸ（１）の実現値θ（ｇ，ｈ）１ｘ１となる。同様に、ステップＳ２１２’からステップＳ２２３’の処理がＳＸ（ｄ２）の実現値θ（ｇ，ｈ）ｄ２ｘ２の計算に対応している。
【０１６４】
また、ステップＳ２２４’の処理が、ＳＸ（１）の実現値のｄ２乗＝ＳＸ（ｄ２）の実現値、すなわち（θ（ｇ，ｈ）１ｘ１）ｄ２＝θ（ｇ，ｈ）ｄ２ｘ２であるかどうかの判定に対応している。ステップＳ２２４’で用いる判定条件（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４は、（ｗ３）＾（ｔ４ｓ４ｓ３−１）＝ｗ４⇔（ｗ３１／ｓ３）ｔ４＝ｗ４１／ｓ４⇔（ｚ３１／ｒ６ν’−ｒ７）ｄ２＝ｚ４１／ｒ９ν’−ｒ１０⇔（θ（ｇ，ｈ）１ｘ１）ｄ２＝θ（ｇ，ｈ）ｄ２ｘ２⇔ＳＸ（１）の実現値のｄ２乗＝ＳＸ（ｄ２）の実現値であるためである。ここで、定義よりｓ３＝ｒ６、ｗ３＝ｚ３ν’−ｒ６ｒ７、ｔ４＝ｄ２、ｓ４＝ｒ９、ｗ４＝ｚ４ν’−ｒ９ｒ１０である。
【０１６５】
さらに、ステップＳ２２５’における（ｗ３）＾（ｓ３−１）が、θ（ｇ，ｈ）に対応している。上記したようにＳＸ（１）の実現値のｄ２乗＝ＳＸ（ｄ２）の実現値のとき、（ｗ３）＾（ｓ３−１）＝（ｚ３ν’−ｒ６ｒ７）＾（ｒ６−１）＝ｚ３１／ｒ６ν’−ｒ７＝θ（ｇ，ｈ）１ｘ１＝θ（ｇ，ｈ）であるためである。
【０１６６】
［第五実施形態］
第五実施形態の代理計算システムは、ステップＳ１３’、ステップＳ１１０’及びステップＳ１１１’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。
【０１６７】
第一入力情報計算部１３’は、ｇ１＝μｇｒ１ｇではなく、ｇ１＝ｇｒ１で定義される第一入力情報を計算する（ステップＳ１３’）。
第一リスト情報計算部１５’は、ｚ１ν−ｒ１ｒ２ではなく、乱数ｒ１及び乱数ｒ２を用いてｒ１ｒ２を計算して、その計算結果を第一リスト記憶部１６’に送る（ステップＳ１１０’）。
第一リスト記憶部１６’には、情報の組（ｒ２，ｚ１ν−ｒ１ｒ２）ではなく、計算されたｒ１ｒ２と計算装置２’から受信したｚ１∈Ｆとから構成される情報の組（ｒ１ｒ２，ｚ１）が記憶される（ステップＳ１１１’）。
【０１６８】
第四実施形態のステップＳ１１０’では、ｚ１ν−ｒ１ｒ２という群Ｆのべき演算を行う必要があったが、第五実施形態のステップＳ１１０’ではｒ１ｒ２の計算を行っておりべき演算の回数が１回減っている。このように、べき演算の回数を減らすことにより演算の効率性を増すことができる。また、群Ｇ、群Ｈにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。
【０１６９】
［第六実施形態］
第六実施形態の代理計算システムは、ステップＳ２４’、ステップＳ２１０’及びステップＳ２１１’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。
【０１７０】
第六入力情報計算部３４’は、ｈ３＝μｈｒ７σｈではなく、ｈ３＝ｈｒ７で定義される第六入力情報ｈ３を計算する（ステップＳ２４’）。
第三リスト情報計算部３５’は、ｚ３ν’−ｒ６ｒ７ではなく、乱数ｒ６及び乱数ｒ７を用いてｒ６ｒ７を計算する（ステップＳ２１０’）。
第三リスト記憶部３６’には、情報の組（ｒ６，ｚ３ν’−ｒ６ｒ７）ではなく、計算されたｒ６ｒ７と計算装置２’から受信したｚ３∈Ｆとから構成される情報の組（ｒ６ｒ７，ｚ３）が記憶される（ステップＳ２１１’）。
【０１７１】
第四実施形態のステップＳ２１０’では、ｚ３ν’−ｒ６ｒ７という群Ｆのべき演算を行う必要があったが、第六実施形態のステップＳ２１０’ではｒ６ｒ７の計算を行っておりべき演算の回数が１回減っている。このように、べき演算の回数を減らすことにより演算の効率性を増すことができる。
【０１７２】
群Ｇ、群Ｈにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。
【０１７３】
［第七実施形態］
第七実施形態の代理計算システムは、ステップＳ１２５’及びステップＳ２１４’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。
第一判定部２８’は、上記の関係を満たす場合には、ｔ１ｓ２をσに代入し、ｗ２をν’に代入する（ステップＳ１２５’）。
第十乱数生成部４２’は、乱数ｒ９を用いて−ｒ９−１を計算してｒ１０とする（ステップＳ２１４’）。
【０１７４】
このように、ν’の定義を変更して、σを計算装置２’にとって推測が困難な乱数とすることにより安全性が増す。また、乱数ｒ９を用いて乱数ｒ１０を計算することにより、乱数を生成する回数を減らすことができる。乱数ｒ１０が乱数ｒ９により定まるため第八入力情報ｈ４＝μｈｒ１０σｈｄ２の乱雑性が低下し安全性が損なわれるとも思われるが、第八入力情報ｈ４＝μｈｒ１０σｈｄ２は乱数ｒ１０だけでなく更にσにより撹乱されているため安全性は損なわれない。
【０１７５】
なお、第七実施形態においては更にステップＳ２２’及びステップＳ２１１’を以下のように変更してもよい。
【０１７６】
第七乱数生成部３２’は、乱数ｒ６を用いて−ｒ６−１を計算してｒ７とする（ステップＳ２２’）。
第三リスト記憶部３６’には、１と上記計算されたｚ３ν’−ｒ６ｒ７とから構成される情報の組（１，ｚ３ν’−ｒ６ｒ７）が記憶される（ステップＳ２１１’）。
【０１７７】
このように、乱数ｒ６を用いて乱数ｒ７を計算することにより乱数を生成する回数を減らすことができる。
群Ｇ、群Ｈにおいて非自明べき根の計算が困難であるならば、第四実施形態と比較して安全性は低下しない。
【０１７８】
［第八実施形態］
第八実施形態の代理計算システムは、ステップＳ１１３’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。
【０１７９】
まず、ステップＳ１１３’に先立ち、第五乱数生成部２２’は乱数ｒ５を生成する（ステップＳ１１４’）。
第四乱数生成部２１’は、乱数ｒ５を用いて−ｒ５−１を計算してｒ４とする（ステップＳ１１３’）。
このように、乱数ｒ５を用いて乱数ｒ４を計算することにより乱数を生成する回数を減らすことができる。
【０１８０】
群Ｈの任意の元ｈについて、ｇ∈Ｇでθ（ｇ，ｈ）＝νとなるものを計算することが困難ならば、第四実施形態と比較して安全性は低下しない。
【０１８１】
［第九実施形態］
第九実施形態の代理計算システムは、依頼装置１’が図１２に破線で示された事前計算部２９’を更に含み、ステップＳ１１５’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。
【０１８２】
事前計算部２９’は、第三乱数生成部２７’が生成したｄ１を用いてｇｄ１を計算する。この処理は、ステップＳ１１２’の後、ステップＳ１１５’の前に行う。
第三入力情報計算部２３’は、事前計算されたｇｄ１を用いて、ｇ２＝μｇｒ４ｇｄ１の計算を行う（ステップＳ１１５’）。
【０１８３】
ステップＳ１１４’で、判定条件を満たさない場合にはステップＳ１１’からステップＳ１２３’の処理が繰り返されるが、この繰り返しの処理においては、事前計算されたｇｄ１を再利用する。すなわち、第三乱数生成部２７’は乱数ｄ１を生成せず、第三入力情報計算部２３’は事前計算されたｇｄ１を用いて、ｇ２＝μｇｒ４ｇｄ１の計算を行う。これにより、乱数ｄ１を生成する回数を減らすことができ、ｇ２＝μｇｒ４ｇｄ１の計算を速く行うことができる。
【０１８４】
［第十実施形態］
第十実施形態の代理計算システムは、依頼装置１’が図１３に破線で示された事前計算部４９’を更に含み、ステップＳ２１６’が第四実施形態の代理計算システムとは異なり、他の部分については第四実施形態の代理計算システムと同様である。以下、第四実施形態と異なる部分を中心に説明する。
【０１８５】
事前計算部４９’は、第八乱数生成部４７’が生成したｄ２を用いてｈｄ２を計算する。この処理は、ステップＳ２１２’の後、ステップＳ２１６’の前に行う。
第八入力情報計算部４４’は、事前計算されたｈｄ２を用いて、第八入力情報ｈ４＝μｈｒ１０σｈｄ２の計算を行う（ステップＳ１１６’）。
【０１８６】
ステップＳ２１４’で、判定条件を満たさない場合にはステップＳ２１’からステップＳ２２３’の処理が繰り返されるが、この繰り返しの処理においては、事前計算されたｈｄ２を再利用する。すなわち、第八乱数生成部４７’は乱数ｄ２を生成せず、第八入力情報計算部４４’は事前計算されたｈｄ２を用いて、ｈ４＝μｈｒ１０σｈｄ２の計算を行う。これにより、乱数ｄ２を生成する回数を減らすことができ、ｈ４＝μｈｒ１０σｈｄ２の計算を速く行うことができる。
【０１８７】
［第四実施形態から第十実施形態の変形例等］
第一乱数生成部１１’、第二乱数生成部１２’、第三乱数生成部２７’、第四乱数生成部２１’、第五乱数生成部２２’、第六乱数生成部３１’、第七乱数生成部３２’、第八乱数生成部４７’、第九乱数生成部４１’及び第十乱数生成部４２’のそれぞれは、一様乱数を生成することにより、代理計算システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部１１’、第二乱数生成部１２’、第三乱数生成部２７’、第四乱数生成部２１’、第五乱数生成部２２’、第六乱数生成部３１’、第七乱数生成部３２’、第八乱数生成部４７’、第九乱数生成部４１’及び第十乱数生成部４２’のそれぞれは、一様乱数ではない乱数を生成してもよい。
【０１８８】
リストＬ１、リストＬ２に情報の組が追加される毎に、第一判定部２８’の処理を行ってもよい。例えば、第二リスト記憶部２６’に情報の組（ｄ１，ｒ５，ｚ２ν−ｒ４ｒ５）が記憶されている場合には、ステップＳ１１１’の後に、ステップＳ１２４’の処理を行っても良い。同様に、リストＬ３、リストＬ４に情報の組が追加される毎に、第二判定部４８’の処理を行ってもよい。
【０１８９】
第四実施形態から第十実施形態は互いに組み合わせることができる。
【０１９０】
依頼装置１’の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、計算装置２’の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【０１９１】
依頼装置１’及び計算装置２’のそれぞれはコンピュータによって実現することができる。この場合、この装置が有すべき各機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これ装置における各処理機能が、コンピュータ上で実現される。
【０１９２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１９３】
なお、第一実施形態から第三実施形態と、第四実施形態から第十実施形態とを組み合わせてもよい。例えば、図１７に例示するように、第一実施形態から第三実施形態の計算装置２が第四実施形態から第十実施形態の依頼装置１’を備えており、この依頼装置１’を含む計算装置２が、第四実施形態から第十実施形態で説明したのと同様にして計算装置２’を用いて、関数ｆの計算を行ってもよい。
【０１９４】
具体的には、計算装置２は計算する必要がある関数ｆ（ｘ）を計算するために、対応する写像θ（ｇ，ｈ）の値を、計算装置２’を用いて計算する。関数ｆ（ｘ）に対応する写像θ（ｇ，ｈ）とは、与えられた関数ｆ及びｘに対して、関数ｆ（ｘ）と値が同じ値を出力する写像θ（ｇ，ｈ）である。ある元ｈ∈Ｈに関して、ｆ（ｘ）＝θ（ｘ，ｈ）という関係がある場合には、ｆ（ｘ）に対応する写像θがθ（ｘ，ｈ）となる。
【０１９５】
例えば、参考文献１に記載されたＢｏｎｅｈ−Ｆｒａｎｋｌｉｎ方式のＩＤベース暗号において、ある一定のＩＤに関する復号関数をｆとする。この方式のＩＤベース暗号では、楕円曲線の点がなす有限群Ｇ，Ｈと、ペアリングτ：Ｇ×Ｈ→Ｆを用いて構成される。ＱをＧの元とする。ＩＤベース暗号の鍵発行センタの秘密鍵をｓとして、公開鍵をＰ＝ｓＱとする。ＩＤベース暗号のパブリックパラメータは、群Ｇ，Ｈの記述と、ペアリングτの記述、Ｑ及びＰである。
【０１９６】
〔参考文献１〕Dan Boneh, Matt Franklin, “Identity-Based Encryption from the Weil Pairing”, CRYPTO 2001, LNCS 2139, pp.213-229, 2001.
鍵の発行は以下のようにして行われる。鍵発行センタは、ＩＤに対応して定まるＨの元ＱＩＤについて、ＰＩＤ＝ｓＱＩＤを計算してＩＤの保持者に対して通知する。ＰＩＤはＩＤの保持者の秘密鍵である。このとき、復号関数ｆ：Ｇ→Ｆは、ｆ（ｘ）＝τ（ｘ，ＰＩＤ）で定義される。
【０１９７】
暗号文の作成、暗号文の復号は以下のようにして行われる。平文ｍをあるＩＤについて暗号化するためには、乱数ｒを生成して（Ｑｒ，ｍ（＋）Ｈ（τ（Ｐｒ，ＱＩＤ）））を計算し、これを暗号文（Ｃ１，Ｃ２）とする。復号するためには、暗号文（Ｃ１，Ｃ２）に対して、Ｃ２（＋）Ｈ（ｆ（Ｃ１））を計算することで平文が得られる。ただし、ここでＨはハッシュ関数、（＋）は排他的論理和である。
【０１９８】
このようなＢｏｎｅｈ−Ｆｒａｎｋｌｉｎ方式のＩＤベース暗号において、関数ｆ（ｘ）に対応する写像θは例えばペアリングτを用いて定義される。すなわち、ｆ（ｘ）＝τ（ｘ，ＰＩＤ）である。
【０１９９】
計算装置２がＩＣカードや携帯電話であり、秘密情報の抽出が困難であるが、計算能力が限定されている場合に、このように依頼装置及び計算装置を多重にして組み合わせることが有益である。
【０２００】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図１】
2011086992.tif 000003
【図２】
2011086992.tif 000004
【図３】
2011086992.tif 000005
【図４】
2011086992.tif 000006
【図５】
2011086992.tif 000007
【図６】
2011086992.tif 000008
【図７】
2011086992.tif 000009
【図８】
2011086992.tif 000010
【図９】
2011086992.tif 000011
【図１０】
2011086992.tif 000012
【図１１】
2011086992.tif 000013
【図１２】
2011086992.tif 000014
【図１３】
2011086992.tif 000015
【図１４】
2011086992.tif 000016
【図１５】
2011086992.tif 000017
【図１６】
2011086992.tif 000018
【図１７】
2011086992.tif 000019
【国際調査報告】
2011086992.tif 000020
2011086992.tif 000021
2011086992.tif 000022
2011086992.tif 000023