(57)【要約】  高速かつ高精度にシグモイド関数を秘密計算する技術を提供する。g(x)を秘密計算が可能な関数とし、入力値xのシェア[[x]]から入力値xに対するシグモイド関数の値のシェア[[σ'(x)]]を計算する秘密シグモイド関数計算システムであって、第一比較結果[[c]]=less_than([[x]],t1)を生成する第一比較手段と、第二比較結果[[d]]=greater_than([[x]],t0)を生成する第二比較手段と、第一論理計算結果[[e]]=not([[c]])を生成する第一論理計算手段と、第二論理計算結果[[k]]=and([[c]],[[d]])または[[k]]=mul([[c]],[[d]])を生成する第二論理計算手段と、シェア[[σ'(x)]]=mul([[k]],[[g(x)]])+[[e]]を計算する関数値計算手段とを含む。
2020071187.tif 000002
【特許請求の範囲】
【請求項１】
t0, t1をt0<t1を満たす実数、g(x)を秘密計算が可能な関数とし、
3個以上の秘密シグモイド関数計算装置で構成され、入力値xのシェア[[x]]から、入力値xに対するシグモイド関数の値のシェア[[σ'(x)]]を計算する秘密シグモイド関数計算システムであって、
前記シェア[[x]]から、[[c]]=less_than([[x]], t1)により、第一比較結果[[c]]を生成する第一比較手段と、
前記シェア[[x]]から、[[d]]=greater_than([[x]], t0)により、第二比較結果[[d]]を生成する第二比較手段と、
前記第一比較結果[[c]]から、[[e]]=not([[c]])により、第一論理計算結果[[e]]を生成する第一論理計算手段と、
前記第一比較結果[[c]]と前記第二比較結果[[d]]から、[[k]]=and([[c]], [[d]])または[[k]]=mul([[c]], [[d]])により、第二論理計算結果[[k]]を生成する第二論理計算手段と、
前記シェア[[x]]と前記第一論理計算結果[[e]]と前記第二論理計算結果[[k]]から、[[σ'(x)]]=mul([[k]], [[g(x)]])+[[e]]により、前記シェア[[σ'(x)]]を計算する関数値計算手段と
を含む秘密シグモイド関数計算システム。
【請求項２】
請求項１に記載の秘密シグモイド関数計算システムであって、
前記関数g(x)は、g(x)=ax+b（ただし、a, bは実数）である
ことを特徴とする秘密シグモイド関数計算システム。
【請求項３】
mを1以上の整数、ηを0<η<1を満たす実数、Sigmoid([[x]])を請求項１または２に記載の秘密シグモイド関数計算システムを用いて入力値xのシェア[[x]]から入力値xに対するシグモイド関数の値のシェアを計算する関数とし、
3個以上の秘密ロジスティック回帰計算装置で構成され、説明変数のデータxi→のシェア[[xi→]](0≦i≦m-1)、目的変数のデータyiのシェア[[yi]](0≦i≦m-1)から、ロジスティック回帰モデルのモデルパラメータw→のシェア[[w→]]を計算する秘密ロジスティック回帰計算システムであって、
i=0, …, m-1に対して、
t回更新を行ったモデルパラメータw→の値wt→のシェア[[wt→]]と前記シェア[[xi→]]から、[[bi]]=hpsum([[wt→]], [[(1, xi→)]])により、[[bi]]を計算し、
前記[[bi]]から、[[ci]]=Sigmoid([[bi]])により、[[ci]]を計算し、
前記シェア[[yi]]と前記[[ci]]から、[[di]]=[[ci]]-[[yi]]により、誤差[[di]]を計算する誤差計算手段と、
j=0, …, nに対して、
前記誤差[[di]] (0≦i≦m-1)と前記シェア[[xi→]]の第j要素[[xi,j]] (0≦i≦m-1)から、[[e]]=Σi=0m-1[[di]][[xi,j]]により、[[e]]を計算し、
前記シェア[[wt→]]の第j要素[[wj,t]]と前記[[e]]から、[[wj,t+1]]=[[wj,t]]-η(1/m)[[e]]により、t+1回更新を行ったモデルパラメータw→の値wt+1→のシェア[[wt+1→]]の第j要素[[wj,t+1]]を計算するモデルパラメータ更新手段と
を含む秘密ロジスティック回帰計算システム。
【請求項４】
t0, t1をt0<t1を満たす実数、g(x)を秘密計算が可能な関数とし、
入力値xのシェア[[x]]から、入力値xに対するシグモイド関数の値のシェア[[σ'(x)]]を計算する、3個以上の秘密シグモイド関数計算装置で構成される秘密シグモイド関数計算システムの中の秘密シグモイド関数計算装置であって、
前記シェア[[x]]から、[[c]]=less_than([[x]], t1)により、第一比較結果[[c]]を生成するための第一比較部と、
前記シェア[[x]]から、[[d]]=greater_than([[x]], t0)により、第二比較結果[[d]]を生成するための第二比較部と、
前記第一比較結果[[c]]から、[[e]]=not([[c]])により、第一論理計算結果[[e]]を生成するための第一論理計算部と、
前記第一比較結果[[c]]と前記第二比較結果[[d]]から、[[k]]=and([[c]], [[d]])または[[k]]=mul([[c]], [[d]])により、第二論理計算結果[[k]]を生成するための第二論理計算部と、
前記シェア[[x]]と前記第一論理計算結果[[e]]と前記第二論理計算結果[[k]]から、[[σ'(x)]]=mul([[k]], [[g(x)]])+[[e]]により、前記シェア[[σ'(x)]]を計算するための関数値計算部と
を含む秘密シグモイド関数計算装置。
【請求項５】
mを1以上の整数、ηを0<η<1を満たす実数、Sigmoid([[x]])を、3個以上の、請求項４に記載の秘密シグモイド関数計算装置で構成される秘密シグモイド関数計算システムを用いて入力値xのシェア[[x]]から入力値xに対するシグモイド関数の値のシェアを計算する関数とし、
説明変数のデータxi→のシェア[[xi→]](0≦i≦m-1)、目的変数のデータyiのシェア[[yi]](0≦i≦m-1)から、ロジスティック回帰モデルのモデルパラメータw→のシェア[[w→]]を計算する、3個以上の秘密ロジスティック回帰計算装置で構成される秘密ロジスティック回帰計算システムの中の秘密ロジスティック回帰計算装置であって、
i=0, …, m-1に対して、
t回更新を行ったモデルパラメータw→の値wt→のシェア[[wt→]]と前記シェア[[xi→]]から、[[bi]]=hpsum([[wt→]], [[(1, xi→)]])により、[[bi]]を計算し、
前記[[bi]]から、[[ci]]=Sigmoid([[bi]])により、[[ci]]を計算し、
前記シェア[[yi]]と前記[[ci]]から、[[di]]=[[ci]]-[[yi]]により、誤差[[di]]を計算するための誤差計算部と、
j=0, …, nに対して、
前記誤差[[di]] (0≦i≦m-1)と前記シェア[[xi→]]の第j要素[[xi,j]] (0≦i≦m-1)から、[[e]]=Σi=0m-1[[di]][[xi,j]]により、[[e]]を計算し、
前記シェア[[wt→]]の第j要素[[wj,t]]と前記[[e]]から、[[wj,t+1]]=[[wj,t]]-η(1/m)[[e]]により、t+1回更新を行ったモデルパラメータw→の値wt+1→のシェア[[wt+1→]]の第j要素[[wj,t+1]]を計算するためのモデルパラメータ更新部と
を含む秘密ロジスティック回帰計算装置。
【請求項６】
t0, t1をt0<t1を満たす実数、g(x)を秘密計算が可能な関数とし、
3個以上の秘密シグモイド関数計算装置で構成される秘密シグモイド関数計算システムが、入力値xのシェア[[x]]から、入力値xに対するシグモイド関数の値のシェア[[σ'(x)]]を計算する秘密シグモイド関数計算方法であって、
前記秘密シグモイド関数計算システムが、前記シェア[[x]]から、[[c]]=less_than([[x]], t1)により、第一比較結果[[c]]を生成する第一比較ステップと、
前記秘密シグモイド関数計算システムが、前記シェア[[x]]から、[[d]]=greater_than([[x]], t0)により、第二比較結果[[d]]を生成する第二比較ステップと、
前記秘密シグモイド関数計算システムが、前記第一比較結果[[c]]から、[[e]]=not([[c]])により、第一論理計算結果[[e]]を生成する第一論理計算ステップと、
前記秘密シグモイド関数計算システムが、前記第一比較結果[[c]]と前記第二比較結果[[d]]から、[[k]]=and([[c]], [[d]])または[[k]]=mul([[c]], [[d]])により、第二論理計算結果[[k]]を生成する第二論理計算ステップと、
前記秘密シグモイド関数計算システムが、前記シェア[[x]]と前記第一論理計算結果[[e]]と前記第二論理計算結果[[k]]から、[[σ'(x)]]=mul([[k]], [[g(x)]])+[[e]]により、前記シェア[[σ'(x)]]を計算する関数値計算ステップと
を含む秘密シグモイド関数計算方法。
【請求項７】
mを1以上の整数、ηを0<η<1を満たす実数、Sigmoid([[x]])を請求項６に記載の秘密シグモイド関数計算方法を用いて入力値xのシェア[[x]]から入力値xに対するシグモイド関数の値のシェアを計算する関数とし、
3個以上の秘密ロジスティック回帰計算装置で構成される秘密ロジスティック回帰計算システムが、説明変数のデータxi→のシェア[[xi→]](0≦i≦m-1)、目的変数のデータyiのシェア[[yi]](0≦i≦m-1)から、ロジスティック回帰モデルのモデルパラメータw→のシェア[[w→]]を計算する秘密ロジスティック回帰計算方法であって、
前記秘密ロジスティック回帰計算システムが、i=0, …, m-1に対して、
t回更新を行ったモデルパラメータw→の値wt→のシェア[[wt→]]と前記シェア[[xi→]]から、[[bi]]=hpsum([[wt→]], [[(1, xi→)]])により、[[bi]]を計算し、
前記[[bi]]から、[[ci]]=Sigmoid([[bi]])により、[[ci]]を計算し、
前記シェア[[yi]]と前記[[ci]]から、[[di]]=[[ci]]-[[yi]]により、誤差[[di]]を計算する誤差計算ステップと、
前記秘密ロジスティック回帰計算システムが、j=0, …, nに対して、
前記誤差[[di]] (0≦i≦m-1)と前記シェア[[xi→]]の第j要素[[xi,j]] (0≦i≦m-1)から、[[e]]=Σi=0m-1[[di]][[xi,j]]により、[[e]]を計算し、
前記シェア[[wt→]]の第j要素[[wj,t]]と前記[[e]]から、[[wj,t+1]]=[[wj,t]]-η(1/m)[[e]]により、t+1回更新を行ったモデルパラメータw→の値wt+1→のシェア[[wt+1→]]の第j要素[[wj,t+1]]を計算するモデルパラメータ更新ステップと
を含む秘密ロジスティック回帰計算方法。
【請求項８】
請求項４に記載の秘密シグモイド関数計算装置または請求項５に記載の秘密ロジスティック回帰計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算技術に関し、特にシグモイド関数を秘密計算する技術に関する。
【背景技術】
【０００２】
シグモイド関数を秘密計算するための従来の方法として、非特許文献１に記載の方法がある。【０００３】
ここで、秘密計算とは、暗号化された数値を復元することなく指定された演算の演算結果を得る方法のことである（例えば参考非特許文献１参照）。参考非特許文献１の方法では、数値を復元することのできる複数の情報を3つの秘密計算装置に分散するという暗号化を行い、数値を復元することなく、加減算、定数和、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を3つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。一般に、分散数は3に限らずW（Wは3以上の所定の定数）とすることができ、W個の秘密計算装置による協調計算によって秘密計算を実現するプロトコルはマルチパーティプロトコルと呼ばれる。
（参考非特許文献１：千田浩司，濱田浩気，五十嵐大，高橋克巳，“軽量検証可能３パーティ秘匿関数計算の再考”，In CSS，2010．）
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Payman Mohassel and Yupeng Zhang, “SecureML: A System for Scalable Privacy-Preserving Machine Learning”, In IEEE Symposium on Security and Privacy(SP) 2017, pp.19-38, 2017.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、シグモイド関数は、次式で表される非線形関数であり（図１参照）、精度と処理速度の２つを両立させて秘密計算するのは容易ではない。【０００６】
【数１】
2020071187.tif 000003
【０００７】
例えば、非特許文献１に記載の方法では、1/2が整数環や論理回路上で高速に処理できることを利用した関数を用いるため、比較的高速に処理できるが、シグモイド関数の近似を主たる目的としない処理速度を優先する関数を用いているため、近似精度は低い。【０００８】
そこで本発明は、高速かつ高精度にシグモイド関数を秘密計算する技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一態様は、t0, t1をt0<t1を満たす実数、g(x)を秘密計算が可能な関数とし、3個以上の秘密シグモイド関数計算装置で構成され、入力値xのシェア[[x]]から、入力値xに対するシグモイド関数の値のシェア[[σ'(x)]]を計算する秘密シグモイド関数計算システムであって、前記シェア[[x]]から、[[c]]=less_than([[x]], t1)により、第一比較結果[[c]]を生成する第一比較手段と、前記シェア[[x]]から、[[d]]=greater_than([[x]], t0)により、第二比較結果[[d]]を生成する第二比較手段と、前記第一比較結果[[c]]から、[[e]]=not([[c]])により、第一論理計算結果[[e]]を生成する第一論理計算手段と、前記第一比較結果[[c]]と前記第二比較結果[[d]]から、[[k]]=and([[c]], [[d]])または[[k]]=mul([[c]], [[d]])により、第二論理計算結果[[k]]を生成する第二論理計算手段と、前記シェア[[x]]と前記第一論理計算結果[[e]]と前記第二論理計算結果[[k]]から、[[σ'(x)]]=mul([[k]], [[g(x)]])+[[e]]により、前記シェア[[σ'(x)]]を計算する関数値計算手段とを含む。
【発明の効果】
【００１０】
本発明によれば、高速かつ高精度にシグモイド関数を秘密計算することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】図１は、シグモイド関数σ(x)を表す図である。
【図２】図２は、秘密シグモイド関数計算アルゴリズムを示す図である。
【図３】図３は、秘密ロジスティック回帰計算アルゴリズムを示す図である。
【図４】図４は、近似シグモイド関数σ’(x)を表す図である。
【図５】図５は、秘密シグモイド関数計算システム１０の構成を示すブロック図である。
【図６】図６は、秘密シグモイド関数計算装置１００iの構成を示すブロック図である。
【図７】図７は、秘密シグモイド関数計算システム１０の動作を示すフローチャートである。
【図８】図８は、秘密ロジスティック回帰計算システム２０の構成を示すブロック図である。
【図９】図９は、秘密ロジスティック回帰計算装置２００iの構成を示すブロック図である。
【図１０】図１０は、秘密ロジスティック回帰計算システム２０の動作を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１３】
後述する秘密シグモイド関数計算アルゴリズム、秘密ロジスティック回帰計算アルゴリズムは、既存の秘密計算上の演算の組み合わせで構築される。これらのアルゴリズムが必要とする演算は、秘匿化、加算、乗算、大小比較、論理演算（否定、論理積）、エイチピーサム(hpsum)である。なお、エイチピーサムとは積和のことである。以下、各演算について説明していく。
【００１４】
＜演算＞
［秘匿化］
[[x]]をxを秘密分散で秘匿した値（以下、xのシェアという）とする。秘密分散方法には、任意の方法を用いることができる。例えば、GF(261-1)上のShamir秘密分散、Z2上の複製秘密分散を用いることができる。
【００１５】
ある１つのアルゴリズムの中で複数の秘密分散方法を組み合わせて用いてもよい。この場合、適宜相互に変換するものとする。
【００１６】
また、n次元ベクトルx→=(x0, …, xn-1)に対して、[[x→]]=([[x0]], …, [[xn-1]])とする。
【００１７】
なお、xを[[x]]の平文という。
【００１８】
xから[[x]]を求める方法（秘匿化）、[[x]]からxを求める方法（復元）として、具体的には、参考非特許文献１、参考非特許文献２に記載の方法がある。
（参考非特許文献２：Shamir, A., “How to share a secret”, Communications of the ACM, Vol.22, No.11, pp.612-613, 1979.）
【００１９】
［加算、乗算］
秘密計算による加算[[x]]+[[y]]は、[[x]], [[y]]を入力とし、[[x+y]]を出力する。秘密計算による乗算[[x]]×[[y]]（mul([[x]], [[y]])）は、[[x]], [[y]]を入力とし、[[x×y]]を出力する。
【００２０】
なお、[[x]]、[[y]]のいずれかが秘匿されていない値（以下、公開値という）であってもよい。例えば、β、γを公開値として、[[x]], βを入力として、[[x+β]]を出力するようにしたり、γ, [[y]]を入力とし、[[γ×y]]を出力することもできる。
【００２１】
加算、乗算の具体的方法として、参考非特許文献３、参考非特許文献４に記載の方法がある。
（参考非特許文献３：Ben-Or, M., Goldwasser, S. and Wigderson, A., “Completeness theorems for non-cryptographic fault-tolerant distributed computation”, Proceedings of the twentieth annual ACM symposium on Theory of computing, ACM, pp. 1-10, 1988.）
（参考非特許文献４：Gennaro, R., Rabin, M. O. and Rabin, T., “Simplied VSS and fast-track multiparty computations with applications to threshold cryptography”, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, ACM, pp.101-111, 1998.）
【００２２】
［大小比較］
秘密計算less_than([[x]], t)（tは公開値）は、[[x]]を入力とし、[[〔x<t〕]]を出力する。秘密計算greater_than([[x]], t)（tは公開値）は、[[x]]を入力とし、[[〔x>t〕]]を出力する。ここで、〔・〕は、述語を表す。例えば、〔x<t〕は、“xはtより小さい”という述語を表し、“xはtより小さい”が真である場合は、[[〔x<t〕]]=[[1]]、偽である場合は、[[〔x<t〕]]=[[0]]となる。
【００２３】
［論理演算］
秘密計算による否定¬[[x]]は、[[x]]を入力とし、[[¬x]]を出力する。秘密計算による論理積and([[x]], [[y]])は、[[x]], [[y]]を入力とし、[[and(x, y)]]を出力する。
【００２４】
［エイチピーサム(hpsum)］
秘密計算hpsum([[x→]], [[y→]])は、[[x→]], [[y→]]（ただし、x→=(x0, …, xn-1), y→=(y0, …, yn-1)）を入力とし、[[Σj=0n-1xjyj]]を出力する。つまり、２つのベクトルの第j要素の積の和を出力する。
【００２５】
＜技術的背景＞
（近似シグモイド関数）
シグモイド関数σ(x)は、図１に示すような単調増加関数である。また、シグモイド関数σ(x)は、limx→∞σ(x)=1、limx→-∞σ(x)=0となる性質を持っている。図１からもわかるように、xが5以上となる場合にはσ(x)はほぼ1、xが-5以下となる場合にはほぼ0となっている。さらに、σ(x)の値がほぼ0になっている部分とほぼ1になっている部分の間（特に、x=0の付近）では直線的に増えており、この部分にのみ注目すると単純な関数（例えば、１次関数）で近似しても相応の近似精度が得られる可能性があることがわかる。
【００２６】
そこで、シグモイド関数σ(x)のこのような特徴を考慮して、xの値に応じて３つの式を用いて近似することを考える。つまり、シグモイド関数σ(x)を近似する関数σ'(x)（以下、近似シグモイド関数σ'(x)という）を、次式により定義する。
【００２７】
【数２】
2020071187.tif 000004
【００２８】
式(2)からわかるように、xが閾値t1以上である場合は1、閾値t0以下である場合は0、閾値t0と閾値t1の間にある場合は所定の関数g(x)でσ(x)を近似する関数がσ'(x)である。
【００２９】
近似シグモイド関数σ'(x)は、条件分岐式“IF γ THEN α ELSE β”が数式“γα+(1-γ)β”により表現できることを用いると、次式のように１つの式で表すことができる。
【００３０】
【数３】
2020071187.tif 000005
【００３１】
ただし、c=〔x<t1〕, d=〔x>t0〕である。したがって、c, dは括弧内の式が真である場合に1、偽である場合に0となる。なお、and(c, d)=cdであるから、式(3)は次式のように表すこともできる。
【００３２】
【数４】
2020071187.tif 000006
【００３３】
例えば、近似シグモイド関数σ'(x)の定義に用いる関数g(x)を１次関数g(x)=ax+bとすることができる。
【００３４】
［アルゴリズム］
ここでは、近似シグモイド関数σ'(x)を用いてシグモイド関数を秘密計算するアルゴリズム（秘密シグモイド関数計算アルゴリズム）について説明する。秘密シグモイド関数計算アルゴリズムは、xのシェア[[x]]を入力とし、パラメータt0, t1と秘密計算可能な関数g(x)を用いて、[[σ'(x)]]を計算し、出力する。ここで、関数g(x)が秘密計算可能な関数であるとは、入力値xのシェア[[x]]から、関数値g(x)のシェア[[g(x)]]が計算できる関数のことをいう。g(x)=ax+bとする場合の具体的な手順を図２に示す。この場合、a, bは任意の値とすることができる。また、t0, t1も任意の値とすることができる。なお、a, b, t0, t1はいずれも秘匿しておく必要がない値（公開値）である。図２をみれば、ステップ１〜ステップ５では式(3)'に従い[[σ'(x)]]を計算していることがわかる。
【００３５】
１次関数g(x)=ax+bは乗算と加算それぞれ１回ずつで計算できるため、計算コストが非常に低い。それに対して、例えば、関数g(x)に３次関数を用いてシグモイド関数を近似する場合、一般に３次関数がax3+bx2+cx+dと表されることからわかるように、１次関数で近似した場合よりも計算コストが明らかに大きくなる。また、近似シグモイド関数σ'(x)の計算に必要な処理は、全体として、大小比較２回、否定１回、乗算３回、加算２回（あるいは、大小比較２回、否定１回、論理積１回、乗算２回、加算２回）というように、複雑なシグモイド関数の計算がシンプルな演算のみで構成できることもわかる。
【００３６】
なお、以下では、秘密シグモイド関数計算アルゴリズムをSigmoidと表すこととする。したがって、Sigmoid([[x]])=[[σ'(x)]]となる。
【００３７】
（ロジスティック回帰分析）
ロジスティック回帰分析のモデルf(x→)（ただし、x→=(x1, …, xn)）は、n+1次元ベクトルw→=(w0, …, wn)をモデルパラメータとして、次式により表される。
【００３８】
【数５】
2020071187.tif 000007
【００３９】
ただし、(1, x→)はn+1次元ベクトル(1, x1, …, xn)を表す。
【００４０】
モデルパラメータw→を学習する方法として、関数の最小値を探索する学習法である最急降下法がある。最急降下法では、以下の入力、パラメータを用いて学習を行う。
【００４１】
（入力）説明変数のデータxi→、目的変数のデータyi（ただし、0≦i≦m-1、mは1以上の整数であり、学習データの数を表す）
【００４２】
（パラメータ）学習率η(0<η<1)、学習回数T
【００４３】
なお、学習率η及び学習回数Tについては、適切な値が設定されるものとする。
【００４４】
wt→=(w0,t, …, wn,t)をt回(0≦t≦T-1)更新を行ったモデルパラメータとして、以下の式により学習する。
【００４５】
【数６】
2020071187.tif 000008
【００４６】
つまり、学習データxi→, yiを用いて、モデルパラメータw→の第j要素wjごとに更新していく。なお、モデルパラメータw→の初期値w0→については適切な値が設定されるものとする。
【００４７】
［アルゴリズム］
ここでは、ロジスティック回帰モデルのモデルパラメータを秘密計算するアルゴリズム（秘密ロジスティック回帰計算アルゴリズム）について説明する。秘密ロジスティック回帰計算アルゴリズムは、説明変数のデータxi→のシェア[[xi→]]、目的変数のデータyiのシェア[[yi]]を入力とし、公開値であるパラメータη, Tを用いて、モデルパラメータw→のシェア[[w→]]を計算し、出力する。具体的な手順を図３に示す。図３をみれば、ステップ４〜ステップ１９では式(5)に従い[[w→]]を計算していることがわかる。また、ステップ８において、秘密シグモイド関数計算アルゴリズムSigmoidを用いてシグモイド関数の値を求めていることもわかる。
【００４８】
秘密シグモイド関数計算アルゴリズムSigmoidを用いると、シグモイド関数の計算の精度がよくなるため、ロジスティック回帰の計算の精度もよくなる。また、秘密ロジスティック回帰計算アルゴリズムの各ステップをみればわかるように、計算過程において秘密が保持されているため、外部に情報を全く漏らさず、安全に計算することができる。
【００４９】
なお、処理コストの観点から（浮動小数点でなく）固定小数点を用いて秘密ロジスティック回帰計算アルゴリズムの計算を行う場合、乗算を行うごとに数値精度が増大し、データ型の上限を超えてしまうことがある。当該アルゴリズムでは乗算を含む処理を繰り返し行うため、桁あふれを起こさないように桁落しを行う（途中で意図的に数値精度を落とす）必要がある。
【００５０】
（適用例）
a=0.25, b=0.5, t0=-2, t1=2としたときの近似シグモイド関数σ'(x)を図４に示す。図４のハイブリッド近似が近似シグモイド関数σ'(x)を表す。シグモイド関数σ(x)のx=0における傾きが0.25であり、値が0.5であることから、a=0.25, b=0.5とした。図４にはシグモイド関数（図中のsigmoid）もあわせて示してあり、この図を見ると、シグモイド関数σ(x)は近似シグモイド関数σ'(x)により精度よく近似されていることがわかる。
【００５１】
また、ロジスティック回帰分析では最終的に2値分類する際の閾値として、x=0付近の値を用いることが多いため、x=0付近におけるシグモイド関数の近似精度が高くなるのが好ましい。近似シグモイド関数σ'(x)を用いると、x=0付近における近似精度が高くなるため、ロジスティック回帰分析における最終計算結果であるモデルパラメータの精度が高くなる。
【００５２】
＜第１実施形態＞
以下、図５〜図７を参照して秘密シグモイド関数計算システム１０について説明する。図５は、秘密シグモイド関数計算システム１０の構成を示すブロック図である。秘密シグモイド関数計算システム１０は、W個（Wは3以上の所定の整数）の秘密シグモイド関数計算装置１００1、…、１００Wを含む。秘密シグモイド関数計算装置１００1、…、１００Wは、ネットワーク８００に接続しており、相互に通信可能である。ネットワーク８００は、例えば、インターネットなどの通信網あるいは同報通信路などでよい。図６は、秘密シグモイド関数計算装置１００i(1≦i≦W)の構成を示すブロック図である。図７は、秘密シグモイド関数計算システム１０の動作を示すフローチャートである。
【００５３】
図６に示すように秘密シグモイド関数計算装置１００iは、第一比較部１１０iと、第二比較部１２０iと、第一論理計算部１３０iと、第二論理計算部１４０iと、関数値計算部１５０iと、記録部１９０iを含む。記録部１９０iを除く秘密シグモイド関数計算装置１００iの各構成部は、秘密シグモイド関数計算アルゴリズムで必要とされる演算、つまり、少なくとも秘匿化、加算、乗算、大小比較、否定、論理積、エイチピーサム(hpsum)のうち、各構成部の機能を実現するうえで必要になる演算を実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば参考非特許文献１〜４のそれぞれで開示されるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから詳細な説明については省略する。また、記録部１９０iは、秘密シグモイド関数計算装置１００iの処理に必要な情報を記録する構成部である。例えば、記録部１９０iは、パラメータt0, t1（ただし、t0, t1はt0<t1を満たす実数）を記録しておく。また、記録部１９０iは、近似シグモイド関数σ'(x)の定義に用いる関数g(x)を計算するために必要なパラメータも記録しておく。なお、関数g(x)は任意の秘密計算可能な関数とすることができる。例えば、g(x)=ax+b（ただし、a, bは実数）とすることができる。この場合、記録部１９０iは、パラメータa, bもあわせて記録しておくことになる。
【００５４】
W個の秘密シグモイド関数計算装置１００iによる協調計算によって、秘密シグモイド関数計算システム１０はマルチパーティプロトコルである秘密シグモイド関数計算アルゴリズムを実現する。よって、秘密シグモイド関数計算システム１０の第一比較手段１１０（図示していない）は第一比較部１１０1、…、１１０Wで構成され、第二比較手段１２０（図示していない）は第二比較部１２０1、…、１２０Wで構成され、第一論理計算手段１３０（図示していない）は第一論理計算部１３０1、…、１３０Wで構成され、第二論理計算手段１４０（図示していない）は第二論理計算部１４０1、…、１４０Wで構成され、関数値計算手段１５０（図示していない）は関数値計算部１５０1、…、１５０Wで構成される。
【００５５】
秘密シグモイド関数計算システム１０は、入力値xのシェア[[x]]から、入力値xに対するシグモイド関数の値のシェア[[σ'(x)]]を計算する（図２参照）。以下、図７に従い秘密シグモイド関数計算システム１０の動作について説明する。
【００５６】
第一比較手段１１０は、入力値xのシェア[[x]]から、[[c]]=less_than([[x]], t1)により、第一比較結果[[c]]を生成する（Ｓ１１０）。図２の秘密シグモイド関数計算アルゴリズムのステップ１に対応する。
【００５７】
第二比較手段１２０は、入力値xのシェア[[x]]から、[[d]]=greater_than([[x]], t0)により、第二比較結果[[d]]を生成する（Ｓ１２０）。図２の秘密シグモイド関数計算アルゴリズムのステップ２に対応する。
【００５８】
第一論理計算手段１３０は、Ｓ１１０で生成した第一比較結果[[c]]から、[[e]]=not([[c]])により、第一論理計算結果[[e]]を生成する（Ｓ１３０）。図２の秘密シグモイド関数計算アルゴリズムのステップ３に対応する。
【００５９】
第二論理計算手段１４０は、Ｓ１１０で生成した第一比較結果[[c]]とＳ１２０で生成した第二比較結果[[d]]から、[[k]]=and([[c]], [[d]])により、第二論理計算結果[[k]]を生成する（Ｓ１４０）。図２の秘密シグモイド関数計算アルゴリズムのステップ４に対応する。もちろん、[[k]]=and([[c]], [[d]])の代わりに、[[k]]=mul([[c]], [[d]])を用いてもよい。
【００６０】
関数値計算手段１５０は、入力値xのシェア[[x]]とＳ１３０で生成した第一論理計算結果[[e]]とＳ１４０で生成した第二論理計算結果[[k]]から、[[σ'(x)]]=mul([[k]], [[g(x)]])+[[e]]により、関数値のシェア[[σ'(x)]]を計算する（Ｓ１５０）。図２の秘密シグモイド関数計算アルゴリズムのステップ５に対応する。
【００６１】
本実施形態の発明によれば、高速かつ高精度にシグモイド関数を秘密計算することが可能となる。
【００６２】
本実施形態の発明では、秘密計算が容易ではない非線形関数であるシグモイド関数の計算を、秘匿化、加算、乗算など簡単な演算の組合せに還元する。これにより、高速かつ高精度なシグモイド関数の秘密計算が可能となる。また、計算途中の値が秘匿化されていることから、安全なシグモイド関数の秘密計算が可能となる。
【００６３】
＜第２実施形態＞
以下、図８〜図１０を参照して秘密ロジスティック回帰計算システム２０について説明する。図８は、秘密ロジスティック回帰計算システム２０の構成を示すブロック図である。秘密ロジスティック回帰計算システム２０は、W'個（W'は3以上の所定の整数）の秘密ロジスティック回帰計算装置２００1、…、２００W'を含む。秘密ロジスティック回帰計算装置２００1、…、２００W'は、ネットワーク８００に接続しており、相互に通信可能である。ネットワーク８００は、例えば、インターネットなどの通信網あるいは同報通信路などでよい。図９は、秘密ロジスティック回帰計算装置２００i(1≦i≦W')の構成を示すブロック図である。図１０は、秘密ロジスティック回帰計算システム２０の動作を示すフローチャートである。
【００６４】
図９に示すように秘密ロジスティック回帰計算装置２００iは、初期化部２１０iと、誤差計算部２２０iと、モデルパラメータ更新部２３０iと、収束条件判定部２４０iと、記録部２９０iを含む。記録部２９０iを除く秘密ロジスティック回帰計算装置２００iの各構成部は、秘密ロジスティック回帰計算アルゴリズムで必要とされる演算、つまり、少なくとも秘匿化、加算、乗算、大小比較、否定、論理積、エイチピーサム(hpsum)のうち、各構成部の機能を実現するうえで必要になる演算を実行できるように構成されている。本発明において個々の演算を実現するための具体的な機能構成は、例えば参考非特許文献１〜４のそれぞれで開示されるアルゴリズムを実行できるような構成で十分であり、これらは従来的構成であるから詳細な説明については省略する。また、記録部２９０iは、秘密ロジスティック回帰計算装置２００iの処理に必要な情報を記録する構成部である。例えば、記録部２９０iは、パラメータη, T（ただし、ηを0<η<1を満たす実数、Tは1以上の整数）を記録しておく。また、記録部２９０iは、秘密シグモイド関数計算アルゴリズムSigmoidの計算に必要なパラメータも記録しておく。例えば、記録部２９０iは、パラメータt0, t1を記録しておく。
【００６５】
W'個の秘密ロジスティック回帰計算装置２００iによる協調計算によって、秘密ロジスティック回帰計算システム２０はマルチパーティプロトコルである秘密ロジスティック回帰計算アルゴリズムを実現する。よって、秘密ロジスティック回帰計算システム２０の初期化手段２１０（図示していない）は初期化部２１０1、…、２１０W'で構成され、誤差計算手段２２０（図示していない）は誤差計算部２２０1、…、２２０W'で構成され、モデルパラメータ更新手段２３０（図示していない）はモデルパラメータ更新部２３０1、…、２３０W'で構成され、収束条件判定手段２４０（図示していない）は収束条件判定部２４０1、…、２４０W'で構成される。
【００６６】
秘密ロジスティック回帰計算システム２０は、説明変数のデータxi→のシェア[[xi→]](0≦i≦m-1、ただし、mは1以上の整数)、目的変数のデータyiのシェア[[yi]] (0≦i≦m-1)から、ロジスティック回帰モデルのモデルパラメータw→のシェア[[w→]]を計算する（図３参照）。以下、図１０に従い秘密ロジスティック回帰計算システム２０の動作について説明する。
【００６７】
初期化手段２１０は、モデルパラメータw→の初期値w0→のシェア[[w0→]]を設定する（Ｓ２１０）。具体的には、予め記録部２９０iに記録している、適切な初期値w0→のシェア[[w0→]]を設定するのでよい。図３の秘密ロジスティック回帰計算アルゴリズムのステップ１に対応する。
【００６８】
誤差計算手段２２０は、i=0, …, m-1に対して、t回更新を行ったモデルパラメータw→の値wt→のシェア[[wt→]]とシェア[[xi→]]から、[[bi]]=hpsum([[wt→]], [[(1, xi→)]])により、[[bi]]を計算し、[[bi]]から、[[ci]]=Sigmoid([[bi]])により、[[ci]]を計算し、シェア[[yi]]と[[ci]]から、[[di]]=[[ci]]-[[yi]]により、誤差[[di]]を計算する（Ｓ２２０）。図３の秘密ロジスティック回帰計算アルゴリズムのステップ５〜１１に対応する。なお、Sigmoidは、秘密シグモイド関数計算システム１０を用いて計算すればよい。
【００６９】
モデルパラメータ更新手段２３０は、j=0, …, nに対して、Ｓ２２０で計算した誤差[[di]] (0≦i≦m-1)とシェア[[xi→]]の第j要素[[xi,j]] (0≦i≦m-1)から、[[e]]=Σi=0m-1[[di]][[xi,j]]により、[[e]]を計算し、シェア[[wt→]]の第j要素[[wj,t]]と[[e]]から、[[wj,t+1]]=[[wj,t]]-η(1/m)[[e]]により、t+1回更新を行ったモデルパラメータw→の値wt+1→のシェア[[wt+1→]]の第j要素[[wj,t+1]]を計算する（Ｓ２３０）。ここで、xi,0=1 (i=0, …, m-1)とする。図３の秘密ロジスティック回帰計算アルゴリズムのステップ１２〜１７に対応する。
【００７０】
条件判定部２４０は、事前に設定されたモデルパラメータ更新の繰り返し条件、つまり、t<Tを判定し、条件が満たされる場合はＳ２２０〜Ｓ２３０の処理を繰り返し、繰り返し条件が満たされない場合（所定の学習回数Tに達した場合）、シェア[[wT-1→]]をモデルパラメータw→のシェア[[w→]]として出力し、処理を終了する（Ｓ２４０）。
【００７１】
本実施形態の発明によれば、高速かつ高精度にロジスティック回帰モデルのモデルパラメータを秘密計算することが可能となる。
【００７２】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００８１】
上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。
【図１】
2020071187.tif 000009
【図２】
2020071187.tif 000010
【図３】
2020071187.tif 000011
【図４】
2020071187.tif 000012
【図５】
2020071187.tif 000013
【図６】
2020071187.tif 000014
【図７】
2020071187.tif 000015
【図８】
2020071187.tif 000016
【図９】
2020071187.tif 000017
【図１０】
2020071187.tif 000018
【手続補正書】
【提出日】令和3年3月19日(2021.3.19)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
加算、乗算の具体的方法として、参考非特許文献３、参考非特許文献４に記載の方法がある。
（参考非特許文献３：Ben-Or, M., Goldwasser, S. and Wigderson, A., “Completeness theorems for non-cryptographic fault-tolerant distributed computation”, Proceedings of the twentieth annual ACM symposium on Theory of computing, ACM, pp. 1-10, 1988.）
（参考非特許文献４：Gennaro, R., Rabin, M. O. and Rabin, T., “Simplified VSS and fast-track multiparty computations with applications to threshold cryptography”, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, ACM, pp.101-111, 1998.）
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
収束条件判定手段２４０は、事前に設定されたモデルパラメータ更新の繰り返し条件、つまり、t<Tを判定し、条件が満たされる場合はＳ２２０〜Ｓ２３０の処理を繰り返し、繰り返し条件が満たされない場合（所定の学習回数Tに達した場合）、シェア[[wT-1→]]をモデルパラメータw→のシェア[[w→]]として出力し、処理を終了する（Ｓ２４０）。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正の内容】
【図９】
2020071187.tif 000019
【国際調査報告】
2020071187.tif 000020
2020071187.tif 000021
2020071187.tif 000022
2020071187.tif 000023