(57)【特許請求の範囲】
【請求項１】
3台の分散値変換装置p0, p1, p2を含む分散値変換システムであって、
i=0, 1とし、i'∈{0, 1}とし、i≠i'とし、
上記分散値変換装置piは、
情報をShamir秘密分散により3つのシェアに分割するために用いる座標x0, x1, x2を記憶する座標記憶部と、
上記分散値変換装置pi'と乱数rを共有する乱数共有部と、
上記座標x0, x1から座標0をラグランジュ補間するための係数λ0, λ1を計算する第一係数計算部と、
次式を計算することにより、加法的秘密分散のシェア<a>iをShamir秘密分散のシェア[a]iへ変換する第一変換部と、
【数８】
0005872085.tif 000009
上記座標x0, x1から上記座標x2をラグランジュ補間するための係数λ'0, λ'1を計算する第二係数計算部と、
次式を計算することにより、Shamir秘密分散のシェア[a]iから値[b]iを計算する第二変換部と、
【数９】
0005872085.tif 000010
を含み、
上記分散値変換装置p2は、
上記値[b]0と上記値[b]1とを加算してShamir秘密分散のシェア[a]2を計算するシェア生成部
を含む分散値変換システム。
【請求項２】
i∈{0, 1}とし、i'∈{0, 1}とし、i≠i'とし、
情報をShamir秘密分散により3つのシェアに分割するために用いる座標x0, x1, x2を記憶する座標記憶部と、
他の分散値変換装置pi'と乱数rを共有する乱数共有部と、
上記座標x0, x1から座標0をラグランジュ補間するための係数λ0, λ1を計算する第一係数計算部と、
次式を計算することにより、加法的秘密分散のシェア<a>iをShamir秘密分散のシェア[a]iへ変換する第一変換部と、
【数１０】
0005872085.tif 000011
上記座標x0, x1から上記座標x2をラグランジュ補間するための係数λ'0, λ'1を計算する第二係数計算部と、
次式を計算することにより、Shamir秘密分散のシェア[a]iから値[b]iを計算する第二変換部と、
【数１１】
0005872085.tif 000012
を含む分散値変換装置。
【請求項３】
i=0, 1とし、i'∈{0, 1}とし、i≠i'とし、
分散値変換装置piの座標記憶部に、情報をShamir秘密分散により3つのシェアに分割するために用いる座標x0, x1, x2が記憶されており、
上記分散値変換装置piが、分散値変換装置pi'と乱数rを共有する乱数共有ステップと、
上記分散値変換装置piが、上記座標x0, x1から座標0をラグランジュ補間するための係数λ0, λ1を計算する第一係数計算ステップと、
上記分散値変換装置piが、次式を計算することにより、加法的秘密分散のシェア<a>iをShamir秘密分散のシェア[a]iへ変換する第一変換ステップと、
【数１２】
0005872085.tif 000013
上記分散値変換装置piが、上記座標x0, x1から上記座標x2をラグランジュ補間するための係数λ'0, λ'1を計算する第二係数計算ステップと、
上記分散値変換装置piが、次式を計算することにより、Shamir秘密分散のシェア[a]iから値[b]iを計算する第二変換ステップと、
【数１３】
0005872085.tif 000014
分散値変換装置p2が、上記値[b]0と上記値[b]1とを加算してShamir秘密分散のシェア[a]2を計算するシェア生成ステップと、
を含む分散値変換方法。
【請求項４】
請求項２に記載の分散値変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密分散技術に関し、特に、ある秘密分散の分散値を他の秘密分散の分散値へ変換する技術に関する。
【背景技術】
【０００２】
秘密分散とは、データを複数に分割した分散値に変換し、一定個数以上のシェアを用いれば元のデータを復元でき、一定個数未満のシェアからは元のデータを一切復元できなくする技術である。なお、秘密分散した複数個の値の組を分散値と呼び、分散値のうちの１個の断片をシェアと呼ぶ。
【０００３】
秘密分散の例としては、Shamir秘密分散（Shamir's Secret Sharing）や加法的秘密分散（Additive Secret Sharing）などが挙げられる。非特許文献１には、加法的秘密分散の分散値をShamir秘密分散の分散値へ変換する技術が記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】五十嵐大、濱田浩気、菊池亮、千田浩司、“インターネット環境レスポンス1秒の統計処理を目指した, 秘密計算基数ソートの改良”、SCIS2014、2014年
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載された加法的秘密分散からShamir秘密分散へ分散値を変換する技術では、通信量が大きいという課題がある。通信量は、秘密計算時に計算主体間で行われる通信の、全通信路の総量である。
【０００６】
この発明の目的は、このような点に鑑みて、加法的秘密分散の分散値をShamir秘密分散の分散値へ変換する際の通信量を削減することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の分散値変換システムは、3台の分散値変換装置p0, p1, p2を含む分散値変換システムであって、i=0, 1とし、i'∈{0, 1}とし、i≠i'とし、分散値変換装置piは、情報をShamir秘密分散により3つのシェアに分割するために用いる座標x0, x1, x2を記憶する座標記憶部と、分散値変換装置pi'と乱数rを共有する乱数共有部と、座標x0, x1から座標0をラグランジュ補間するための係数λ0, λ1を計算する第一係数計算部と、次式を計算することにより、加法的秘密分散のシェア<a>iをShamir秘密分散のシェア[a]iへ変換する第一変換部と、
【数１】
0005872085.tif 000002
座標x0, x1から座標x2をラグランジュ補間するための係数λ'0, λ'1を計算する第二係数計算部と、次式を計算することにより、Shamir秘密分散のシェア[a]iから値[b]iを計算する第二変換部と、
【数２】
0005872085.tif 000003
を含み、分散値変換装置p2は、値[b]0と値[b]1とを加算してShamir秘密分散のシェア[a]2を計算するシェア生成部を含む。
【発明の効果】
【０００８】
従来技術では、加法的秘密分散からShamir秘密分散へ分散値を変換する際の通信量は、疑似乱数を利用する場合で体要素３個分、疑似乱数を利用しない場合で体要素６個分であった。この発明の分散値変換技術では、疑似乱数を利用する場合で体要素２個分、疑似乱数を利用しない場合で体要素３個分の通信量で、加法的秘密分散からShamir秘密分散へ分散値を変換することができる。したがって、この発明の分散値変換技術によれば、加法的秘密分散の分散値をShamir秘密分散の分散値へ従来よりも少ない通信量で効率的に変換することができる。また、非特許文献１の秘密計算基数ソートにこの発明を適用することで、効率的なソートを実現することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、分散値変換システムの機能構成を例示する図である。
【図２】図２は、分散値変換装置の機能構成を例示する図である。
【図３】図３は、分散値変換方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立ち、この明細書における表記方法およびこの発明の基本的な考え方について説明する。
【００１１】
［表記方法］
piは、i番目のシェアを所持するパーティを表す。
P=(p0,…,pn-1)は、シェアを所持するnパーティ全体の集合を表す。
[・]x（角括弧）は、平文・のShamir秘密分散による分散値を表す。xは平文空間の要素数を表す。x=pのとき、xは省略して[・]と表す。pは群Zpの位数である素数である。
[・]iは、Shamir秘密分散値[・]のうち、パーティpi∈Pが所持するシェアを表す。
{・}x（波括弧）は、平文・の複製型秘密分散による分散値を表す。xは平文空間の要素数を表す。x=2のとき、xは省略して{・}と表す。
{・}iは、複製型秘密分散値{・}のうち、パーティpi∈Pが所持するシェアを表す。
<・>x（山括弧）は、平文・の加法的秘密分散による分散値を表す。xは平文空間の要素数を表す。x=pのとき、xは省略して<・>と表す。
<・>iは、加法型秘密分散値<・>のうち、パーティpi∈Pが所持するシェアを表す。
【００１２】
［Shamir秘密分散］
Shamir秘密分散（Shamir's Secret Sharing）は(k,n)-秘密分散の一つである。(k,n)-秘密分散は、入力された平文をn個に分割した分散値をn個の計算主体に分散して保持しておき、任意のk個のシェアが揃えば平文を復元でき、k個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。このとき、n, kは1以上の整数であり、n=2k-1である。Shamir秘密分散についての詳細は下記参考文献１を参照されたい。
〔参考文献１〕A. Shamir, “How to share a secret”, Communications of the ACM, vol. 22(11), pp. 612-613, 1979.
【００１３】
Shamir秘密分散では、i番目のパーティpiに座標xiを割り当て、乱数riを用いて、次式により、平文aを分散する。
【数３】
0005872085.tif 000004
【００１４】
Shamir秘密分散のメリットは、データ容量が小さいことである。一方、デメリットは、体の要素数がn+1以上でなければならず、mod 2は使えないことである。
【００１５】
［複製型秘密分散］
複製型秘密分散（Replicated Secret Sharing）は(k,n)-秘密分散の一つである。複製型秘密分散についての詳細は下記参考文献２を参照されたい。
〔参考文献２〕R. Cramer, I. Damgard, and Y. Ishai, “Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation”, TCC 2005, vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, 2005.
【００１６】
複製型秘密分散では、例えばn=3, k=2の場合、平文aをa:=a0+a1+a2と変形し、(a0, a1), (a1, a2), (a2, a0)の3つのシェアに分散する。シェアを構成する各要素a0, a1, a2はサブシェアと呼ぶ。
【００１７】
複製型秘密分散のメリットは、体の要素数が制限されず、mod 2が使えることである。また、体でなく群でも利用できる。一方、デメリットは、各シェアのサイズが比較的大きくなることである。
【００１８】
［加法的秘密分散］
加法的秘密分散とは、複製型秘密分散による(k,k)-秘密分散である。(k,k)-秘密分散とは、(k,n)-秘密分散において、n=kとした場合である。(k,k)-秘密分散では、全パーティのシェアが集まらない限り平文を復元することはできない。加法的秘密分散は、k個のシェアを加算するだけで平文が復元される最もシンプルな秘密分散である。
【００１９】
加法的秘密分散では、平文aは次式を満たすようにk個の分散値<a>0,…,<a>k-1に分散される。
【数４】
0005872085.tif 000005
【００２０】
加法的秘密分散のメリットは、体の要素数が制限されず、mod 2が使えることである。また、体でなく群でも利用でき、シェアを合計したデータ量が最も小さく、演算が高速である。一方、デメリットは、冗長性がないことである。
【００２１】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２２】
実施形態の分散値変換システムは、図１に例示するように、3台の分散値変換装置１1,１2,１3を含む。本形態では、分散値変換装置１1,１2,１3はそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、分散値変換装置１1,１2,１3へ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から分散値変換装置１1,１2,１3へオフラインで入力するように構成してもよい。
【００２３】
分散値変換装置１i（i=1,2,3）は、図２に例示するように、入力部１０、乱数共有部１１、第一係数計算部１２、第一変換部１３、第二係数計算部１４、第二変換部１５、シェア生成部１６、出力部１７、および座標記憶部１８を含む。
【００２４】
分散値変換装置１iは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。分散値変換装置１iは、例えば、中央演算処理装置の制御のもとで各処理を実行する。分散値変換装置１iに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。分散値変換装置１iの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００２５】
分散値変換装置１iの備える座標記憶部１８は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００２６】
図３を参照して、実施形態の分散値変換方法の処理手続きを説明する。
【００２７】
以下では、p0, p1, p2を協調動作して分散値の変換を行う3台の分散値変換装置とする。p0, p1, p2は論理的に分散値変換装置の役割を指し示す符号であり、どの分散値変換装置１1,１2,１3がどの分散値変換装置p0, p1, p2に対応するかは実行時に任意に決定される。
【００２８】
座標記憶部１８には、ある情報をShamir秘密分散により3個のシェアに分割するために用いる3個の座標x0, x1, x2が記憶されている。座標x0, x1, x2の求め方は、上記参考文献１を参照されたい。
【００２９】
ステップＳ１０0において、分散値変換装置p0の入力部１０へ変換対象となる加法的秘密分散のシェア<a>0が入力される。同様に、ステップＳ１０1において、分散値変換装置p1の入力部１０へ変換対象となる加法的秘密分散のシェア<a>1が入力される。加法的秘密分散のシェア<a>i（i=0, 1）は、第一変換部１３へ送られる。加法的秘密分散のシェア<a>0, <a>1は情報aを2つに分割した分散値である。すなわち、a:=<a>0+<a>1である。
【００３０】
ステップＳ１１において、分散値変換装置p0の乱数共有部１１と分散値変換装置p1の乱数共有部１１とは、乱数rを共有する。乱数rは、第二変換部１５へ送られる。乱数の共有は、一方の分散値変換装置pi（i∈{0, 1}）が乱数rを生成し、その乱数rを他方の分散値変換装置pi'（i'∈{0, 1}、i≠i'）へ送信すればよい。もしくは、分散値変換装置piとpi'とで事前にシードを共有しておき、そのシードを用いて疑似乱数rを生成してもよい。共有したシードから疑似乱数を求める方法であれば、通信なしで乱数rを共有することができる。
【００３１】
ステップＳ１２において、分散値変換装置pi（i=0, 1）の第一係数計算部１２は、座標記憶部１８から座標x0, x1を読み出し、座標x0, x1から座標0をラグランジュ補間するための係数λ0, λ1を計算する。係数λ0, λ1は、第一変換部１３へ送られる。
【００３２】
ステップＳ１３0において、分散値変換装置p0の第一変換部１３は、i=0として次式を計算し、加法的秘密分散のシェア<a>0をShamir秘密分散のシェア[a]0へ変換する。同様に、ステップＳ１３1において、分散値変換装置p1の第一変換部１３は、i=1として次式を計算し、加法的秘密分散のシェア<a>1をShamir秘密分散のシェア[a]1へ変換する。Shamir秘密分散のシェア[a]i（i=0, 1）は、第二変換部１５へ送られる。
【数５】
0005872085.tif 000006
【００３３】
ステップＳ１４において、分散値変換装置pi（i=0, 1）の第二係数計算部１４は、座標記憶部１８から座標x0, x1, x2を読み出し、座標x0, x1から座標x2をラグランジュ補間するための係数λ'0, λ'1を計算する。係数λ'0, λ'1は、第二変換部１５へ送られる。
【００３４】
ステップＳ１５0において、分散値変換装置p0の第二変換部１５は、i=0について次式を計算し、値[b]0を計算する。値[b]0は、分散値変換装置p2のシェア生成部１６へ送信される。同様に、ステップＳ１５1において、分散値変換装置p1の第二変換部１５は、i=1について次式を計算し、値[b]1を計算する。値[b]1は、分散値変換装置p2のシェア生成部１６へ送信される。ステップＳ１５2において、分散値変換装置p2のシェア生成部１６は、値[b]0, [b]1を受信する。
【数６】
0005872085.tif 000007
【００３５】
ステップＳ１６において、分散値変換装置p2のシェア生成部１６は、次式により、値[b]0と値[b]1とを加算してShamir秘密分散のシェア[a]2を計算する。
【数７】
0005872085.tif 000008
【００３６】
ステップＳ１７において、分散値変換装置pi（i=0, 1, 2）の出力部１７は、Shamir秘密分散のシェア[a]iを出力する。
【００３７】
上記のように構成することにより、実施形態の分散値変換システムおよび方法は、従来よりも少ない通信量で、加法的秘密分散の分散値をShamir秘密分散の分散値へ変換することができる。特に、加法的秘密分散値のシェアが入力される2台の分散値変換装置p0, p1は、通信なしで分散値の変換を行うことができる。
【００３８】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００３９】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４１】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４４】
１０  入力部
１１  乱数共有部
１２  第一係数計算部
１３  第一変換部
１４  第二係数計算部
１５  第二変換部
１６  シェア生成部
１７  出力部
１８  座標記憶部
【要約】
【課題】少ない通信量で加法的秘密分散の分散値をShamir秘密分散の分散値へ変換する。
【解決手段】座標記憶部１８に、情報をShamir秘密分散により3つのシェアに分割するために用いる座標x0, x1, x2が記憶されている。乱数共有部１１が、他の分散値変換装置と乱数rを共有する。第一係数計算部１２が、座標x0, x1から座標0をラグランジュ補間するための係数λ0, λ1を計算する。第一変換部１３が、加法的秘密分散のシェア<a>iをShamir秘密分散のシェア[a]iへ変換する。第二係数計算部１４が、座標x0, x1から座標x2をラグランジュ補間するための係数λ'0, λ'1を計算する。第二変換部１５が、Shamir秘密分散のシェア[a]iから値[b]iを計算する。シェア生成部１６が、値[b]0と値[b]1とを加算してShamir秘密分散のシェア[a]2を計算する。
【選択図】図２【図１】
0005872085.tif 000015
【図２】
0005872085.tif 000016
【図３】
0005872085.tif 000017