(57)【要約】  c=abの関係を持つ値a, b, cの秘匿文の組を効率よく作成する。秘匿文生成部１２は、i=0, …, mについて、xi=f(ki)を満たすxiの秘匿文[xi]と、yi=g(ki)を満たすyiの秘匿文[yi]とを生成する。断片生成部１３は、i=1, …, mについて、[xi]-[ai]を復元したεiと[yi]-[bi]を復元したρiとを生成し、[ci]+εi[bi]+ρi[ai]+εiρiを計算して秘匿文[z1], …, [zm]を生成する。乱数合成部１４は、相異なる値k0, …, kmと秘匿文[z1], …, [zm]を用いて秘匿文[z0]を生成する。
2017065123.tif 000002
【特許請求の範囲】
【請求項１】
tを0以上の整数とし、m=2t+1とし、iを1以上m以下の各整数とし、[ai], [bi], [ci]をそれぞれm個の値ai, bi, ciの秘匿文とし、k0, …, kmをm+1個の相異なる値とし、f(x), g(x)をランダムなt次多項式とし、
i=0, …, mについて、xi=f(ki)を満たすxiの秘匿文[xi]と、yi=g(ki)を満たすyiの秘匿文[yi]とを生成する秘匿文生成部と、
i=1, …, mについて、[xi]-[ai]を復元したεiと[yi]-[bi]を復元したρiとを生成し、[ci]+εi[bi]+ρi[ai]+εiρiを計算して秘匿文[z1], …, [zm]を生成する断片生成部と、
次式を計算して秘匿文[z0]を生成する乱数合成部と、
【数１１】
2017065123.tif 000013
を含む秘密乱数合成装置。
【請求項２】
請求項１に記載の秘密乱数合成装置であって、
上記秘匿文生成部は、i=0, …, tについて、ランダムな値の秘匿文[xi], [yi]を生成し、i=t+1, …, mについて、次式を計算して秘匿文[xi], [yi]を生成するものである、
【数１２】
2017065123.tif 000014
秘密乱数合成装置。
【請求項３】
請求項２に記載の秘密乱数合成装置であって、
[ai], [bi], [ci], [xi], [yi], [zi]は加法的秘密分散による秘匿文であり、
上記秘匿文生成部は、i=0, …, tについて、ランダムな値を生成して秘匿文[xi]のシェアとし、ランダムな値を生成して秘匿文[yi]のシェアとするものである、
秘密乱数合成装置。
【請求項４】
tを0以上の整数とし、m=2t+1とし、iを1以上m以下の各整数とし、[ai], [bi], [ci]をそれぞれm個の値ai, bi, ciの秘匿文とし、k0, …, kmをm+1個の相異なる値とし、f(x), g(x)をランダムなt次多項式とし、
秘匿文生成部が、i=0, …, mについて、xi=f(ki)を満たすxiの秘匿文[xi]と、yi=g(ki)を満たすyiの秘匿文[yi]とを生成する秘匿文生成ステップと、
断片生成部が、i=1, …, mについて、[xi]-[ai]を復元したεiと[yi]-[bi]を復元したρiとを生成し、[ci]+εi[bi]+ρi[ai]+εiρiを計算して秘匿文[z1], …, [zm]を生成する断片生成ステップと、
乱数合成部が、次式を計算して秘匿文[z0]を生成する乱数合成ステップと、
【数１３】
2017065123.tif 000015
を含む秘密乱数合成方法。
【請求項５】
請求項１から３のいずれかに記載の秘密乱数合成装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号応用技術に関し、特に、入力データを明かすことなく乱数を合成する技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元することなく特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１参照）。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元することなく、加減算、定数加算、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。【０００３】
秘密計算で乗算を行う場合に、c=abの関係を持つ平文a, b, cの秘匿文を使って効率よく乗算を行うことができる方法として、非特許文献２の方法がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克巳、“軽量検証可能3パーティ秘匿関数計算の再考”、CSS、2010年
【非特許文献２】Ivan Damgard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart, “Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits”, Computer Security - ESORICS 2013, vol. 8134 of Lecture Notes in Computer Science, pp. 1-18, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献２に記載された従来技術では、平文a, b, cがc=abの関係を持つ秘匿文の組を作るために非常に計算コストの大きいsomewhat準同型暗号を用いており、効率が悪かった。【０００６】
この発明の目的は、このような点に鑑みて、c=abの関係を持つ値a, b, cの秘匿文の組を効率よく作成する技術を提供することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の秘密乱数合成装置は、tを0以上の整数とし、m=2t+1とし、iを1以上m以下の各整数とし、[ai], [bi], [ci]をそれぞれm個の値ai, bi, ciの秘匿文とし、k0, …, kmをm+1個の相異なる値とし、f(x), g(x)をランダムなt次多項式とし、i=0, …, mについて、xi=f(ki)を満たすxiの秘匿文[xi]と、yi=g(ki)を満たすyiの秘匿文[yi]とを生成する秘匿文生成部と、i=1, …, mについて、[xi]-[ai]を復元したεiと[yi]-[bi]を復元したρiとを生成し、[ci]+εi[bi]+ρi[ai]+εiρiを計算して秘匿文[z1], …, [zm]を生成する断片生成部と、次式を計算して秘匿文[z0]を生成する乱数合成部と、を含む。【０００８】
【数１】
2017065123.tif 000003
【発明の効果】
【０００９】
この発明の秘密乱数合成技術によれば、c=abの関係を持つ値a, b, cの秘匿文の組を効率よく作成することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、秘密乱数合成システムの機能構成を例示する図である。
【図２】図２は、秘密乱数合成装置の機能構成を例示する図である。
【図３】図３は、秘密乱数合成方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１１】
実施形態の説明に先立ち、この明細書における表記方法および用語の定義について説明する。
【００１２】
＜表記方法＞
ある値aを暗号化や秘密分散などにより秘匿化した値をaの秘匿文と呼び、[a]と表記する。また、aを[a]の平文と呼ぶ。秘匿化が秘密分散である場合は、[a]により各パーティが持つ秘密分散の断片の集合を参照する。秘匿文[a]のうちi番目のパーティPiが持つシェアを[a]iで参照する。なお、シェアとは秘密分散された断片のことであり、パーティとは秘密計算を協調して行う各参加者のことである。
【００１３】
＜復元＞
秘匿文[a]から平文aを計算する処理を復元と呼び、次式のように記述する。
【００１４】
【数２】
2017065123.tif 000004
【００１５】
＜加算、減算、定数倍＞
秘匿文に対する加算、減算の各演算は、二つの値a, bの秘匿文[a], [b]を入力とし、a+b, a-bの計算結果d1, d2の秘匿文[d1], [d2]を計算する。秘匿文に対する定数倍の演算は、値aの秘匿文[a]と平文cとを入力とし、caの計算結果d3の秘匿文[d3]を計算する。これらの演算の実行をそれぞれ次式のように記述する。
【００１６】
【数３】
2017065123.tif 000005
【００１７】
なお、誤解を招く恐れのない場合は、Add([a], [b]), Sub([a], [b]), CMul(c, [a])をそれぞれ[a]+[b], [a]-[b], c[a]と略記する。
【００１８】
＜ランダムな秘匿文の生成＞
誰も知らないランダムな値rの秘匿文[r]を生成する処理を次式のように記述する。
【００１９】
【数４】
2017065123.tif 000006
【００２０】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２１】
［第一実施形態］
第一実施形態の秘密乱数合成システムは、図１に例示するように、n（≧2）台の秘密乱数合成装置１1, …, １nを含む。この実施形態では、秘密乱数合成装置１1, …, １nはそれぞれ通信網２へ接続される。通信網２は、秘密乱数合成装置１1, …, １nそれぞれと通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密乱数合成装置１i（i∈{0, …, n-1}）へ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで入力するように構成してもよい。
【００２２】
秘密乱数合成装置１は、図２に例示するように、入力部１１、秘匿文生成部１２、断片生成部１３、乱数合成部１４、および出力部１５を含む。この秘密乱数合成装置１が、図３に例示する各ステップの処理を行うことにより第一実施形態の秘密乱数合成方法が実現される。
【００２３】
秘密乱数合成装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密乱数合成装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密乱数合成装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密乱数合成装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００２４】
図３を参照して、第一実施形態の秘密乱数合成方法の処理手続きを説明する。
【００２５】
ステップＳ１１において、入力部１１へ、それぞれm個の値ai, bi, ciの秘匿文（[ai], [bi], [ci]）と、m+1個の値k0, …, kmとが入力される。ここで、m=2t+1であり、tは0以上の整数であり、iは1以上m以下の各整数である。値k0, …, kmは相異なる任意の値であり、すべての秘密乱数合成装置１1, …, １nに事前に共有されている。値k0, …, kmは秘匿文生成部１２へ送られる。秘匿文（[ai], [bi], [ci]）は断片生成部１３へ送られる。
【００２６】
ステップＳ１２１において、秘匿文生成部１２は、f(x)を誰も知らないランダムなt次多項式として、i=0, …, mについて、xi=f(ki)を満たすxiの秘匿文[xi]を生成する。ランダムなt次多項式とは、各項の係数がランダムに定まるt次の多項式である。秘匿文[x1], …, [xm]は断片生成部１３へ送られる。秘匿文[x0]は出力部１５へ送られる。
【００２７】
秘匿文生成部１２は、具体的には、以下のようにして秘匿文[x0], …, [xm]を生成する。まず、i=0, …, tについて、式（１）を計算して秘匿文[x0], …, [xt]を生成する。
【００２８】
【数５】
2017065123.tif 000007
【００２９】
次に、i=t+1, …, mについて、式（２）を計算して秘匿文[xt+1], …, [xm]を生成する。
【００３０】
【数６】
2017065123.tif 000008
【００３１】
ステップＳ１２２において、秘匿文生成部１２は、g(x)を誰も知らないランダムなt次多項式として、i=0, …, mについて、yi=g(ki)を満たすyiの秘匿文[yi]を生成する。秘匿文[y0], …, [ym]の生成方法は、秘匿文[x0], …, [xm]と同様にして行えばよい。秘匿文[y1], …, [ym]は断片生成部１３へ送られる。秘匿文[y0]は出力部１５へ送られる。
【００３２】
ステップＳ１３１において、断片生成部１３は、i=1, …, mについて、式（３）を計算して値εiを生成する。
【００３３】
【数７】
2017065123.tif 000009
【００３４】
ステップＳ１３２において、断片生成部１３は、i=1, …, mについて、式（４）を計算して値ρiを生成する。
【００３５】
【数８】
2017065123.tif 000010
【００３６】
ステップＳ１３３において、断片生成部１３は、i=1, …, mについて、式（５）を計算して秘匿文[zi]を生成する。秘匿文[z1], …, [zm]は乱数合成部１４へ送られる。
【００３７】
【数９】
2017065123.tif 000011
【００３８】
ステップＳ１４において、乱数合成部１４は、式（６）を計算して秘匿文[z0]を生成する。秘匿文[z0]は出力部１５へ送られる。
【００３９】
【数１０】
2017065123.tif 000012
【００４０】
ステップＳ１５において、出力部１５は、秘匿文の組（[x0], [y0], [z0]）を出力する。
【００４１】
［第二実施形態］
第二実施形態の秘密乱数合成方法は、加法的秘密分散により秘匿化した場合にc=abの関係を持つ値a, b, cの秘匿文の組を生成する方法である。この実施形態では、入力される秘匿文[ai], [bi], [ci]と、生成される秘匿文[xi], [yi], [zi]とが加法的秘密分散による秘匿文である。加法的秘密分散については、例えば、非特許文献２に記載されている。
【００４２】
第二実施形態の秘匿文生成部１２は、ステップＳ１２１において、i=0, …, tについて秘匿文[xi]を生成する際に、各パーティがランダムな値を生成し、秘匿文[xi]のシェアとする。また、ステップＳ１２２において、i=0, …, tについて秘匿文[yi]を生成する際に、各パーティがランダムな値を生成し、秘匿文[yi]のシェアとする。
【００４３】
上記のように構成することにより、この発明の秘密乱数合成技術によれば、誰も知らないことが期待され、ci=aibiを満たすランダムなm（=2t+1）組の値（ai, bi, ci）の秘匿文（[ai], [bi], [ci]）のうち、いずれかt組の値が漏洩してしまっている場合であっても、誰も知らないz=xyを満たすランダムな値の組（x, y, z）の秘匿文（[x], [y], [z]）を作成することができる。
【００４４】
この発明のポイントは、ランダムな値x0, y0の秘匿文に対する乗算を、2t+1回の乗算に分解して行なっていることである。このとき、(t+1, 2t+1)しきい値秘密分散を利用して、[x]および[y]を2t+1個の秘匿文に分散しているため、2t+1組の秘匿文のうちt組の情報が漏洩していても、xおよびyを復元することができない。その結果、誰も知らないランダムな値の組の秘匿文を作ることができる。
【００４５】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４６】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４８】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2017065123.tif 000016
【図２】
2017065123.tif 000017
【図３】
2017065123.tif 000018
【国際調査報告】
2017065123.tif 000019
2017065123.tif 000020
2017065123.tif 000021
2017065123.tif 000022