(57)【特許請求の範囲】
【請求項１】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、kをk≦x<k+1を満たす整数、rをk≦r<k+1を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記値xを代入した前記n次多項式a0+a1x1+…+anxnの値の秘匿文[[a0+a1x1+…+anxn]]を計算する秘密計算システムであって、
前記秘密計算装置は、
前記秘匿文[[r]]を用いて、前記秘匿文[[x]]から前記値xと前記乱数rの大小比較結果であるu（ただし、x≦rならばu=1、x≦rでないならばu=0）の秘匿文[[u]]を生成する比較部と、
前記秘匿文[[x]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[x]]-[[r]]+[[u]]として生成するマスク部と、
前記秘匿文[[c]]から、前記マスクcを復元する復元部と、
前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算部と、
【数６】
0006629466.tif 000007
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択部と、
前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記秘匿文[[a0+a1x1+…+anxn]]として計算する線形結合部と
を含むものである秘密計算システム。
【請求項２】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
前記値xの逆数1/xが1/x=a0+a1x1+…+anxnと表されるものとし、
2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記逆数1/xの秘匿文[[1/x]]を計算する秘密計算システムであって、
前記秘密計算装置は、
前記秘匿文[[x]]から、x=s×2e×f(s∈{-1,1}、eは整数、1≦f<2)を満たすs,e,fの秘匿文[[s]],[[e]],[[f]]を生成する入力値分解部と、
前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較部と、
前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスク部と、
前記秘匿文[[c]]から、前記マスクcを復元する復元部と、
前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算部と、
【数７】
0006629466.tif 000008
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択部と、
前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの逆数1/fの秘匿文[[1/f]]として計算する線形結合部と、
前記秘匿文[[s]]、前記秘匿文[[e]]、前記秘匿文[[1/f]]から、[[s]]×([[1/f]]<<[[-e]])（ただし、[[1/f]]<< [[-e]]は1/fを-eビット左シフトした値）を前記秘匿文[[1/x]]として計算する逆数計算部と
を含むものである秘密計算システム。
【請求項３】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
前記値xの対数logxがlogx=a0+a1x1+…+anxnと表されるものとし、
2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記対数logxの秘匿文[[logx]]を計算する秘密計算システムであって、
前記秘密計算装置は、
前記秘匿文[[x]]から、x=2e×f(eは整数、1≦f<2)を満たすe,fの秘匿文[[e]],[[f]]を生成する入力値分解部と、
前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較部と、
前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスク部と、
前記秘匿文[[c]]から、前記マスクcを復元する復元部と、
前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算部と、
【数８】
0006629466.tif 000009
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択部と、
前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの対数logfの秘匿文[[logf]]として計算する線形結合部と、
前記秘匿文[[e]]、前記秘匿文[[logf]]から、前記対数logfにeを加算した値[[logf]]+[[e]]を前記秘匿文[[logx]]として計算する対数計算部と
を含むものである秘密計算システム。
【請求項４】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、kをk≦x<k+1を満たす整数、rをk≦r<k+1を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記値xを代入した前記n次多項式a0+a1x1+…+anxnの値の秘匿文[[a0+a1x1+…+anxn]]を計算する秘密計算システムの中の秘密計算装置であって、
前記秘匿文[[r]]を用いて、前記秘匿文[[x]]から前記値xと前記乱数rの大小比較結果であるu（ただし、x≦rならばu=1、x≦rでないならばu=0）の秘匿文[[u]]を生成する比較部と、
前記秘匿文[[x]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[x]]-[[r]]+[[u]]として生成するマスク部と、
前記秘匿文[[c]]から、前記マスクcを復元する復元部と、
前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算部と、
【数９】
0006629466.tif 000010
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択部と、
前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記秘匿文[[a0+a1x1+…+anxn]]として計算する線形結合部と
を含む秘密計算装置。
【請求項５】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
前記値xの逆数1/xが1/x=a0+a1x1+…+anxnと表されるものとし、
2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記逆数1/xの秘匿文[[1/x]]を計算する秘密計算システムの中の秘密計算装置であって、
前記秘匿文[[x]]から、x=s×2e×f(s∈{-1,1}、eは整数、1≦f<2)を満たすs,e,fの秘匿文[[s]],[[e]],[[f]]を生成する入力値分解部と、
前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較部と、
前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスク部と、
前記秘匿文[[c]]から、前記マスクcを復元する復元部と、
前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算部と、
【数１０】
0006629466.tif 000011
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択部と、
前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの逆数1/fの秘匿文[[1/f]]として計算する線形結合部と、
前記秘匿文[[s]]、前記秘匿文[[e]]、前記秘匿文[[1/f]]から、[[s]]×([[1/f]]<<[[-e]])（ただし、[[1/f]]<< [[-e]]は1/fを-eビット左シフトした値）を前記秘匿文[[1/x]]として計算する逆数計算部と
を含む秘密計算装置。
【請求項６】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
前記値xの対数logxがlogx=a0+a1x1+…+anxnと表されるものとし、
2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記対数logxの秘匿文[[logx]]を計算する秘密計算システムの中の秘密計算装置であって、
前記秘匿文[[x]]から、x=2e×f(eは整数、1≦f<2)を満たすe,fの秘匿文[[e]],[[f]]を生成する入力値分解部と、
前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較部と、
前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスク部と、
前記秘匿文[[c]]から、前記マスクcを復元する復元部と、
前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算部と、
【数１１】
0006629466.tif 000012
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択部と、
前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの対数logfの秘匿文[[logf]]として計算する線形結合部と、
前記秘匿文[[e]]、前記秘匿文[[logf]]から、前記対数logfにeを加算した値[[logf]]+[[e]]を前記秘匿文[[logx]]として計算する対数計算部と
を含む秘密計算装置。
【請求項７】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、kをk≦x<k+1を満たす整数、rをk≦r<k+1を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
2個以上の秘密計算装置で構成される秘密計算システムが実行する、前記値xの秘匿文[[x]]から、前記値xを代入した前記n次多項式a0+a1x1+…+anxnの値の秘匿文[[a0+a1x1+…+anxn]]を計算する秘密計算方法であって、
前記秘密計算装置が、前記秘匿文[[r]]を用いて、前記秘匿文[[x]]から前記値xと前記乱数rの大小比較結果であるu（ただし、x≦rならばu=1、x≦rでないならばu=0）の秘匿文[[u]]を生成する比較ステップと、
前記秘密計算装置が、前記秘匿文[[x]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[x]]-[[r]]+[[u]]として生成するマスクステップと、
前記秘密計算装置が、前記秘匿文[[c]]から、前記マスクcを復元する復元ステップと、
前記秘密計算装置が、前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0, …, nに対して係数biを次式で計算する係数計算ステップと、
【数１２】
0006629466.tif 000013
前記秘密計算装置が、前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択ステップと、
前記秘密計算装置が、前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記秘匿文[[a0+a1x1+…+anxn]]として計算する線形結合ステップと
を実行する秘密計算方法。
【請求項８】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
前記値xの逆数1/xが1/x=a0+a1x1+…+anxnと表されるものとし、
2個以上の秘密計算装置で構成される秘密計算システムが実行する、前記値xの秘匿文[[x]]から、前記逆数1/xの秘匿文[[1/x]]を計算する秘密計算方法であって、
前記秘密計算装置が、前記秘匿文[[x]]から、x=s×2e×f(s∈{-1,1}、eは整数、1≦f<2)を満たすs,e,fの秘匿文[[s]],[[e]],[[f]]を生成する入力値分解ステップと、
前記秘密計算装置が、前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較ステップと、
前記秘密計算装置が、前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスクステップと、
前記秘密計算装置が、前記秘匿文[[c]]から、前記マスクcを復元する復元ステップと、
前記秘密計算装置が、前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算ステップと、
【数１３】
0006629466.tif 000014
前記秘密計算装置が、前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択ステップと、
前記秘密計算装置が、前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの逆数1/fの秘匿文[[1/f]]として計算する線形結合ステップと、
前記秘密計算装置が、前記秘匿文[[s]]、前記秘匿文[[e]]、前記秘匿文[[1/f]]から、[[s]]×([[1/f]]<<[[-e]])（ただし、[[1/f]]<<[[-e]]は1/fを-eビット左シフトした値）を前記秘匿文[[1/x]]として計算する逆数計算ステップと
を実行する秘密計算方法。
【請求項９】
a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、
前記値xの対数logxがlogx=a0+a1x1+…+anxnと表されるものとし、
2個以上の秘密計算装置で構成される秘密計算システムが実行する、前記値xの秘匿文[[x]]から、前記対数logxの秘匿文[[logx]]を計算する秘密計算方法であって、
前記秘密計算装置が、前記秘匿文[[x]]から、x=2e×f(eは整数、1≦f<2)を満たすe,fの秘匿文[[e]],[[f]]を生成する入力値分解ステップと、
前記秘密計算装置が、前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較ステップと、
前記秘密計算装置が、前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスクステップと、
前記秘密計算装置が、前記秘匿文[[c]]から、前記マスクcを復元する復元ステップと、
前記秘密計算装置が、前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算ステップと、
【数１４】
0006629466.tif 000015
前記秘密計算装置が、前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択ステップと、
前記秘密計算装置が、前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの対数logfの秘匿文[[logf]]として計算する線形結合ステップと、
前記秘密計算装置が、前記秘匿文[[e]]、前記秘匿文[[logf]]から、前記対数logfにeを加算した値[[logf]]+[[e]]を前記秘匿文[[logx]]として計算する対数計算ステップと
を実行する秘密計算方法。
【請求項１０】
請求項４ないし６のいずれか１項に記載の秘密計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算技術に関するものであり、特に、入力値を秘密にしたまま多項式を計算する秘密計算技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元することなく指定された演算の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば非特許文献１参照）。非特許文献１の方法では、数値を復元することのできる複数の情報（数値の断片）を3つの秘密計算装置に分散するという暗号化を行い、数値を復元することなく、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を3つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。一般に、分散数は3に限らずW（Wは2以上の所定の定数）とすることができ、W個の秘密計算装置による協調計算によって秘密計算を実現するプロトコルはマルチパーティプロトコルと呼ばれる。【０００３】
なお、分散数が2の場合の秘密計算方法については、例えば、非特許文献２に開示されている。【０００４】
秘密計算によって多項式の計算を実現した方法として、非特許文献３の方法がある。非特許文献３の方法では、変数xの多項式の計算を行う際に、x1,x2,…,x2^kそれぞれにx2^kを乗ずる処理(k=0,1,…)を並列に行うことを繰り返して、x1,x2,…,xnの計算を実現している（なお、^（キャレット）は上付き添字を表し、例えば、xy^zはyzがxに対する上付き添字であることを表している）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】千田浩司, 濱田浩気, 五十嵐大, 高橋克巳, “軽量検証可能３パーティ秘匿関数計算の再考”, 情報処理学会シンポジウム論文集, Vol.2010, No.9, pp.555-560，2010.
【非特許文献２】Ivan Damgard, Valerio Pastro, Nigel Smart, Sarah Zakarias,“Multiparty Computation from Somewhat Homomorphic Encryption”, CRYPTO 2012, LNCS7417, pp.643-662, 2012.
【非特許文献３】Liina Kamm, Jan Willemson, “Secure floating point arithmetic and private satellite collision analysis”, International Journal of Information Security, Vol.14, No.6, pp.531-548, 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献３の方法では、多項式a0+a1x1+…+anxnを計算する際、2n-1回（ceiling(log2n)+1段）の乗算とn回の加算を実行する必要があるため、計算時間が大きくなるという問題があった。【０００７】
そこで本発明は、より小さい計算時間で多項式を計算する秘密計算技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様は、a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、kをk≦x<k+1を満たす整数、rをk≦r<k+1を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記値xを代入した前記n次多項式a0+a1x1+…+anxnの値の秘匿文[[a0+a1x1+…+anxn]]を計算する秘密計算システムであって、前記秘匿文[[r]]を用いて、前記秘匿文[[x]]から前記値xと前記乱数rの大小比較結果であるu（ただし、x≦rならばu=1、x≦rでないならばu=0）の秘匿文[[u]]を生成する比較手段と、前記秘匿文[[x]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[x]]-[[r]]+[[u]]として生成するマスク手段と、前記秘匿文[[c]]から、前記マスクcを復元する復元手段と、前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算手段と、【０００９】
【数１】
0006629466.tif 000002
【００１０】
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択手段と、前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記秘匿文[[a0+a1x1+…+anxn]]として計算する線形結合手段とを含む。【００１１】
本発明の一態様は、a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、前記値xの逆数1/xが1/x=a0+a1x1+…+anxnと表されるものとし、2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記逆数1/xの秘匿文[[1/x]]を計算する秘密計算システムであって、前記秘匿文[[x]]から、x=s×2e×f(s∈{-1,1}、eは整数、1≦f<2)を満たすs,e,fの秘匿文[[s]],[[e]],[[f]]を生成する入力値分解手段と、前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較手段と、前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスク手段と、前記秘匿文[[c]]から、前記マスクcを復元する復元手段と、前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算手段と、【００１２】
【数２】
0006629466.tif 000003
【００１３】
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択手段と、前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの逆数1/fの秘匿文[[1/f]]として計算する線形結合手段と、前記秘匿文[[s]]、前記秘匿文[[e]]、前記秘匿文[[1/f]]から、[[s]]×([[1/f]]<<[[-e]])（ただし、[[1/f]]<<[[-e]]は1/fを-eビット左シフトした値）を前記秘匿文[[1/x]]として計算する逆数計算手段とを含む。【００１４】
本発明の一態様は、a0+a1x1+…+anxnを変数xのn次多項式（nは多項式の次数、a0,a1,…,anは多項式の各係数）、xを前記n次多項式に代入する値、rを1≦r<2を満たす乱数、[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を前記乱数rとr-1のべき乗の秘匿文とし、前記値xの対数logxがlogx=a0+a1x1+…+anxnと表されるものとし、2個以上の秘密計算装置で構成され、前記値xの秘匿文[[x]]から、前記対数logxの秘匿文[[logx]]を計算する秘密計算システムであって、前記秘匿文[[x]]から、x=2e×f(eは整数、1≦f<2)を満たすe,fの秘匿文[[e]],[[f]]を生成する入力値分解手段と、前記秘匿文[[r]]を用いて、前記秘匿文[[f]]から前記fと前記乱数rの大小比較結果であるu（ただし、f≦rならばu=1、f≦rでないならばu=0）の秘匿文[[u]]を生成する比較手段と、前記秘匿文[[f]]、前記秘匿文[[r]]、前記秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[f]]-[[r]]+[[u]]として生成するマスク手段と、前記秘匿文[[c]]から、前記マスクcを復元する復元手段と、前記次数n、前記係数a0,a1,…,an、前記マスクcから、i=0,…,nに対して係数biを次式で計算する係数計算手段と、【００１５】
【数３】
0006629466.tif 000004
【００１６】
前記秘匿文[[u]]から、i=1,…,nに対して前記大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する選択手段と、前記係数bi(i=0,…,n)と前記秘匿文[[si]](i=1,…,n)の線形結合b0+b1[[s1]]+…+bn[[sn]]を前記fの対数logfの秘匿文[[logf]]として計算する線形結合手段と、前記秘匿文[[e]]、前記秘匿文[[logf]]から、前記対数logfにeを加算した値[[logf]]+[[e]]を前記秘匿文[[logx]]として計算する対数計算手段とを含む。
【発明の効果】
【００１７】
本発明によれば、多項式の計算に必要な乗算を1段とすることにより、多項式の秘密計算に必要な計算時間を削減することが可能となる。
【図面の簡単な説明】
【００１８】
【図１】第一実施形態の秘密計算アルゴリズムの処理手順を示す図である。
【図２】秘密計算システム１０の構成を示すブロック図である。
【図３】秘密計算装置１００iの構成を示すブロック図である。
【図４】秘密計算システム１０の動作を示すフローチャートである。
【図５】第二実施形態の秘密計算アルゴリズムの処理手順を示す図である。
【図６】秘密計算装置２００iの構成を示すブロック図である。
【図７】秘密計算システム２０の動作を示すフローチャートである。
【図８】第三実施形態の秘密計算アルゴリズムの処理手順を示す図である。
【図９】秘密計算装置３００iの構成を示すブロック図である。
【図１０】秘密計算システム３０の動作を示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２０】
後述する秘密計算アルゴリズムは、既存の秘密計算上の演算の組み合わせで構築される。この秘密計算アルゴリズムが必要とする演算は、秘匿化と復元、加算、減算、乗算、比較、選択、左シフトである。まず、各演算の定義、記法等について説明する。
【００２１】
＜定義、記法等＞
［秘匿化と復元］
ある値aを暗号化や秘密分散などにより秘匿化した値のことをaの秘匿文と呼び、[[a]]と表すこととする。aの秘匿文[[a]]が秘密分散により生成されたものである場合は、[[a]]により各秘密計算装置が持つ秘密分散の断片の集合を参照するものとする。
【００２２】
また、aの秘匿文[[a]]を復元して、aを得る処理をa←Open([[a]])と表すこととする。
【００２３】
秘匿化と復元の方法として、具体的には、参考非特許文献１の手法がある。
（参考非特許文献１）Mehrdad Aliasgari, Marina Blanton, Yihua Zhang, Aaron Steele, “Secure Computation on Floating Point Numbers”, NDSS 2013, 2013.
【００２４】
参考非特許文献１には、浮動小数点での演算について開示されている。固定小数点や整数での演算については、参考非特許文献１に開示されている浮動小数点から固定小数点や整数への型変換を組み合わせることで実現することができる。
【００２５】
［加算、減算、乗算］
加算、減算、乗算の各演算は、2つの値a, bの秘匿文[[a]], [[b]]を入力とし、それぞれa+b, a-b, abの計算結果である和c1、差c2、積c3の秘匿文[[c1]]，[[c2]]，[[c3]]を計算する。[[c1]]，[[c2]]，[[c3]]を得る処理をそれぞれ、[[c1]]←Add([[a]],[[b]])，[[c2]]←Sub([[a]],[[b]])，[[c3]]←Mul([[a]],[[b]])と表すこととする。誤解を招く恐れのない場合は、Add([[a]],[[b]])， Sub([[a]],[[b]])， Mul([[a]],[[b]])をそれぞれ[[a]]+[[b]], [[a]]-[[b]], [[a]]×[[b]]と略記することもある。
【００２６】
加算、減算、乗算の方法として、具体的には、参考非特許文献１の手法がある。参考非特許文献１には、浮動小数点での演算について開示されている。固定小数点や整数での演算については、参考非特許文献１に開示されている浮動小数点から固定小数点や整数への型変換を組み合わせることで実現することができる。
【００２７】
［比較］
aの秘匿文[[a]]、bの秘匿文[[b]]に対して、a≦bならばc=1、a≦bでないならばc=0となるaとbの大小比較結果cの秘匿文[[c]]を計算する処理を[[c]]←([[a]]≦?[[b]])と表すこととする。
【００２８】
比較の方法として、具体的には、参考非特許文献１の手法がある。参考非特許文献１には、浮動小数点での演算について開示されている。固定小数点や整数での演算については、参考非特許文献１に開示されている浮動小数点から固定小数点や整数への型変換を組み合わせることで実現することができる。
【００２９】
［選択］
a∈{0,1}の秘匿文[[a]]と2つの値t,fの秘匿文[[t]],[[f]]に対して、a=1ならばb=t、a=0ならばb=fとなる選択値bの秘匿文[[b]]を計算する処理を[[b]]←IfElse([[a]],[[t]],[[f]])と表すことにする。この選択処理は、IfElse([[a]],[[t]],[[f]]):=[[a]]×[[t]]+[[a]]×[[f]]として、乗算と加算を用いて実現することができる。
【００３０】
［左シフト］
aの秘匿文[[a]]とbの秘匿文[[b]]からaをbビット左シフトした値（つまり、aを2b倍した値）である左シフト値c(=a×2b)の秘匿文[[c]]を計算する処理を[[c]]←[[a]]<<[[b]]と表すこととする。
【００３１】
浮動小数点での演算については、指数部にシフト量(x << yのyのこと)を加算すればよい。また、固定小数点や整数での演算については、参考非特許文献１の固定小数点数と浮動小数点数の相互変換と上述の浮動小数点数の左シフトを組み合わせればよい。
【００３２】
＜第一実施形態＞
第一実施形態の秘密計算アルゴリズムの入力と出力、処理手順と第一実施形態の秘密計算アルゴリズムを実現する秘密計算システムについて、以下説明していく。
【００３３】
［入力と出力］
図１に示す第一実施形態の秘密計算アルゴリズムの入力と出力について説明する。
【００３４】
多項式a0+a1x1+…+anxnの次数n、係数a0,a1,…,anと多項式に代入する値xの秘匿文[[x]]が入力となる。また、k≦r<k+1（ただし、kはk≦x<k+1を満たす整数とする）を満たす乱数rとr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]も入力する。
【００３５】
xを代入した多項式a0+a1x1+…+anxnの値の秘匿文[[a0+a1x1+…+anxn]]が出力となる。
【００３６】
［処理手順］
図１に示す第一実施形態の秘密計算アルゴリズムの処理手順について説明する。その際、図１の左端の数字を用いてステップ１、ステップ２等と表現することにする。
【００３７】
ステップ１では、入力された秘匿文[[x]]と[[r]]から、xと乱数rの大小比較結果であるuの秘匿文[[u]]←([[x]]≦?[[r]])を生成する。[[u]]は、x≦rならばu=1、x≦rでないならばu=0となるuの秘匿文である。
【００３８】
ステップ２では、秘匿文[[x]]、[[r]]とステップ１で生成した秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[x]]-[[r]]+[[u]]として生成する。マスクcは、0<c≦1を満たす。
【００３９】
ステップ３では、ステップ２で生成した秘匿文[[c]]から、マスクcを復元する。
【００４０】
ステップ４では、次数n、係数a0,a1,…,anとステップ３で復元したcから、i=0,…,nに対して係数biを次式で計算する。
【００４１】
【数４】
0006629466.tif 000005
【００４２】
ステップ５では、ステップ１で生成した秘匿文[[u]]から、i=1,…,nに対して大小比較結果uに応じて定まる選択値siの秘匿文[[si]]=IfElse([[u]],[[(r-1)i]],[[ri]])を生成する。[[si]]は、u=1ならばsi=(r-1)i、u=0ならばsi=riとなる秘匿文である。つまり、[[u]]=[[1]]ならば[[si]]=[[(r-1)i]]、[[u]]=[[0]]ならば[[si]]=[[ri]]となる。
【００４３】
ステップ６では、ステップ４で生成した係数bi(i=0,…,n)とステップ５で生成した秘匿文[[si]](i=1,…,n)から、線形結合b0+b1[[s1]]+…+bn[[sn]]を計算する。ここで、[[a0+a1x1+…+anxn]]= b0+b1[[s1]]+…+bn[[sn]]が成り立つ。
【００４４】
［秘密計算システム］
以下、図２〜図４を参照して第一実施形態の秘密計算システム１０について説明する。図２は、秘密計算システム１０の構成を示すブロック図である。秘密計算システム１０は、W個（Wは2以上の所定の整数）の秘密計算装置１００1、…、１００Wを含む。秘密計算装置１００1、…、１００Wは、ネットワーク８００に接続しており、相互に通信可能である。ネットワーク８００は、例えば、インターネットなどの通信網あるいは同報通信路などでよい。図３は、秘密計算装置１００i(1≦i≦W)の構成を示すブロック図である。図４は、秘密計算システム１０の動作を示すフローチャートである。
【００４５】
図３に示すように秘密計算装置１００iは、乱数生成部１１０iと、比較部１２０iと、マスク部１３０iと、復元部１４０iと、係数計算部１５０iと、選択部１６０iと、線形結合部１７０iと、記録部１９０iを含む。記録部１９０iを除く秘密計算装置１００iの各構成部は、秘密計算アルゴリズムで必要とされる演算、つまり、少なくとも秘匿化、復元、加算、減算、乗算、比較、選択のうち、各構成部の機能を実現するうえで必要になる演算を実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば先行技術文献として開示している非特許文献や＜定義、記法等＞で開示している参考非特許文献などにあるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから詳細な説明については省略する。また、記録部１９０iは、秘密計算装置１００iの処理に必要な情報を記録する構成部である。例えば、次数n、係数a0,a1,…,anを記録しておく。
【００４６】
W個の秘密計算装置１００iによる協調計算によって、秘密計算システム１０はマルチパーティプロトコルである秘密計算アルゴリズムを実現する。よって、秘密計算システム１０の乱数生成手段１１０（図示していない）は乱数生成部１１０1、…、１１０Wで構成され、比較手段１２０（図示していない）は比較部１２０1、…、１２０Wで構成され、マスク手段１３０（図示していない）はマスク部１３０1、…、１３０Wで構成され、復元手段１４０（図示していない）は復元部１４０1、…、１４０Wで構成され、係数計算手段１５０（図示していない）は係数計算部１５０1、…、１５０Wで構成され、選択手段１６０（図示していない）は選択部１６０1、…、１６０Wで構成され、線形結合手段１７０（図示していない）は線形結合部１７０1、…、１７０Wで構成される。
【００４７】
秘密計算システム１０は、事前に生成した乱数r（k≦r<k+1、ただし、kはk≦x<k+1を満たす整数）とr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…,[[(r-1)n]]を用いて、多項式に代入する値xの秘匿文[[x]]から、xを代入した多項式a0+a1x1+…+anxnの値の秘匿文[[a0+a1x1+…+anxn]]を計算する。以下、図４に従い秘密計算システム１０の動作について説明する。
【００４８】
乱数生成手段１１０は、k≦r<k+1を満たす乱数rを生成し、秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を生成する（Ｓ１１０）。図１の秘密計算アルゴリズムの入力値の事前セットアップに対応する。秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]は、記録部１９０1、…、１９０Wに記録しておく。
【００４９】
比較手段１２０は、秘匿文[[x]]が入力される前に生成しておいた秘匿文[[r]]を用いて、秘匿文[[x]]から値xと乱数rの大小比較結果であるuの秘匿文[[u]]←([[x]]≦?[[r]])を生成する（Ｓ１２０）。図１の秘密計算アルゴリズムのステップ１に対応する。
【００５０】
マスク手段１３０は、秘匿文[[x]]、[[r]]とＳ１２０で生成した秘匿文[[u]]から、マスクcの秘匿文[[c]]を[[c]]=[[x]]-[[r]]+[[u]]として生成する（Ｓ１３０）。図１の秘密計算アルゴリズムのステップ２に対応する。
【００５１】
復元手段１４０は、Ｓ１３０で生成した秘匿文[[c]]から、マスクcを復元する（Ｓ１４０）。図１の秘密計算アルゴリズムのステップ３に対応する。
【００５２】
係数計算手段１５０は、多項式の次数n、係数a0,a1,…,anとＳ１４０で復元したマスクcから、i=0,…,nに対して係数biを次式で計算する（Ｓ１５０）。図１の秘密計算アルゴリズムのステップ４に対応する。
【００５３】
【数５】
0006629466.tif 000006
【００５４】
選択手段１６０は、Ｓ１２０で生成した秘匿文[[u]]から、i=1,…,nに対して大小比較結果uに応じて定まる選択値si（ただし、u=1ならばsi=(r-1)i、u=0ならばsi=ri）の秘匿文[[si]]を生成する（Ｓ１６０）。図１の秘密計算アルゴリズムのステップ５に対応する。
【００５５】
線形結合手段１７０は、Ｓ１５０で生成した係数bi(i=0,…,n)とＳ１６０で生成した秘匿文[[si]](i=1,…,n)から、線形結合b0+b1[[s1]]+…+bn[[sn]]を計算する（Ｓ１７０）。図１の秘密計算アルゴリズムのステップ６に対応する。
【００５６】
本実施形態の発明によれば、多項式a0+a1x1+…+anxnの計算をn回の加算、n回(1段)の乗算、1回の比較、1回の復元で実現することができるため、計算コストが削減される。特に、固定小数点での計算のように加算演算が無視できる場合は、計算時間が効果的に削減される。具体的には、従来おおよそビット分解を2n-1回（ceiling(log2n)+1段) 要した処理がn+1回(2段)の処理で実現することができる。また、代入する値xの範囲がk≦x<k+1に制限されることを利用し、入力値[[x]]から出力値[[a0+a1x1+…+anxn]]を計算する処理をx-r+uと事前に生成した乱数rとr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を用いて計算する処理に還元している。通常、x-r+u を復元すると情報が漏れてしまうが、x-r+uが0より大きく1以下の一様ランダムな値となるように調整することにより、安全にa0+a1x1+…+anxnの計算を実行することを可能としている。
【００５７】
＜第二実施形態＞
xの逆数1/xが多項式を用いて1/x=a0+a1x1+…+anxnと表すことができる場合、第一実施形態の秘密計算アルゴリズムを用いて、xの秘匿文[[x]]から、逆数1/xの秘匿文[[1/x]]を効率的に計算することができる。
【００５８】
第二実施形態の秘密計算アルゴリズムの入力と出力、処理手順と第二実施形態の秘密計算アルゴリズムを実現する秘密計算システムについて、以下説明していく。
【００５９】
［入力と出力］
図５に示す第二実施形態の秘密計算アルゴリズムの入力と出力について説明する。
【００６０】
多項式a0+a1x1+…+anxnの次数n、係数a0,a1,…,anと逆数の値を計算する値xの秘匿文[[x]]が入力となる。また、1≦r<2を満たす乱数rとr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]も入力する。
【００６１】
xの逆数1/xの秘匿文[[1/x]]が出力となる。
【００６２】
［処理手順］
図５に示す第二実施形態の秘密計算アルゴリズムの処理手順について説明する。その際、図５の左端の数字を用いてステップ１、ステップ２等と表現することにする。
【００６３】
ステップ１では、入力された秘匿文[[x]]に対して、x=s×2e×f(s∈{-1,1}、eは整数、1≦f<2)を満たすs,e,fの秘匿文[[s]],[[e]],[[f]]を生成する。参考非特許文献１の[[x]]の浮動小数点表現を求める演算を用いて、秘匿文[[s]],[[e]],[[f]]を生成することができる。
【００６４】
ステップ２では、多項式の次数n、係数a0,a1,…,an、秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]とステップ１で生成した秘匿文[[f]]から、 [[a0+a1f1+…+anfn]]を計算する。ここで、[[a0+a1f1+…+anfn]]=[[1/f]]が成り立つ。
【００６５】
ステップ３では、ステップ１で生成した秘匿文[[s]],[[e]]とステップ２で計算した秘匿文[[1/f]]から、[[s]]×([[1/f]]<<[[-e]])を計算する。ここで、[[s]]×([[1/f]]<<[[-e]])=[[1/x]]が成り立つ。
【００６６】
［秘密計算システム］
以下、図６〜図７を参照して第二実施形態の秘密計算システム２０について説明する。秘密計算システム２０は、W個（Wは2以上の所定の整数）の秘密計算装置１００1、…、１００Wを含む代わりに、W個の秘密計算装置２００1、…、２００Wを含む点において秘密計算システム１０と異なる。図６は、秘密計算装置２００i(1≦i≦W)の構成を示すブロック図である。図７は、秘密計算システム２０の動作を示すフローチャートである。
【００６７】
図６に示すように秘密計算装置２００iは、入力値分解部２１０iと、逆数計算部２２０iを更に含む点において秘密計算装置１００iと異なる。入力値分解部２１０iと逆数計算部２２０iも、秘密計算アルゴリズムで必要とされる演算のうち、その機能を実現するうえで必要になる演算を実行できるように構成されている。
【００６８】
秘密計算システム２０の入力値分解手段２１０は入力値分解部２１０1、…、２１０Wで構成され、逆数計算手段２２０は逆数計算部２２０1、…、２２０Wで構成される。
【００６９】
秘密計算システム２０は、事前に生成した乱数r（1≦r<2）とr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を用いて、多項式に代入する値xの秘匿文[[x]]から、xの逆数1/xの秘匿文[[1/x]]を計算する。以下、図７に従い秘密計算システム２０の動作について説明する。
【００７０】
乱数生成手段１１０は、1≦r<2を満たす乱数rを生成し、秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を生成する（Ｓ１１０）。図５の秘密計算アルゴリズムの入力値の事前セットアップに対応する。秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]は、記録部１９０1、…、１９０Wに記録しておく。
【００７１】
入力値分解手段２１０は、秘匿文[[x]]から、x=s×2e×f(s∈{-1,1}、eは整数、1≦f<2)を満たすs,e,fの秘匿文[[s]],[[e]],[[f]]を生成する（Ｓ２１０）。図５の秘密計算アルゴリズムのステップ１に対応する。
【００７２】
比較手段１２０、マスク手段１３０、復元手段１４０、係数計算手段１５０、選択手段１６０、線形結合手段１７０は、多項式の次数n、係数a0,a1,…,anと、[[x]]が入力される前に生成しておいた秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]と、Ｓ２１０で生成した秘匿文[[f]]とから、[[a0+a1f1+…+anfn]](=[[1/f]])を計算する（Ｓ１２０〜Ｓ１７０）。図５の秘密計算アルゴリズムのステップ２（図１の秘密計算アルゴリズムのステップ１〜ステップ６）に対応する。
【００７３】
逆数計算手段２２０は、Ｓ２１０で生成した秘匿文[[s]],[[e]]と、Ｓ１２０〜Ｓ１７０で計算した秘匿文[[1/f]]から、[[s]]×([[1/f]]<<[[-e]])を逆数1/xの秘匿文[[1/x]]として計算する（Ｓ２２０）。図５の秘密計算アルゴリズムのステップ３に対応する。
【００７４】
本実施形態の発明によれば、第一実施形態の秘密計算アルゴリズムを用いて多項式a0+a1x1+…+anxnの計算をすることにより、秘匿文[[x]]から逆数1/xの秘匿文[[1/x]]を計算するコストを削減することができる。また、xを分解して得られるfの範囲が1に制限されることを利用し、入力値[[f]]から出力値[[a0+a1f1+…+anfn]]を計算する処理をf-r+uと事前に生成した乱数rとr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を用いて計算する処理に還元している。通常、f-r+u を復元すると情報が漏れてしまうが、f-r+uが0より大きく1以下の一様ランダムな値となるように調整することにより、安全にa0+a1f1+…+anfnの計算を実行することを可能としている。
【００７５】
＜第三実施形態＞
xの対数logxが多項式を用いてlogx=a0+a1x1+…+anxnと表すことができる場合、第一実施形態の秘密計算アルゴリズムを用いて、xの秘匿文[[x]]から、対数logxの秘匿文[[logx]]を効率的に計算することができる。
【００７６】
第三実施形態の秘密計算アルゴリズムの入力と出力、処理手順と第三実施形態の秘密計算アルゴリズムを実現する秘密計算システムについて、以下説明していく。
【００７７】
［入力と出力］
図８に示す第三実施形態の秘密計算アルゴリズムの入力と出力について説明する。
【００７８】
多項式a0+a1x1+…+anxnの次数n、係数a0,a1,…,anと対数の値を計算する値xの秘匿文[[x]]が入力となる。また、1≦r<2を満たす乱数rとr-1のべき乗の秘匿文[[r]], [[r2]],…,[[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]も入力する。
【００７９】
xの対数logxの秘匿文[[logx]]が出力となる。
【００８０】
［処理手順］
図８に示す第三実施形態の秘密計算アルゴリズムの処理手順について説明する。その際、図８の左端の数字を用いてステップ１、ステップ２等と表現することにする。
【００８１】
ステップ１では、入力された秘匿文[[x]]に対して、x=2e×f(eは整数、1≦f<2)を満たすe,fの秘匿文[[e]],[[f]]を生成する。参考非特許文献１の[[x]]の浮動小数点表現を求める演算を用いて、秘匿文[[e]],[[f]]を生成することができる。
【００８２】
ステップ２では、多項式の次数n、係数a0,a1,…,an、秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]とステップ１で生成した秘匿文[[f]]から、[[a0+a1f1+…+anfn]]を計算する。ここで、[[a0+a1f1+…+anfn]]=[[logf]]が成り立つ。
【００８３】
ステップ３では、ステップ１で生成した秘匿文[[e]]とステップ２で計算した秘匿文[[logf]]から、[[logf]]+[[e]]を計算する。ここで、[[logf]]+[[e]]=[[logx]]が成り立つ。
【００８４】
［秘密計算システム］
以下、図９〜図１０を参照して第三実施形態の秘密計算システム３０について説明する。秘密計算システム３０は、W個（Wは2以上の所定の整数）の秘密計算装置１００1、…、１００Wを含む代わりに、W個の秘密計算装置３００1、…、３００Wを含む点において秘密計算システム１０と異なる。図９は、秘密計算装置３００i(1≦i≦W)の構成を示すブロック図である。図１０は、秘密計算システム３０の動作を示すフローチャートである。
【００８５】
図９に示すように秘密計算装置３００iは、入力値分解部３１０iと、対数計算部３２０iを更に含む点において秘密計算装置１００iと異なる。入力値分解部３１０iと対数計算部３２０iも、秘密計算アルゴリズムで必要とされる演算のうち、その機能を実現するうえで必要になる演算を実行できるように構成されている。
【００８６】
秘密計算システム３０の入力値分解手段３１０は入力値分解部３１０1、…、３１０Wで構成され、対数計算手段３２０は対数計算部３２０1、…、３２０Wで構成される。
【００８７】
秘密計算システム３０は、事前に生成した乱数r（1≦r<2）とr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を用いて、多項式に代入する値xの秘匿文[[x]]から、xの対数logxの秘匿文[[logx]]を計算する。以下、図１０に従い秘密計算システム３０の動作について説明する。
【００８８】
乱数生成手段１１０は、1≦r<2を満たす乱数rを生成し、秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を生成する（Ｓ１１０）。図８の秘密計算アルゴリズムの入力値の事前セットアップに対応する。秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]は、記録部１９０1、…、１９０Wに記録しておく。
【００８９】
入力値分解手段３１０は、秘匿文[[x]]から、x=2e×f(eは整数、1≦f<2)を満たすe,fの秘匿文[[e]],[[f]]を生成する（Ｓ３１０）。図８の秘密計算アルゴリズムのステップ１に対応する。
【００９０】
比較手段１２０、マスク手段１３０、復元手段１４０、係数計算手段１５０、選択手段１６０、線形結合手段１７０は、多項式の次数n、係数a0,a1,…,anと、[[x]]が入力される前に生成しておいた秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]と、Ｓ３１０で生成した秘匿文[[f]]とから、[[a0+a1f1+…+anfn]](=[[logf]])を計算する（Ｓ１２０〜Ｓ１７０）。図８の秘密計算アルゴリズムのステップ２（図１の秘密計算アルゴリズムのステップ１〜ステップ６）に対応する。
【００９１】
対数計算手段３２０は、Ｓ３１０で生成した秘匿文[[e]]と、Ｓ１２０〜Ｓ１７０で計算した秘匿文[[logf]]から、[[logf]]+[[e]]を対数logxの秘匿文[[logx]]として計算する（Ｓ３２０）。図８の秘密計算アルゴリズムのステップ３に対応する。
【００９２】
本実施形態の発明によれば、第一実施形態の秘密計算アルゴリズムを用いて多項式a0+a1x1+…+anxnの計算をすることにより、秘匿文[[x]]から対数logxの秘匿文[[logx]]を計算するコストを削減することができる。また、xを分解して得られるfの範囲が1に制限されることを利用し、入力値[[f]]から出力値[[a0+a1f1+…+anfn]]を計算する処理をf-r+uと事前に生成した乱数rとr-1のべき乗の秘匿文[[r]], [[r2]],…, [[rn]], [[r-1]], [[(r-1)2]],…, [[(r-1)n]]を用いて計算する処理に還元している。通常、f-r+u を復元すると情報が漏れてしまうが、f-r+uが0より大きく1以下の一様ランダムな値となるように調整することにより、安全にa0+a1f1+…+anfnの計算を実行することを可能としている。
【００９３】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００９４】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【００９５】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【００９６】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００９７】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００９８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１０２】
上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。
【図１】
0006629466.tif 000016
【図２】
0006629466.tif 000017
【図３】
0006629466.tif 000018
【図４】
0006629466.tif 000019
【図５】
0006629466.tif 000020
【図６】
0006629466.tif 000021
【図７】
0006629466.tif 000022
【図８】
0006629466.tif 000023
【図９】
0006629466.tif 000024
【図１０】
0006629466.tif 000025