(57)【要約】【課題】安全に楕円加算を計算する。【解決手段】マルチパーティ計算システム１は、少なくとも三台の秘匿計算装置２を含む。pを3より大きい素数とし、Fpを位数pの有限体とし、c,dを有限体Fp上の定数とし、cd(1-c4d)≠0であり、E:x2+y2=c2(1+dx2y2)を有限体Fp上で定義された楕円曲線とし、[・]pを有限体Fp上の秘密分散による値・の分散値とする。秘匿計算装置２は、楕円曲線E上の点P=(xP,yP)の分散値[P]p=([xP]p,[yP]p)及び楕円曲線E上の点Q=(xQ,yQ)の分散値[Q]p=([xQ]p,[yQ]p)を入力とし、次式により点Pと点Qを楕円加算した点R=(xR,yR)の分散値[R]p=([xR]p,[yR]p)を計算する楕円加算部１２を含む。2015132754.tif 000023【選択図】図１
2015132754.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも三台の秘匿計算装置を含むマルチパーティ計算システムであって、
pを3より大きい素数とし、Fpを位数pの有限体とし、c,dを有限体Fp上の定数とし、cd(1-c4d)≠0であり、E:x2+y2=c2(1+dx2y2)を有限体Fp上で定義された楕円曲線とし、[・]pを有限体Fp上の秘密分散による値・の分散値とし、
上記秘匿計算装置は、
楕円曲線E上の点P=(xP,yP)の分散値[P]p=([xP]p,[yP]p)及び楕円曲線E上の点Q=(xQ,yQ)の分散値[Q]p=([xQ]p,[yQ]p)を入力とし、次式により点Pと点Qを楕円加算した点R=(xR,yR)の分散値[R]p=([xR]p,[yR]p)を計算する楕円加算部
【数１０】
2015132754.tif 000020
を含むマルチパーティ計算システム。
【請求項２】
請求項１に記載のマルチパーティ計算システムであって、
Invを逆数を求める関数とし、x・yを値xと値yの乗算とし、
上記楕円加算部は、
分散値[u=xP・yQ]p、[v=yP・xQ]p、[s=xP・xQ]p及び[t=yP・yQ]pを計算する第一乗算部と、
分散値[w=u・v]pを計算する第二乗算部と、
分散値[g]p←Inv([c(1+dw)]p)及び分散値[h]p←Inv([c(1-dw)]p)を計算する逆数計算部と、
分散値[xR=(u+v)・g]p及び分散値[yR=(s-t)・h]pを計算する座標計算部と、
を含むマルチパーティ計算システム。
【請求項３】
請求項１または２に記載のマルチパーティ計算システムであって、
Zpを素数pを法とする剰余環とし、
上記秘匿計算装置は、
楕円曲線E上の点P=(xP,yP)の分散値[P]p=([xP]p,[yP]p)及び指数e∈Zpの分散値[e]pを入力とし、点Pの楕円スカラー倍算eP=R=(xR,yR)の分散値[R]p=([xR]p,[yR]p)を計算する楕円スカラー倍算部をさらに含み、
上記楕円スカラー倍算部は、
Lビットの乱数sの分散値[s]pと、乱数sのビット表現s1,…,sLをビット毎に秘密分散した分散値[s]B=([s1]p,…,[sL]p)とを生成する乱数生成部と、
分散値[e]pと分散値[s]pを加算して分散値[t=e+s mod p]pを求め、分散値[t]pを復元して値tを得る乱数加算部と、
値tのビット表現t1,…,tLをビット毎に秘密分散した分散値[t]B=([t1]p,…,[tL]p)を生成する乱数分散部と、
分散値[s]Bと分散値[t]Bの各ビットを比較し、値tが乱数sより小さければフラグ[f=1]pを設定し、値tが乱数s以上であればフラグ[f=0]pを設定するフラグ設定部と、
分散値[P]p及び値tを用いて点Pのt倍算tP=Tの分散値[T]pを計算し、分散値[P]pを用いて点Pのp倍算pP=Uの分散値[U]pを計算する第一倍算部と、
分散値[T]pと分散値[U]pの楕円加算T+U=Vの分散値[V]pを求める加算部と、
フラグ[f]pを検査し、[f=1]pであれば分散値[W]p=[V]pに設定し、[f=0]pであれば分散値[W]p=[T]pに設定するフラグ検査部と、
分散値[P]p及び分散値[s]Bを用いて点Pのs倍算sP=Sの分散値[S]pを計算する第二倍算部と、
分散値[S]pを用いて点Sの逆元-Sの分散値[-S]pを求め、分散値[W]pと分散値[-S]pを楕円加算して点Rの分散値[R]pを求める減算部と、
を含むマルチパーティ計算システム。
【請求項４】
pを3より大きい素数とし、Fpを位数pの有限体とし、c,dを有限体Fp上の定数とし、cd(1-c4d)≠0であり、E:x2+y2=c2(1+dx2y2)を有限体Fp上で定義された楕円曲線とし、[・]pを有限体Fp上の秘密分散による値・の分散値とし、
楕円曲線E上の点P=(xP,yP)の分散値[P]p=([xP]p,[yP]p)及び楕円曲線E上の点Q=(xQ,yQ)の分散値[Q]p=([xQ]p,[yQ]p)を入力とし、次式により点Pと点Qを楕円加算した点R=(xR,yR)の分散値[R]p=([xR]p,[yR]p)を出力する楕円加算部
【数１１】
2015132754.tif 000021
を含む秘匿計算装置。
【請求項５】
pを3より大きい素数とし、Fpを位数pの有限体とし、c,dを有限体Fp上の定数とし、cd(1-c4d)≠0であり、E:x2+y2=c2(1+dx2y2)を有限体Fp上で定義された楕円曲線とし、[・]pを有限体Fp上の秘密分散による値・の分散値とし、
楕円加算部が、楕円曲線E上の点P=(xP,yP)の分散値[P]p=([xP]p,[yP]p)及び楕円曲線E上の点Q=(xQ,yQ)の分散値[Q]p=([xQ]p,[yQ]p)を入力とし、次式により点Pと点Qを楕円加算した点R=(xR,yR)の分散値[R]p=([xR]p,[yR]p)を出力する楕円加算ステップ
【数１２】
2015132754.tif 000022
を含むマルチパーティ計算方法。
【請求項６】
請求項４に記載の秘匿計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術の応用技術に関し、特に、複数の参加者間で秘密情報を秘匿して計算を行うマルチパーティ計算技術に関する。
【背景技術】
【０００２】
マルチパーティ計算技術は、複数の計算主体が持つ秘密情報を秘匿したまま、他の計算主体と協力して秘密情報から得られる関数値を計算する技術である。マルチパーティ計算技術では、要素技術として秘密分散技術を利用する。秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。
【０００３】
定数ラウンドのマルチパーティ計算方式の従来技術には、非特許文献１に記載の技術がある。定数ラウンドとは、入力のビット長に関わらず一定回数以下のラウンド数で計算が完了することを意味している。非特許文献１に記載のマルチパーティ計算方式では、線形秘密分散による分散値を用いて有限体演算やビット演算などを定数ラウンドで行うことができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ivan Damgard, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, Tomas Toft, “Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation”, TCC 2006, pp. 285-304
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載された従来のマルチパーティ計算方式では、有限体演算やビット演算などは行うことができるが、楕円曲線上での楕円加算や楕円スカラー倍算を行うことはできなかった。
【０００６】
単独の計算主体が楕円加算や楕円スカラー倍算を行うためには、通常、楕円曲線のアフィン座標を用いたワイエルストラス標準型の楕円加算公式が用いられる。この楕円加算公式では、無限遠点の加算を行う際に、通常の点の加算とは異なる処理を行う必要がある。そのため、この楕円加算公式をマルチパーティ計算に単純に適用すると、計算対象となる点の情報が漏洩してしまうという問題があった。
【０００７】
この発明の目的は、マルチパーティ計算技術において、楕円曲線上の楕円加算や楕円スカラー倍算を安全に計算することである。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、この発明のマルチパーティ計算システムは、少なくとも三台の秘匿計算装置を含む。pを3より大きい素数とし、Fpを位数pの有限体とし、c,dを有限体Fp上の定数とし、cd(1-c4d)≠0であり、E:x2+y2=c2(1+dx2y2)を有限体Fp上で定義された楕円曲線とし、[・]pを有限体Fp上の秘密分散による値・の分散値とする。秘匿計算装置は、楕円曲線E上の点P=(xP,yP)の分散値[P]p=([xP]p,[yP]p)及び楕円曲線E上の点Q=(xQ,yQ)の分散値[Q]p=([xQ]p,[yQ]p)を入力とし、次式により点Pと点Qを楕円加算した点R=(xR,yR)の分散値[R]p=([xR]p,[yR]p)を計算する楕円加算部を含む。
【０００９】
【数１】
2015132754.tif 000003
【発明の効果】
【００１０】
この発明のマルチパーティ計算技術によれば、楕円曲線上の楕円加算や楕円スカラー倍算を安全に計算することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、マルチパーティ計算システムの機能構成を例示する図である。
【図２】図２は、秘匿計算装置の機能構成を例示する図である。
【図３】図３は、楕円加算部の機能構成を例示する図である。
【図４】図４は、楕円スカラー倍算部の機能構成を例示する図である。
【図５】図５は、楕円加算方法の処理フローを例示する図である。
【図６】図６は、楕円スカラー倍算方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１２】
実施形態の説明に先立ち、この明細書で用いる表記方法及び用語を定義する。
［表記方法］
pは3より大きい素数である。
【００１３】
Fpは位数pの有限体である。
【００１４】
Zpは素数pを法とする剰余環である。
【００１５】
[・]pは、・が値である場合は、値・を有限体Fp上で秘密分散した分散値である。・が数式である場合は、式・をマルチパーティ計算により解くことを表す。
【００１６】
x・yは値xと値yの乗算を表す。
【００１７】
［ワイエルストラス標準型の楕円加算公式］
有限体Fp上のワイエルストラス標準型の楕円曲線は、E:y2=x3+ax+bで表すことができる。ここで、a,bは有限体Fpの元である定数であり、4a3+27b2≠0を満たす。
【００１８】
楕円曲線E:y2=x3+ax+b上の点P=(xP,yP)と点Q=(xQ,yQ)の楕円加算P+Q=R=(xR,yR)は、以下のように求めることができる。なお、Οは無限遠点を表す。
【００１９】
P=Οのとき、R=Qとする。
【００２０】
Q=Οのとき、R=Pとする。
【００２１】
yP=-yQのとき、R=Οとする。
【００２２】
yP≠-yQのとき、R=(xR,yR)は、下記の式（１）で計算することができる。
【００２３】
【数２】
2015132754.tif 000004
【００２４】
ここで、λは点P,Qを通る直線の傾きであり、下記の式（２）で計算することができる。
【００２５】
【数３】
2015132754.tif 000005
【００２６】
ワイエルストラス標準型の楕円加算公式は、様々な形の楕円曲線を選択することができるため、汎用性が高い。しかし、計算対象である二点の関係により特別な処理が必要であるため、その情報が漏洩する問題がある。マルチパーティ計算では、情報を秘匿したまま計算できる必要があるため、ワイエルストラス標準型の楕円加算公式を単純に適用することができない。
【００２７】
［エドワーズ標準型の楕円加算公式］
有限体Fp上のエドワーズ標準型の楕円曲線は、E:x2+y2=c2(1+dx2y2)で表すことができる。ここで、c,dは有限体Fpの元である定数であり、cd(1-c4d)≠0を満たす。
【００２８】
楕円曲線E:x2+y2=c2(1+dx2y2)上の点P=(xP,yP)と点Q=(xQ,yQ)の楕円加算P+Q=R=(xR,yR)は、下記の式（３）の楕円加算公式で計算することができる。
【００２９】
【数４】
2015132754.tif 000006
【００３０】
ここで、単位元Ο=(0,c)であり、点P=(xP,yP)の逆元は、-P=(-xP,yP)である。P=Qの場合も、式（３）の楕円加算公式により正しく計算することができる。
【００３１】
エドワーズ標準型の楕円加算公式についての詳細な説明は、下記の参考文献１〜３を参照されたい。
〔参考文献１〕Harold M. Edwards, “A Normal Form for Elliptic Curves”, Bulletin of the American Mathematical Society, vol. 44, No. 3, pp. 393-422, 2007.
〔参考文献２〕Daniel J. Bernstein and Tanja Lange, “Faster Addition and Doubling on Elliptic Curves”, ASIACRYPT 2007, pp. 29-50, 2007.
〔参考文献３〕Daniel J. Bernstein and Tanja Lange, “Inverted Edwards Coordinates”, AAECC 2007, pp. 20-27, 2007.
【００３２】
エドワーズ標準型の楕円加算公式は、楕円曲線の形が限定されるためワイエルストラス標準型よりも汎用性に劣るが、どのような二点であっても一つの楕円加算公式で計算ができる。したがって、エドワーズ標準型の楕円加算公式を用いれば、マルチパーティ計算において安全に楕円加算を行うことが可能となる。
【００３３】
［秘密分散方式］
この発明で用いる秘密分散方式は、以下の条件を満たす限り、どのような秘密分散方式であってもよい。
・分散値[a]pと分散値[b]pの加算[a]p+[b]p→[a+b mod p]pを通信なく、すなわち単一の計算主体のみで実行することができる。
・定数aと分散値[b]pの乗算a[b]p=[ab mod p]pを通信なく実行することができる。
・分散値[a]pと分散値[b]pの乗算[a]p・[b]p→[ab mod p]pを他の計算主体と協調して無条件に安全に実行することができる。
【００３４】
上記の条件を満たす秘密分散方式として、例えば、下記の参考文献４に記載された秘密分散方式を利用することができる。
〔参考文献４〕Ronald Cramer, Ivan Damgard, and Ueli Maurer, “General secure multiparty computation from any linear secret-sharing scheme”, Advances in Cryptology - EuroCrypt 2000, pp. 316-334, 2000.
【００３５】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００３６】
［実施形態］
図１を参照して、実施形態に係るマルチパーティ計算システム１の構成例を説明する。マルチパーティ計算システム１は、N（≧3）台の秘匿計算装置２1,…,２Nとネットワーク９を含む。秘匿計算装置２1,…,２Nはネットワーク９にそれぞれ接続される。ネットワーク９は秘匿計算装置２1,…,２Nそれぞれが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、秘匿計算装置２1,…,２Nそれぞれとは必ずしもネットワーク９を介してオンラインで通信可能である必要はない。例えば、ある秘匿計算装置２n（1≦n≦N）が出力する情報をＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から異なる秘匿計算装置２m（1≦m≦N、n≠m）へオフラインで入力するように構成してもよい。
【００３７】
図２を参照して、マルチパーティ計算システム１に含まれる秘匿計算装置２の構成例を説明する。秘匿計算装置２は、入力部１０、楕円加算部１２、楕円スカラー倍算部１４及び出力部１６を含む。秘匿計算装置２は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘匿計算装置２は、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘匿計算装置２に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００３８】
図３を参照して、秘匿計算装置２に含まれる楕円加算部１２の構成例を説明する。楕円加算部１２は、第一乗算部２０、第二乗算部２２、逆数計算部２４及び座標計算部２６を含む。
【００３９】
図４を参照して、秘匿計算装置２に含まれる楕円スカラー倍算部１４の構成例を説明する。楕円スカラー倍算部１４は、乱数生成部４０、乱数加算部４２、乱数分散部４４、フラグ設定部４６、第一倍算部４８、加算部５０、フラグ検査部５２、第二倍算部５４及び減算部５６を含む。
【００４０】
N台の秘匿計算装置２1,…,２Nは、それぞれ同様の処理を行う。以降の説明では、断わりのない限り、N台の秘匿計算装置２1,…,２Nから任意に選択したn番目の秘匿計算装置２n（n=1,…,N）の実行する処理を中心に説明するが、他の秘匿計算装置２m（m=1,…,N、m≠n）も同様の処理を実行するものである。
【００４１】
＜楕円加算方法＞
図５を参照しながら、実施形態に係るマルチパーティ計算システム１が実行する楕円加算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００４２】
以下では、pは3より大きい素数（すなわち、p>3）である。Zpは素数pを法とする剰余環である。FpはZp=Fpである位数pの有限体である。E:x2+y2=c2(1+dx2y2)は有限体Fp上で定義されたエドワーズ標準型の楕円曲線である。ここで、c,dは有限体Fpの元（すなわち、c,d∈Fp）であり、cd(1-c4d)≠0を満たすものとする。
【００４３】
ステップＳ１０ａにおいて、入力部１０へ楕円曲線E:x2+y2=c2(1+dx2y2)上の点P=(xP,yP)を秘密分散した分散値[P]p=([xP]p,[yP]p)及び楕円曲線E:x2+y2=c2(1+dx2y2)上の点Q=(xQ,yQ)を秘密分散した分散値[Q]p=([xQ]p,[yQ]p)が入力される。分散値[P]p及び分散値[Q]pは楕円加算部１２へ入力される。
【００４４】
ステップＳ２０からＳ２６において、楕円加算部１２は、入力された分散値[P]p=([xP]p,[yP]p)及び分散値[Q]p=([xQ]p,[yQ]p)を用いて、点Pと点Qの楕円加算P+Q=R=(xR,yR)を秘密分散した分散値[R]p=([xR]p,[yR]p)を計算する。
【００４５】
分散値[R]p=([xR]p,[yR]p)は、エドワーズ標準型の楕円加算公式を用いて、下記の式（４）により計算することができる。
【００４６】
【数５】
2015132754.tif 000007
【００４７】
式（４）はどのように計算してもよいが、少ないラウンドで計算するためには、例えば、以下の手続きに従って計算すればよい。
【００４８】
ステップＳ２０において、第一乗算部２０へ分散値[P]p=([xP]p,[yP]p)及び分散値[Q]p=([xQ]p,[yQ]p)が入力される。第一乗算部２０は、他の秘匿計算装置２m（m=1,…,N、m≠n）と協調して、分散値[u=xP・yQ]p、[v=yP・xQ]p、[s=xP・xQ]p及び[t=yP・yQ]pを計算する。各乗算は独立しているため、第一乗算部２０が各分散値の計算に要するラウンド数は1であり、通信数は4である。分散値[u]p及び分散値[v]pは第二乗算部２２及び座標計算部２６へ出力される。分散値[s]p及び分散値[t]pは座標計算部２６へ出力される。
【００４９】
ステップＳ２２において、第二乗算部２２は、他の秘匿計算装置２m（m=1,…,N、m≠n）と協調して、分散値[w=u・v]pを計算する。第二乗算部２２が分散値の計算に要するラウンド数は1であり、通信数は1である。分散値[w]pは逆数計算部２４へ出力される。
【００５０】
ステップＳ２４において、逆数計算部２４は、他の秘匿計算装置２m（m=1,…,N、m≠n）と協調して、分散値[g]p←Inv([c(1+dw)]p)及び分散値[h]p←Inv([c(1-dw)]p)を計算する。ここで、Invは逆数を計算する関数である。Inv関数の演算は2ラウンドを必要とするため、逆数計算部２４が分散値の計算に要するラウンド数は2であり、通信数は4である。分散値[g]p及び分散値[h]pは座標計算部２６へ出力される。
【００５１】
ステップＳ２６において、座標計算部２６は、他の秘匿計算装置２m（m=1,…,N、m≠n）と協調して、点R=(xR,yR)のx座標の分散値[xR=(u+v)・g]p及び点Rのy座標の分散値[yR=(s-t)・h]pを計算する。各乗算は独立しているため、座標計算部２６が分散値の計算に要するラウンド数は1であり、通信数は2である。分散値[xR]p及び分散値[yR]pは出力部１６へ出力される。
【００５２】
ステップＳ１６において、出力部１６は、点Rの分散値[R]p=([xR]p,[yR]p)を出力する。
【００５３】
楕円加算部１２が、ステップＳ１０からステップＳ１６の処理を実行するために、5ラウンド、11乗算分の通信量を必要とする。なお、点Pの分散値[P]p=([xP]p,[yP]p)から逆元の点-Pの分散値[-P]p=([-xP]p,[yP]p)を計算するためには、他の秘匿計算装置２m（m=1,…,N、m≠n）との通信は不要である。
【００５４】
楕円加算を定数ラウンドで計算するための関数EC-Addの一例を次表に示す。
【００５５】
【表１】
2015132754.tif 000008
【００５６】
ここで、各ステップの下行に示す「/*α,β.*/」の値は、αが当該ステップで必要とされるラウンド数であり、βが当該ステップで必要とされる通信数である。
【００５７】
＜楕円スカラー倍算方法＞
図６を参照しながら、実施形態に係るマルチパーティ計算システム１が実行する楕円スカラー倍算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
【００５８】
ステップＳ１０ｂにおいて、入力部１０へ楕円曲線E:x2+y2=c2(1+dx2y2)上の点P=(xP,yP)を秘密分散した分散値[P]p=([xP]p,[yP]p)及び指数e∈Zpを秘密分散した分散値[e]pが入力される。分散値[P]p及び分散値[e]pは楕円スカラー倍算部１４へ入力される。
【００５９】
ステップＳ４０からＳ５６において、楕円スカラー倍算部１４は、入力された分散値[P]p=([xP]p,[yP]p)及び分散値[e]pを用いて、点Pの楕円スカラー倍算eP=R=(xR,yR)を秘密分散した分散値[R]p=([xR]p,[yR]p)を計算する。
【００６０】
楕円スカラー倍算は楕円加算を用いれば様々な方法で実現することができるが、定数ラウンドで計算するためには、例えば、次表に例示する関数EC-Exp-Priを以下の手続きに従って計算すればよい。なお、表中の記号と文中で使用する記号が異なる場合があれば適宜読み替えられたい。以降に具体例を示す関数についても同様である。
【００６１】
【表２】
2015132754.tif 000009
【００６２】
ステップＳ４０において、乱数生成部４０は、他の秘匿計算装置２m（m=1,…,N、m≠n）と協調して、Lビットの乱数sの分散値[s]pと、乱数sのビット表現s1,…,sLをビット毎に秘密分散した分散値[s]B=([s1]p,…,[sL]p)との組([s]B,[s]p)を生成する。分散値[s]pは乱数加算部４２へ出力される。分散値[s]Bはフラグ設定部４６及び第二乗算部５４へ出力される。乱数の生成方法としては、下記参考文献５に記載されているSolvedBits関数を利用することができる。
〔参考文献５〕Tomas Toft, “Constant-Rounds, Almost-Linear Bit-Decomposition of Secret Shared Values”, CT-RSA 2009, pp. 357-371, 2009.
【００６３】
ステップＳ４２において、乱数加算部４２は、入力された分散値[e]pと分散値[s]pを加算して分散値[t=e+s mod p]pを求める。続いて、他の秘匿計算装置２m（m=1,…,N、m≠n）と協調して、分散値[t]pを復元して値tを得る。値tは乱数分散部４４及び第一倍算部４８へ出力される。
【００６４】
ステップＳ４４において、乱数分散部４４は、値tのビット表現t1,…,tLをビット毎に秘密分散した分散値[t]B=([t1]p,…,[tL]p)を生成する。分散値[t]Bはフラグ設定部４６へ出力される。
【００６５】
ステップＳ４６において、フラグ設定部４６は、分散値[s]Bと分散値[t]Bの各ビットを比較し、値tが乱数sより小さければフラグ[f=1]pを設定し、値tが乱数s以上であればフラグ[f=0]pを設定する。フラグ[f]pはフラグ検査部５２へ出力される。
【００６６】
ビット表現された値をビット毎に秘密分散した分散値同士を比較する方法としては、上記参考文献５もしくは下記参考文献６に記載されているBitLessThan関数を利用することができる。
〔参考文献６〕Chao Ning and Qiuliang Xu, “Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition”, ASIACRYPT 2010, pp. 483-500, 2010.
【００６７】
ステップＳ４８において、第一倍算部４８は、入力された分散値[P]p及び値tを用いて点Pのt倍算tP=Tの分散値[T]pを計算し、分散値[P]pを用いて点Pのp倍算pP=Uの分散値[U]pを計算する。分散値[T]p及び分散値[U]pは加算部５０へ出力される。また、分散値[T]pはフラグ検査部５２へも出力される。
【００６８】
楕円曲線上の点Pの分散値[P]pを公開された指数eで楕円スカラー倍算し点R=ePの分散値[R]pを計算する方法は、例えば、以下の手続きに従って計算すればよい。
【００６９】
まず、秘匿計算装置２i（i=1,…,N）はランダムな点Siを生成し、点eSiを計算する。続いて、点Si及び点eSiをそれぞれ秘密分散して、分散値[Si]p及び分散値[eSi]pを生成する。続いて、下記の式（５）により分散値[S]p及び分散値[eS]pを計算する。
【００７０】
【数６】
2015132754.tif 000010
【００７１】
次に、点Pと点Sの楕円加算P+S=T=(xT,yT)の分散値[T]p=([xT]p,[yT]p)を計算する。
【００７２】
次に、分散値[T]p=([xT]p,[yT]p)を復元して点T=(xT,yT)を得る。
【００７３】
次に、点Tのe倍算eT=U=(xU,yU)を計算する。続いて、点Uを秘密分散して分散値[U]p=([xU]p,[yU]p)を得る。
【００７４】
そして、分散値[eS]pを用いて点eSの逆元-eSの分散値[-eS]pを求め、分散値[U]pと分散値[-eS]pを楕円加算して点R=ePの分散値[R]pを求める。
【００７５】
公開された値を指数とする楕円スカラー倍算を定数ラウンドで計算するための関数EC-Exp-Pubの一例を次表に示す。
【００７６】
【表３】
2015132754.tif 000011
【００７７】
乱数の分散値とその乱数をスカラー倍した分散値との組を定数ラウンドで生成するための関数EC-Rand-Pairの一例を次表に示す。
【００７８】
【表４】
2015132754.tif 000012
【００７９】
ステップＳ５０において、加算部５０は、入力された分散値[T]pと分散値[U]pの楕円加算T+U=Vの分散値[V]pを求める。加算部５０の処理は楕円加算部１２の処理と同様であるので詳細な説明は省略する。分散値[V]pはフラグ検査部５２へ出力される。
【００８０】
ステップＳ５２において、フラグ検査部５２は、入力されたフラグ[f]pを検査し、[f=1]pであれば分散値[W]p=[V]pに設定し、[f=0]pであれば分散値[W]p=[T]pに設定する。分散値[W]pは減算部５６へ出力される。
【００８１】
フラグf=1は値tが乱数sよりも小さいときに設定される。これは、乱数加算部４２において、e+sがpを超えたことを示している。点V=T+Uであり、点T=tPであり、点U=pPであるから、V=tP+pPであり、T=tPである。つまり、f=1のときに点Vを選択し、f=0のときに点Tを選択することは、乗数eに乱数sを加算した際にmod pにより切り下げられた分を補正することを目的としている。
【００８２】
二値{0,1}のいずれかを取るフラグbの分散値[b]pを検査し、入力された点Pの分散値[P]p=([xP]p,[yP]p)もしくは点Qの分散値[Q]p=([xQ]p,[yQ]p)のいずれかを出力する方法は、下記の式（６）を計算して点Rの分散値[R]p=([xR]p,[yR]p)を求めればよい。
【００８３】
【数７】
2015132754.tif 000013
【００８４】
入力されたフラグを検査して入力された二点のいずれかを定数ラウンドで出力するための関数EC-Condの一例を次表に示す。
【００８５】
【表５】
2015132754.tif 000014
【００８６】
ステップＳ５４において、第二倍算部５４は、入力された分散値[P]p及び分散値[s]Bを用いて点Pのs倍算sP=Sの分散値[S]pを計算する。分散値[S]pは減算部５６へ出力される。
【００８７】
指数eのビット表現e1,…,eLをビット毎に秘密分散した分散値[e]B=([e1]p,…,[eL]p)を用いて楕円曲線上の点Pの分散値[P]pの楕円スカラー倍算eP=Rの分散値[R]pを求める方法は、以下の手続きに従って計算を実行すればよい。
【００８８】
まず、i=1,…,Lについて、分散値[P]pを指数2i-1で楕円スカラー倍算し、分散値[Ai]pを計算する。公開された値を指数とする楕円スカラー倍算は、上記に例示した関数EC-Exp-Pubを用いれば計算できる。
【００８９】
次に、i=1,…,Lについて、分散値[ei]pを検査し、[ei=1]pであれば[Bi]p=[Ai]pを設定し、[ei=0]pであれば[Bi]p=[0]pを設定する。入力されたフラグを検査して入力された二点のいずれかを出力する方法は、上記に例示した関数EC-Condを用いれば実現できる。
【００９０】
そして、L個の分散値[B1]p,…,[BL]pをすべて楕円加算して点S=sPの分散値[S]pを求める。
【００９１】
指数のビット表現をビット毎に秘密分散した分散値による楕円スカラー倍算を計算する定数ラウンドの関数EC-Exp-Bitの一例を次表に示す。
【００９２】
【表６】
2015132754.tif 000015
【００９３】
ここで、関数EC-Cond-Zeroは上述の関数EC-Condにおいて、3番目の引数を単位元Οの分散値[Ο]pとした関数である。したがって、EC-Cond-Zero([ei]p,[Ai]p)=EC-Cond([ei]p,[Ai]p,[Ο]p)である。
【００９４】
k個の楕円曲線上の点P1,…,Pkをすべて楕円加算した点Rの分散値[R]pを計算する方法は、以下の手続きに従って計算を実行すればよい。
【００９５】
まず、i=1,…,kについて、ランダムな点Siの分散値[Si]pを生成する。具体的には、秘匿計算装置２j（j=1,…,N）がランダムな点Si,jを生成し、点Si,jを秘密分散して分散値[Si,j]pを生成する。続いて、下記の式（７）により分散値[Si,1]p,…,[Si,L]pを総和して分散値[Si]pを計算する。
【００９６】
【数８】
2015132754.tif 000016
【００９７】
次に、i=2,…,kについて、分散値[Si-1]を用いて点Si-1の逆元-Si-1の分散値[-Si-1]を求め、分散値[-Si-1]と分散値[Pi]pを楕円加算して分散値[Ti]pを計算する。i=1については、[T1]p=[P1]pを設定する。
【００９８】
次に、i=1,…,kについて、分散値[Ti]と分散値[Si]pを楕円加算して点U=T+Sの分散値[Ui]pを計算する。
【００９９】
次に、i=1,…,kについて、分散値[Ui]p=([xUi]p,[yUi]p)を復元して点Ui=(xUi,yUi)を得る。
【０１００】
次に、下記の式（８）により、k個の点U1,…,Ukを総和して点Uを求める。続いて、点Uを秘密分散して分散値[U]p=([xU]p,[yU]p)を得る。
【０１０１】
【数９】
2015132754.tif 000017
【０１０２】
そして、分散値[Sk]pを用いて点Skの逆元-Skの分散値[-Sk]pを求め、分散値[U]pと分散値[-Sk]pを楕円加算して点Rの分散値[R]pを求める。
【０１０３】
複数個の楕円曲線上の点をすべて楕円加算する定数ラウンドの関数EC-Add-UFの一例を次表に示す。
【０１０４】
【表７】
2015132754.tif 000018
【０１０５】
乱数の分散値を生成する定数ラウンドの関数EC-Randの一例を次表に示す。
【０１０６】
【表８】
2015132754.tif 000019
【０１０７】
ステップＳ５６において、減算部５６は、入力された分散値[S]pを用いて点Sの逆元-Sの分散値[-S]pを求め、入力された分散値[W]pと分散値[-S]pを楕円加算して点Rの分散値[R]pを求める。減算部５６の処理は楕円加算部１２の処理と同様であるので詳細な説明は省略する。分散値[R]pは出力部１６へ出力される。
【０１０８】
ステップＳ１６において、出力部１６は、点Rの分散値[R]p=([xR]p,[yR]p)を出力する。
【０１０９】
このように、実施形態に係るマルチパーティ計算システム１は、計算対象の二点がいかなる点であっても特別な処理を必要とせず、楕円曲線上での楕円加算を安全に計算することができる。また、楕円スカラー倍算についても、楕円加算を応用することで実現できるため、安全に計算することができる。
【０１１０】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１１１】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１１２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１１６】
１  マルチパーティ計算システム
２  秘匿計算装置
９  ネットワーク
１０  入力部
１２  楕円加算部
１４  楕円スカラー倍算部
１６  出力部
２０  第一乗算部
２２  第二乗算部
２４  逆数計算部
２６  座標計算部
４０  乱数生成部
４２  乱数加算部
４４  乱数分散部
４６  フラグ設定部
４８  第一倍算部
５０  加算部
５２  フラグ検査部
５４  第二倍算部
５６  減算部
【図１】
2015132754.tif 000024
【図２】
2015132754.tif 000025
【図３】
2015132754.tif 000026
【図４】
2015132754.tif 000027
【図５】
2015132754.tif 000028
【図６】
2015132754.tif 000029