(57)【特許請求の範囲】
【請求項１】
nを3以上の整数とし、n台の分散値変換装置を含む分散値変換システムであって、
上記分散値変換装置は、
乱数rの複製型秘密分散値{r}をShamir秘密分散値[r]へ変換する変換部と、
情報aのShamir秘密分散値[a]を上記Shamir秘密分散値[r]から減算してShamir秘密分散値[b]を計算する秘匿化部と、
上記Shamir秘密分散値[b]を復元して値bを生成する公開部と、
上記値bの複製型秘密分散値{b}を生成する再分散部と、
上記複製型秘密分散値{r}から上記複製型秘密分散値{b}を減算して上記情報aの複製型秘密分散値{a}を生成する復元部と、
を含む分散値変換システム。
【請求項２】
請求項１に記載の分散値変換システムであって、
上記変換部は、n=2k-1とし、複製型秘密分散値{r}の各サブシェアについて当該サブシェアを平文としてk-1個の0を用いてラグランジュ補間により復元した値を総和することで上記Shamir秘密分散値[r]へ変換するものであり、
上記公開部は、改ざん検知が可能な秘密公開方法により、上記Shamir秘密分散値[b]を復元して上記値bを生成するものであり、
上記再分散部は、上記値bと0をサブシェアとして上記複製型秘密分散値{b}を生成するものである
分散値変換システム。
【請求項３】
乱数rの複製型秘密分散値{r}をShamir秘密分散値[r]へ変換する変換部と、
情報aのShamir秘密分散値[a]を上記Shamir秘密分散値[r]から減算してShamir秘密分散値[b]を計算する秘匿化部と、
上記Shamir秘密分散値[b]を復元して値bを生成する公開部と、
上記値bの複製型秘密分散値{b}を生成する再分散部と、
上記複製型秘密分散値{r}から上記複製型秘密分散値{b}を減算して上記情報aの複製型秘密分散値{a}を生成する復元部と、
を含む分散値変換装置。
【請求項４】
nを3以上の整数とし、
n台の分散値変換装置が、乱数rの複製型秘密分散値{r}をShamir秘密分散値[r]へ変換する変換ステップと、
上記n台の分散値変換装置が、情報aのShamir秘密分散値[a]を上記Shamir秘密分散値[r]から減算してShamir秘密分散値[b]を計算する秘匿化ステップと、
少なくともn-(k-1)台の分散値変換装置が、上記Shamir秘密分散値[b]を復元して値bを生成する公開ステップと、
上記n台の分散値変換装置が、上記値bの複製型秘密分散値{b}を生成する再分散ステップと、
上記n台の分散値変換装置が、上記複製型秘密分散値{r}から上記複製型秘密分散値{b}を減算して上記情報aの複製型秘密分散値{a}を生成する復元ステップと、
を含む分散値変換方法。
【請求項５】
請求項３に記載の分散値変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、秘密分散技術に関し、特に、ある秘密分散の分散値を他の秘密分散の分散値へ変換する技術に関する。
【背景技術】
【０００２】
秘密分散とは、データを複数に分割した分散値に変換し、一定個数以上のシェアを用いれば元のデータを復元でき、一定個数未満のシェアからは元のデータを一切復元できなくする技術である。なお、秘密分散した複数個の値の組を分散値と呼び、分散値のうちの１個の断片をシェアと呼ぶ。
【０００３】
秘密分散の例としては、Shamir秘密分散（Shamir's Secret Sharing）や複製型秘密分散（Replicated Secret Sharing）が挙げられる。非特許文献１には、複製型秘密分散の分散値をShamir秘密分散の分散値へ変換する技術が記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
複製型秘密分散の分散値をShamir秘密分散の分散値へ変換する方法は従来から知られていた。逆に、Shamir秘密分散の分散値を複製型秘密分散の分散値へ変換する方法は知られていない。
【０００６】
この発明の目的は、Shamir秘密分散の分散値を複製型秘密分散の分散値へ変換する技術を提供することである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の分散値変換システムは、nを3以上の整数とし、n台の分散値変換装置を含む分散値変換システムであって、分散値変換装置は、乱数rの複製型秘密分散値{r}をShamir秘密分散値[r]へ変換する変換部と、情報aのShamir秘密分散値[a]をShamir秘密分散値[r]から減算してShamir秘密分散値[b]を計算する秘匿化部と、Shamir秘密分散値[b]を復元して値bを生成する公開部と、値bの複製型秘密分散値{b}を生成する再分散部と、複製型秘密分散値{r}から複製型秘密分散値{b}を減算して情報aの複製型秘密分散値{a}を生成する復元部と、を含む。
【発明の効果】
【０００８】
この発明の分散値変換技術によれば、Shamir秘密分散の分散値を複製型秘密分散の分散値へ変換することができる。また、変換中の改ざんを検知することができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、分散値変換システムの機能構成を例示する図である。
【図２】図２は、分散値変換装置の機能構成を例示する図である。
【図３】図３は、分散値変換方法の処理フローを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立ち、この明細書における表記方法およびこの発明の基本的な考え方について説明する。
［表記方法］
piは、i番目のシェアを所持するパーティを表す。
P=(p0,…,pn-1)は、シェアを所持するnパーティ全体の集合を表す。
P'⊆Pは、nパーティ集合Pから選択したn-(k-1)パーティの集合を表す。
[・]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は省略して{・}と表す。pは群Zpの位数である素数である。
【００１１】
［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を分散する。
【数１】
0005872084.tif 000002
【００１３】
Shamir秘密分散のメリットは、データ容量が小さいことである。一方、デメリットは、体の要素数がn+1以上でなければならず、mod 2は使えないことである。
【００１４】
［複製型秘密分散］
複製型秘密分散（Replicated Secret Sharing）は(k,n)-秘密分散の一つである。複製型秘密分散についての詳細は上記非特許文献１を参照されたい。
【００１５】
複製型秘密分散は、例えばn=3, k=2の場合、平文aをa:=a0+a1+a2と変形し、(a0, a1), (a1, a2), (a2, a0)の3つのシェアに分散する。シェアを構成する各要素a0, a1, a2はサブシェアと呼ぶ。
【００１６】
複製型秘密分散のメリットは、体の要素数が制限されず、mod 2が使えることである。また、体でなく群でも利用できる。一方、デメリットは、各シェアのサイズが比較的大きくなることである。
【００１７】
［公開値］
公開値は、nパーティすべてが同じ値を持つ平文である。例えばn=3, k=2の場合、パーティp0, p1, p2が平文aを持つ。
【００１８】
［準公開値］
準公開値はn-(k-1)パーティが同じ値を持つ平文である。このとき、その他のパーティは0を持つ。例えばn=3, k=2の場合、パーティp0, p1が平文aを持ち、パーティp2が0を持つ。準公開値は複製型秘密分散値に通信なしで変換でき、冗長性を持つ。ただし、秘密分散ではなく秘匿性はない。
【００１９】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２０】
分散値変換システムは、図１に例示するように、n（≧3）台の分散値変換装置１1,…,１nを含む。本形態では、分散値変換装置１1,…,１nはそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、分散値変換装置１1,…,１nへ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から秘密計算装置１1,…,１nへオフラインで入力するように構成してもよい。
【００２１】
分散値変換装置１i（i=1,…,n）は、図２に例示するように、入力部１０、乱数生成部１１、変換部１２、秘匿化部１３、公開部１４、再分散部１５、復元部１６、および出力部１７を含む。
【００２２】
分散値変換装置１iは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。分散値変換装置１iは、例えば、中央演算処理装置の制御のもとで各処理を実行する。分散値変換装置１iに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。分散値変換装置１iの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００２３】
図３を参照して、実施形態の分散値変換方法の処理手続きを説明する。
【００２４】
以下では、p0,…,pn-1をn個のシェアを分散して保有するn台の分散値変換装置とする。p0,…,pn-1は論理的に分散値変換装置の役割を指し示す符号であり、どの分散値変換装置１1,…,１nがどの分散値変換装置p0,…,pn-1に対応するかは実行時に任意に決定される。
【００２５】
ステップＳ１０において、n台の分散値変換装置pi（i=0,…,n-1）の入力部１０へ変換対象のShamir秘密分散値[a]iがそれぞれ入力される。Shamir秘密分散値[a]iは、秘匿化部１３へ送られる。
【００２６】
ステップＳ１１において、n台の分散値変換装置piの乱数生成部１１は、乱数rの複製型秘密分散値{r}iを生成する。複製型秘密分散値{r}iは、変換部１２へ送られる。複製型秘密分散値{r}iの生成は、例えばn=3, k=2の場合、以下のように行う。分散値変換装置p0が乱数r0を生成し、その乱数r0を分散値変換装置p1へ送信する。これにより、分散値変換装置p0とp1が乱数r0を共有する。同様に、分散値変換装置p1とp2が乱数r1を共有し、分散値変換装置p0とp2が乱数r2を共有する。分散値変換装置p0は、乱数r0とr2を組にした複製型秘密分散値{r}0=(r0, r2)を生成し、保持する。同様に、分散値変換装置p1は複製型秘密分散値{r}1=(r0, r1)を保持し、分散値変換装置p2は複製型秘密分散値{r}2=(r1, r2)を保持する。乱数生成部１１は、事前に疑似乱数を共有していれば、オフライン処理で製型秘密分散値{r}iを生成することができる。
【００２７】
ステップＳ１２において、n台の分散値変換装置piの変換部１２は、複製型秘密分散値{r}iをShamir秘密分散値[r]iへ変換する。Shamir秘密分散値[r]iは、秘匿化部１３へ送られる。複製型秘密分散値からShamir秘密分散値への変換は、例えばn=3, k=2の場合、以下のように行う。分散値変換装置p0は、複製型秘密分散値{r}0=(r0, r2)のサブシェアr0, r2をそれぞれShamir秘密分散し、Shamir秘密分散値[r0], [r2]を生成する。分散値変換装置p1は、複製型秘密分散値{r}1=(r0, r1)のサブシェアr0, r1をそれぞれShamir秘密分散し、Shamir秘密分散値[r0], [r1]を生成する。分散値変換装置p1は、Shamir秘密分散値[r1]のシェア[r1]0を分散値変換装置p0へ送信する。分散値変換装置p0は、[r0]0, [r1]0, [r2]0を総和して乱数rのShamir秘密分散値[r]0=[r0+r1+r2]0を得る。同様にして、すべての分散値変換装置piがShamir秘密分散値[r]iを得る。変換方法の詳細は、例えば上記非特許文献１を参照されたい。
【００２８】
変換部１２は、複製型秘密分散値{r}の各サブシェアについて、当該サブシェアを平文としてk-1個の0を用いてラグランジュ補間により復元した値を総和することで、オフライン処理によりShamir秘密分散値[r]iを得ることができる。具体的には、例えばn=3, k=2の場合、分散値変換装置p0が、複製型秘密分散値{r}0=(r0, r1)について、r0と0とからラグランジュ補間により求めた値を[r0]0とし、r1と0とからラグランジュ補間により求めた値を[r1]0とし、0を[r2]0とし、[r0]0, [r1]0, [r2]0を総和して[r]0=[r0+r1+r2]0を得る。同様にして、すべての分散値変換装置p1, p2がShamir秘密分散値[r]1, [r]2を得る。
【００２９】
ステップＳ１３において、n台の分散値変換装置piの秘匿化部１３は、Shamir秘密分散値[a]iをShamir秘密分散値[r]iから減算してShamir秘密分散値[b]iを計算する。Shamir秘密分散値[b]iは、公開部１４へ送られる。Shamir秘密分散では、分散値同士の加減算は各パーティが個別にシェア同士を加減算することで実現される。そのため、[b]i=[r]i-[a]iによりShamir秘密分散値[b]iを計算することができる。
【００３０】
ステップＳ１４において、少なくともn-(k-1)台の分散値変換装置pi（∈P'）の公開部１４は、他のk-1台の分散値変換装置pj（j≠i）からk-1個のShamir秘密分散値[b]jを受信し、k個のShamir秘密分散値[b]を復元して値bを得る。値bは、再分散部１５へ送られる。公開部１４は、公開値を生成しても、準公開値を生成してもよい。n台の分散値変換装置piが値bを得ると、公開値bとなる。n-(k-1)台の分散値変換装置piが値bを得、他のk-1台の分散値変換装置pjが0を保持すると、準公開値〔b〕となる。公開部１４は、復元の際に、改ざん検知が可能な秘密公開方法を用いるとよい。改ざん検知が可能な秘密公開方法は、例えば下記参考文献２に記載の方法がある。
〔参考文献２〕I. Damgard, J. B. Nielsen, “Scalable and Unconditionally Secure Multiparty Computation”, CRYPTO 2007, vol. 4622 of Lecture Notes in Computer Science, pp. 572-590, 2007.
【００３１】
また、以下のようにして値bを復元しても改ざん検知が可能である。k-1台の分散値変換装置p1,…,pk-1は、Shamir秘密分散値[b]1,…,[b]k-1を分散値変換装置p0へ送信する。n-k台の分散値変換装置pk,…,pn-1は、Shamir秘密分散値[b]k,…,[b]n-1からチェックサムck,…,cn-1を計算し、そのチェックサムck,…,cn-1を分散値変換装置p0へ送信する。分散値変換装置p0は、k個のShamir秘密分散値[b]0,…,[b]k-1からn-k個のShamir秘密分散値[b]k,…,[b]n-1を復旧し、その秘密分散値[b]k,…,[b]n-1からチェックサムc'k,…,c'n-1をそれぞれ計算する。分散値変換装置p0は、チェックサムck,…,cn-1とチェックサムc'k,…,c'n-1とがすべて一致する場合に、k個のShamir秘密分散値[b]0,…,[b]k-1から値bを復元する。
【００３２】
ステップＳ１５において、n台の分散値変換装置piの再分散部１５は、値bを用いて複製型秘密分散値{b}を生成する。複製型秘密分散値{b}は、復元部１６へ送られる。再分散部１５は、以下のようにして、オフライン処理により複製型秘密分散値{b}を生成することができる。n-(k-1)台の分散値変換装置pi（∈P'）は、値bと0をサブシェアとして複製型秘密分散値{b}i=(b, 0)を生成する。残りの(k-1)台の分散値変換装置pj（∈P”≠P'）は、0の組をサブシェアとして複製型秘密分散値{b}i=(0, 0)を生成する。
【００３３】
ステップＳ１６において、n台の分散値変換装置piの復元部１６は、複製型秘密分散値{r}iから複製型秘密分散値{b}iを減算して情報aの複製型秘密分散値{a}iを生成する。複製型秘密分散値{a}iは、出力部１７へ送られる。複製型秘密分散では、分散値同士の加減算は、各パーティが個別にサブシェア同士を加減算することで実現される。例えば、{r}i=(rα, rβ)とし、{b}i=(bα, bβ)iとし、{a}i={r}i-{b}i=(rα-bα, rβ-bβ)により、オフライン処理で複製型秘密分散値{a}iを計算することができる。
【００３４】
ステップＳ１７において、n台の分散値変換装置piの出力部１７から変換後の複製型秘密分散値{a}iが出力される。
【００３５】
本形態の分散値変換システムおよび方法は、すべての処理ステップが、改ざんのおそれがないオフライン処理、もしくは改ざん検知が可能な処理手続きにより実行することができる。具体的には、乱数生成部１１、変換部１２、秘匿化部１３、再分散部１５、および復元部１６は、オフライン処理とすることができる。また、公開部１４は、改ざん検知が可能な秘密公開方法を用いることができる。そのため、本形態の分散値変換方法は全体として改ざん検知が可能なように構成することができる。
【００３６】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００３７】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００３８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３９】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４２】
１  分散値変換装置
２  通信網
１０  入力部
１１  乱数生成部
１２  変換部
１３  秘匿化部
１４  公開部
１５  再分散部
１６  復元部
１７  出力部
【要約】
【課題】Shamir秘密分散の分散値を複製型秘密分散の分散値へ変換する。
【解決手段】変換部１２は、乱数rの複製型秘密分散値{r}をShamir秘密分散値[r]へ変換する。秘匿化部１３は、情報aのShamir秘密分散値[a]をShamir秘密分散値[r]から減算してShamir秘密分散値[b]を計算する。公開部１４は、Shamir秘密分散値[b]を復元して値bを生成する。再分散部１５は、値bの複製型秘密分散値{b}を生成する。復元部１６は、複製型秘密分散値{r}から複製型秘密分散値{b}を減算して情報aの複製型秘密分散値{a}を生成する。
【選択図】図２【図１】
0005872084.tif 000003
【図２】
0005872084.tif 000004
【図３】
0005872084.tif 000005