(57)【要約】  シェア生成装置は、Ｎ個のシードｓ０，…，ｓＮ−１を得、平文ｘ∈Ｆｍおよび関数値ｅの関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍを得、要素ｙｉとｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを含む情報を、秘密分散における平文ｘのシェアＳＳｉとして得て出力する。ただし、関数値ｙはｍ＝ｍ（０）＋…＋ｍ（Ｎ−１）を満たす要素ｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）によって表現される。
2019039380.tif 000002
【特許請求の範囲】
【請求項１】
Ｎが２以上の整数であり、ｍが１以上の整数であり、ｍ（ｉ）が０以上の整数であり、ｉ＝０，…，Ｎ−１であり、Ｐが関数であり、前記関数Ｐの値域がｍ個の体Ｆの元の列を要素とする集合Ｆｍに属し、
Ｎ個のシードｓ０，…，ｓＮ−１を得るシード生成部と、
Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍが前記シードｓ０，…，ｓＮ−１の関数値であり、ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍが前記関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍの関数値であり、平文ｘ∈Ｆｍおよび前記関数値ｅの関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍを得る演算部と、
前記関数値ｙがｍ＝ｍ（０）＋…＋ｍ（Ｎ−１）を満たす要素ｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）によって表現され、要素ｙｉ∈Ｆｍ（ｉ）とｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の前記シードｓｄとを含む情報を、秘密分散における前記平文ｘのシェアＳＳｉとして得て出力するシェア生成部と、
を有するシェア生成装置。
【請求項２】
請求項１のシェア生成装置であって、
ｖが１以上の整数であり、ｃｅｉｌが天井関数であり、前記要素ｙｉがｍ（ｉ）個のサブ要素（ｙｉ）０，…，（ｙｉ）ｍ（ｉ）−１∈Ｆに分割でき、ｍ’（ｉ）がｃｅｉｌ（ｍ（ｉ）／ｖ）であり、（ｙ’ｉ）ｊが集合Ｆｖに属する（（ｙｉ）ｖｊ，（ｙｉ）ｖｊ＋１，…，（ｙｉ）ｖ（ｊ＋１）−１）∈Ｆｖであり、
前記集合Ｆｖに属するＮ個の任意値ｒ０，…，ｒＮ−１∈Ｆｖを得る任意値生成部と、
チェックサムｃｉ＝Σ０≦ｊ＜ｍ’（ｉ）−１｛（ｙ’ｉ）ｊ ｒｉｊ＋１｝＋（ｙ’ｉ）ｍ’（ｉ）−１ ｒｉｍ’（ｉ）＋１∈Ｆｖを得るチェックサム生成部と、を有し、
前記シェア生成部が生成する前記シェアＳＳｉは、さらにｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の前記任意値ｒｄと前記チェックサムｃｉ−１ ｍｏｄ Ｎとを含む、シェア生成装置。
【請求項３】
請求項１または２のシェア生成装置であって、
前記シェアＳＳ０，…，ＳＳＮ−１の総データ量は、前記平文ｘのデータ量のＮ倍未満である、シェア生成装置。
【請求項４】
請求項１から３の何れかに記載のシェア生成装置であって、
前記関数値ｅはｅ＝Σ０≦ｉ＜ＮＰ（ｓｉ）∈Ｆｍであり、前記関数値ｙはｙ＝ｘ−ｅ∈Ｆｍである、シェア生成装置。
【請求項５】
Ｎ個のシェア変換装置Ａ０，…，ＡＮ−１に含まれるシェア変換装置Ａｉであって、
Ｎが２以上の整数であり、ｍが１以上の整数であり、ｍ（ｉ）が０以上の整数であり、ｉ＝０，…，Ｎ−１であり、ｕ＝０，…，Ｎ−１であり、Ｐが関数であり、前記関数Ｐの値域がｍ個の体Ｆの元の列を要素とする集合Ｆｍに属し、
ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄと集合Ｆｍ（ｉ）に属する要素ｙｉ∈Ｆｍ（ｉ）とを含むシェアＳＳｉを受け付ける第１入力部と、
他のシェア変換装置Ａｉ−１ ｍｏｄ Ｎとの間で任意値ｔｉ∈Ｆｍ（ｉ）を共有する共有部と、
前記任意値ｔｉを前記シェア変換装置Ａｉ−１ ｍｏｄ Ｎのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎとしてシャミア秘密分散法に則って前記要素ｙｉを秘密分散することで各シェア変換装置Ａｕのシェア［ｙｉ］ｕ∈Ｆｍ（ｉ）を得て出力する秘密分散部と、
シェア［ｙｄ］ｉを受け付ける第２入力部と、
前記シードｓｄの関数値Ｐ（ｓｄ）∈Ｆｍを得る演算部と、
Ｎ個のシードｓ０，…，ｓＮ−１の関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）に対する関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍのシェアである、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の前記関数値Ｐ（ｓｄ）の集合ＳＥＴｉを、シャミア秘密分散法に則った前記関数値ｅのシェア［ｅ］ｉに変換するシャミア変換部と、
シェア［ｙ０］ｉ，…，［ｙＮ−１］ｉによって表現されるシェア［ｙ］ｉが平文ｘおよび前記関数値ｅに対する関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍのシェアであり、前記シェア［ｙ］ｉおよび前記シェア［ｅ］ｉを用いた秘密計算により、シャミア秘密分散法に則ったｘ＝ｇ−１（ｙ，ｅ）のシェア［ｘ］ｉを得る第１シェア生成部と、
を有するシェア変換装置。
【請求項６】
請求項５のシェア変換装置であって、
ｖが１以上の整数であり、ｃｅｉｌが天井関数であり、前記要素ｙｄがｍ（ｄ）個のサブ要素（ｙｄ）０，…，（ｙｉ）ｍ（ｄ）−１に分割でき、ｍ’（ｄ）がｃｅｉｌ（ｍ（ｄ）／ｖ）であり、（ｙ’ｄ）ｊが集合Ｆｖに属する（（ｙｄ）ｖｊ，（ｙｄ）ｖｊ＋１，…，（ｙｄ）ｖ（ｊ＋１）−１）∈Ｆｖであり、
前記第１入力部が受け付ける前記シェアＳＳｉは、さらに集合Ｆｖに属するｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の任意値ｒｄ∈Ｆｖとチェックサムｃｉ−１ ｍｏｄ Ｎ∈Ｆｖとを含み、
前記任意値ｒｄおよび前記シェア［ｙｄ］ｉを用いた秘密計算により、シャミア秘密分散法に則ったチェックサムｃｄ＝Σ０≦ｊ＜ｍ’（ｄ）−１｛（ｙ’ｄ）ｊ ｒｄｊ＋１｝＋（ｙ’ｄ）ｍ’（ｄ）−１ ｒｄｍ’（ｄ）＋１∈Ｆｖのシェア［ｃｄ］ｉを得る第２シェア生成部と、
前記シェア［ｃｄ］ｉを他のシェア変換装置Ａｄ＋１ ｍｏｄ Ｎに対して出力する第２出力部と、
シェア［ｃｉ−１ ｍｏｄ Ｎ］ｄを受け付ける第２入力部と、
前記チェックサムｃｉ−１ ｍｏｄ Ｎと前記シェア［ｃｉ−１ ｍｏｄ Ｎ］ｄとが正しい関係にあるかを検証する検証部と、
を有するシェア変換装置。
【請求項７】
請求項５または６のシェア変換装置であって、
前記シェアＳＳ０，…，ＳＳＮ−１の総データ量は、前記平文ｘのデータ量のＮ倍未満である、シェア変換装置。
【請求項８】
請求項５から７の何れかのシェア変換装置であって、
前記関数値ｅはｅ＝Σ０≦ｉ＜ＮＰ（ｓｉ）∈Ｆｍであり、前記関数値ｙはｙ＝ｘ−ｅ∈Ｆｍである、シェア変換装置。
【請求項９】
Ｎが２以上の整数であり、ｍが１以上の整数であり、ｍ（ｉ）が０以上の整数であり、ｉ＝０，…，Ｎ−１であり、ｕ＝０，…，Ｎ−１であり、Ｐが関数であり、前記関数Ｐの値域がｍ個の体Ｆの元の列を要素とする集合Ｆｍに属し、
シェア生成装置とＮ個のシェア変換装置Ａ０，…，ＡＮ−１とを有し、
前記シェア生成装置は、
Ｎ個のシードｓ０，…，ｓＮ−１を得るシード生成部と、
Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍが前記シードｓ０，…，ｓＮ−１の関数値であり、ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍが前記関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍの関数値であり、平文ｘ∈Ｆｍおよび前記関数値ｅの関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍを得る演算部と、
前記関数値ｙがｍ＝ｍ（０）＋…＋ｍ（Ｎ−１）を満たす要素ｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）によって表現され、要素ｙｉ∈Ｆｍ（ｉ）とｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の前記シードｓｄとを含む情報を、秘密分散における前記平文ｘのシェアＳＳｉとして得て出力するシェア生成部と、を含み、
前記シェア変換装置Ａ０，…，ＡＮ−１に含まれるシェア変換装置Ａｉは、
前記シェアＳＳｉを受け付ける第１入力部と、
他のシェア変換装置Ａｉ−１ ｍｏｄ Ｎとの間で任意値ｔｉ∈Ｆｍ（ｉ）を共有する共有部と、
前記任意値ｔｉを前記シェア変換装置Ａｉ−１ ｍｏｄ Ｎのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎとしてシャミア秘密分散法に則って前記要素ｙｉを秘密分散することで各シェア変換装置Ａｕのシェア［ｙｉ］ｕ∈Ｆｍ（ｉ）を得て出力する秘密分散部と、
前記他のシェア変換装置Ａｄから出力されたシェア［ｙｄ］ｉを受け付ける第２入力部と、
前記シードｓｄの関数値Ｐ（ｓｄ）∈Ｆｍを得る演算部と、
Ｎ個のシードｓ０，…，ｓＮ−１の関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）に対する関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍのシェアである、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の前記関数値Ｐ（ｓｄ）の集合ＳＥＴｉを、シャミア秘密分散法に則った前記関数値ｅのシェア［ｅ］ｉに変換するシャミア変換部と、
シェア［ｙ０］ｉ，…，［ｙＮ−１］ｉによって表現されるシェア［ｙ］ｉが平文ｘおよび前記関数値ｅに対する関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍのシェアであり、前記シェア［ｙ］ｉおよび前記シェア［ｅ］ｉを用いた秘密計算により、シャミア秘密分散法に則ったｘ＝ｇ−１（ｙ，ｅ）のシェア［ｘ］ｉを得る第１シェア生成部と、を含む、秘密計算システム。
【請求項１０】
Ｎが２以上の整数であり、ｍが１以上の整数であり、ｍ（ｉ）が０以上の整数であり、ｉ＝０，…，Ｎ−１であり、Ｐが関数であり、前記関数Ｐの値域がｍ個の体Ｆの元の列を要素とする集合Ｆｍに属し、
シード生成部が、Ｎ個のシードｓ０，…，ｓＮ−１を得るシード生成ステップと、
Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍが前記シードｓ０，…，ｓＮ−１の関数値であり、ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍが前記関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍの関数値であり、演算部が、平文ｘ∈Ｆｍおよび前記関数値ｅの関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍを得る演算ステップと、
前記関数値ｙがｍ＝ｍ（０）＋…＋ｍ（Ｎ−１）を満たす要素ｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）によって表現され、シェア生成部が、要素ｙｉ∈Ｆｍ（ｉ）とｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の前記シードｓｄとを含む情報を、秘密分散における前記平文ｘのシェアＳＳｉとして得て出力するシェア生成ステップと、
を有するシェア生成方法。
【請求項１１】
Ｎ個のシェア変換装置Ａ０，…，ＡＮ−１に含まれるシェア変換装置Ａｉのシェア変換方法であって、
Ｎが２以上の整数であり、ｍが１以上の整数であり、ｍ（ｉ）が０以上の整数であり、ｉ＝０，…，Ｎ−１であり、ｕ＝０，…，Ｎ−１であり、Ｐが関数であり、前記関数Ｐの値域がｍ個の体Ｆの元の列を要素とする集合Ｆｍに属し、
第１入力部が、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄと集合Ｆｍ（ｉ）に属する要素ｙｉ∈Ｆｍ（ｉ）とを含むシェアＳＳｉを受け付ける第１入力ステップと、
共有部が、他のシェア変換装置Ａｉ−１ ｍｏｄ Ｎとの間で任意値ｔｉ∈Ｆｍ（ｉ）を共有する共有ステップと、
秘密分散部が、前記任意値ｔｉを前記シェア変換装置Ａｉ−１ ｍｏｄ Ｎのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎとしてシャミア秘密分散法に則って前記要素ｙｉを秘密分散することで各シェア変換装置Ａｕのシェア［ｙｉ］ｕ∈Ｆｍ（ｉ）を得て出力する秘密分散ステップと、
第２入力部が、シェア［ｙｄ］ｉを受け付ける第２入力ステップと、
演算部が、前記シードｓｄの関数値Ｐ（ｓｄ）∈Ｆｍを得る演算ステップと、
シャミア変換部が、Ｎ個のシードｓ０，…，ｓＮ−１の関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）に対する関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍのシェアである、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の前記関数値Ｐ（ｓｄ）の集合ＳＥＴｉを、シャミア秘密分散法に則った前記関数値ｅのシェア［ｅ］ｉに変換するシャミア変換ステップと、
シェア［ｙ０］ｉ，…，［ｙＮ−１］ｉによって表現されるシェア［ｙ］ｉが平文ｘおよび前記関数値ｅに対する関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍのシェアであり、第１シェア生成部が、前記シェア［ｙ］ｉおよび前記シェア［ｅ］ｉを用いた秘密計算により、シャミア秘密分散法に則ったｘ＝ｇ−１（ｙ，ｅ）のシェア［ｘ］ｉを得る第１シェア生成ステップと、
を有するシェア変換方法。
【請求項１２】
請求項１から４の何れかのシェア生成装置、または請求項５から８の何れかのシェア変換装置としてコンピュータを機能させるためのプログラム。
【請求項１３】
請求項１から４の何れかのシェア生成装置、または請求項５から８の何れかのシェア変換装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に秘密計算技術に関する。
【背景技術】
【０００２】
秘密分散方式の一つにシャミア（Shamir）秘密分散法がある（例えば、非特許文献１等参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】A. Shamir, "How to Share a Secret", Communications of the ACM, November 1979, Volume 22, Number 11, pp.612-613.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
秘密計算装置は、シャミア秘密分散法に則って得られたシェアをそのまま用いて秘密計算を行うことができる。しかし、このシェアがＮ個の秘密計算装置に秘密分散される場合、シェアの総データ量は平文のデータ量のＮ倍のオーダーになってしまう。そのため、このシェアをそのままＮ個の秘密計算装置に送信したのでは、総通信データ量も平文のデータ量のＮ倍のオーダーとなってしまう。【０００５】
本発明の目的は、シャミア秘密分散法に則ったシェアよりも総通信データ量が小さく、かつシャミア秘密分散法に則ったシェアに変換可能なシェアを生成する技術、またはシャミア秘密分散法に則ったシェアよりも総通信データ量が小さいシェアをシャミア秘密分散法に則ったシェアに変換する技術を提供することである。
【課題を解決するための手段】
【０００６】
シェア生成装置は、Ｎ個のシードｓ０，…，ｓＮ−１を得、平文ｘ∈Ｆｍおよび関数値ｅの関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍを得、要素ｙｉ∈Ｆｍ（ｉ）とｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを含む情報を、秘密分散における平文ｘのシェアＳＳｉとして得て出力する。ただし、Ｎが２以上の整数であり、ｍが１以上の整数であり、ｍ（ｉ）が０以上の整数であり、ｉ＝０，…，Ｎ−１であり、Ｐが関数であり、関数Ｐの値域がｍ個の体Ｆの元の列を要素とする集合Ｆｍに属し、Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍがシードｓ０，…，ｓＮ−１の関数値であり、ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍが関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍの関数値であり、関数値ｙがｍ＝ｍ（０）＋…＋ｍ（Ｎ−１）を満たす要素ｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）によって表現される。【０００７】
Ｎ個のシェア変換装置Ａ０，…，ＡＮ−１に含まれる各シェア変換装置ＡｉはシェアＳＳｉを受け付け、他のシェア変換装置Ａｉ−１ ｍｏｄ Ｎとの間で任意値ｔｉ∈Ｆｍ（ｉ）を共有し、任意値ｔｉをシェア変換装置Ａｉ−１ ｍｏｄ Ｎのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎとしてシャミア秘密分散法に則って要素ｙｉを秘密分散することで各シェア変換装置Ａｕのシェア［ｙｉ］ｕ∈Ｆｍ（ｉ）を得て出力し、シェア［ｙｄ］ｉを受け付け、シードｓｄの関数値Ｐ（ｓｄ）∈Ｆｍを得、Ｎ個のシードｓ０，…，ｓＮ−１の関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）に対する関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍのシェアである、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについての関数値Ｐ（ｓｄ）の集合ＳＥＴｉを、シャミア秘密分散法に則った関数値ｅのシェア［ｅ］ｉに変換し、シェア［ｙ０］ｉ，…，［ｙＮ−１］ｉによって表現されるシェア［ｙ］ｉおよびシェア［ｅ］ｉを用いた秘密計算により、シャミア秘密分散法に則ったｘ＝ｇ−１（ｙ，ｅ）のシェア［ｘ］ｉを得る。ただし、ｕ＝０，…，Ｎ−１であり、シェア［ｙ］ｉは平文ｘおよび関数値ｅに対する関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍのシェアである。
【発明の効果】
【０００８】
シェア生成装置は、シャミア秘密分散法に則ったシェアよりも総通信データ量が小さく、かつシャミア秘密分散法に則ったシェアに変換可能なシェアを生成できる。シェア変換装置は、シャミア秘密分散法に則ったシェアよりも総通信データ量が小さいシェアをシャミア秘密分散法に則ったシェアに変換できる。
【図面の簡単な説明】
【０００９】
【図１】図１は実施形態の秘密計算システムの構成を例示したブロック図である。
【図２】図２は実施形態のシェア生成装置の機能構成を例示したブロック図である。
【図３】図３は実施形態のシェア変換装置の機能構成を例示したブロック図である。
【図４】図４は実施形態のシェア生成方法を説明するためのフロー図である。
【図５】図５は実施形態のシェア変換方法を説明するためのフロー図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照して本発明の実施形態を説明する。
［第１実施形態］
まず、第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の秘密計算システム１はシェア生成装置１１およびＮ個のシェア変換装置１２−Ａ０，…，１２−ＡＮ−１を有し、これらの装置はインターネット等のネットワークを通じて互いに通信可能である。ただし、Ｎは２以上の整数である。例えば、Ｎは３以上の整数である。Ｎの一例はＮ＝３である。なお、図１には１個のシェア生成装置１１を図示しているが、秘密計算システム１が複数個のシェア生成装置を有していてもよい。
【００１１】
図２に例示するように、本形態のシェア生成装置１１は、シード生成部１１１、演算部１１２、分割部１１３、シェア生成部１１６、通信部１１７、記憶部１１８、および制御部１１９を有し、制御部１１９の制御のもとで各処理を実行する。シェア生成装置１１の各処理部（処理を行う部位）から出力された情報は記憶部１１８に格納され、必要に応じて読み出されて他の処理部に入力される。
【００１２】
図３に例示するように、各シェア変換装置１２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）は、通信部１２０１−Ａｉ、共有部１２０２−Ａｉ、秘密分散部１２０３−Ａｉ、秘密計算部１２０６−Ａｉ、演算部１２０７−Ａｉ、シャミア変換部１２０８−Ａｉ、シェア生成部１２０９−Ａｉ、記憶部１２１０−Ａｉ、および制御部１２１１−Ａｉを有し、制御部１２１１−Ａｉの制御のもとで各処理を実行する。シェア変換装置１２−Ａｉの各処理部から出力された情報は記憶部１２１０−Ａｉに格納され、必要に応じて読み出されて他の処理部に入力される。
【００１３】
＜シェア生成方法＞
図４を用い、本形態のシェア生成装置１１が行うシェア生成方法を説明する。なお、「シェア」とは秘密分散における断片を意味する。
まずシード生成部１１１（図２）は、Ｎ個のシードｓ０，…，ｓＮ−１を得て出力する。シードｓ０，…，ｓＮ−１のデータ形式に限定はなく、どのような値をシードｓ０，…，ｓＮ−１としてもよい。各シードｓ０，…，ｓＮ−１の一例はｗ個の体Ｆの元の列を要素とする集合Ｆｗの元である（ｓ０，…，ｓＮ−１∈Ｆｗ）。ただし、α∈βはαがβの要素であることを意味する。ｗは１以上の整数である。ｗ＝１の場合、Ｆｗは体Ｆである。体Ｆの例は素数ｐを法とした剰余（任意のαに対するα  ｍｏｄ  ｐ）からなる集合であり、この場合の体Ｆでの演算結果は素数ｐを法とした剰余として得られる。ｐ≧３であり、例えばｐ＝２６１−１である。シードｓｉ（ただし、ｉ＝０，…，Ｎ−１）は任意値であってもよいし、他の処理で得られた出力値であってもよい。「任意値」は乱数（擬似乱数または真正乱数）であってもよいし、予め設定された複数の値から選択された値であってもよいし、他の処理で得られた値であってもよい。例えば、シード生成部１１１は、Ｎ個の乱数を生成し、それらをシードｓ０，…，ｓＮ−１として出力する（ステップＳ１１１）。
【００１４】
秘密分散対象の平文ｘ∈Ｆｍおよびシード生成部１１１から出力されたシードｓ０，…，ｓＮ−１は演算部１１２に入力される。ただし、ｍは１以上の整数である。例えば、ｍは２以上の整数または３以上の整数である。演算部１１２は、平文ｘ∈Ｆｍおよび関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍの関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍを得て出力する。ただし、Ｐは関数である。関数Ｐの値域はｍ個の体Ｆの元の列を要素とする集合Ｆｍに属する。集合Ｆｍの一例はｍ個の体Ｆの元を要素とするｍ次元ベクトルの集合である。関数Ｐの定義域はどのようなものであってもよいが、例えば、関数Ｐの定義域は集合Ｆｗに属する。例えばｗ＜ｍである。関数Ｐの例は擬似乱数生成関数である。Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍはシードｓ０，…，ｓＮ−１の関数値（例えば、擬似乱数）である。ｇ：Ｆｍ×２→Ｆｍは２個の集合Ｆｍの元を１個の集合Ｆｍの元に移す線形関数（線形性を持つ関数）である。例えば、ｙ＝ｘ−ｅ∈Ｆｍである。しかし、これは本発明を限定しない。例えばｘ−ｅの一部または全部の項に定数が乗じられた式によって表される演算によって得られる値をｙとしてもよいし、ｘ−ｅの一部または全部の項が逆元に置換された式によって表される演算によって得られる値をｙとしてもよいし、ｘ−ｅの一部または全部の項を逆元に置換し、さらに一部または全部の項に定数が乗じられた式によって表される演算によって得られる値をｙとしてもよいし、さらに定数項が加えられた式によって表される演算によって得られる値をｙとしてもよい。関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））は関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）∈Ｆｍの関数値である。ｆ：Ｆｍ×ｎ→Ｆｍはｎ個の集合Ｆｍの元を１個の集合Ｆｍの元に移す線形関数である。例えば、ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））＝Σ０≦ｉ＜ＮＰ（ｓｉ）＝Ｐ（ｓ０）＋…＋Ｐ（ｓＮ−１）∈Ｆｍである。しかし、これは本発明を限定しない。例えば、Ｐ（ｓ０）＋…＋Ｐ（ｓＮ−１）の一部または全部の項に定数が乗じられた式によって表される演算によって得られる値をｅとしてもよいし、Ｐ（ｓ０）＋…＋Ｐ（ｓＮ−１）の一部または全部の項が逆元に置換された式によって表される演算によって得られる値をｅとしてもよいし、Ｐ（ｓ０）＋…＋Ｐ（ｓＮ−１）の一部または全部の項を逆元に置換し、さらに一部または全部の項に定数が乗じられた式によって表される演算によって得られる値をｅとしてもよいし、さらに定数項が加えられた式によって表される演算によって得られる値をｅとしてもよい（ステップＳ１１２）。
【００１５】
関数値ｙ∈Ｆｍは分割部１１３に入力される。分割部１１３は、関数値ｙをＮ個の要素ｙ０，…，ｙＮ−１に分割して出力する。ただし、ｉ＝０，…，Ｎ−１についてｙｉ∈Ｆｍ（ｉ）であり、ｍ（ｉ）が０以上の整数であり（例えば、ｍ（ｉ）は１以上の整数であり）、ｍ≧Ｎであり、ｍ＝ｍ（０）＋…＋ｍ（Ｎ−１）を満たす。例えば、ｍがＮの倍数である場合にはｍ（０）＝…＝ｍ（Ｎ−１）＝ｍ／Ｎとしてもよい。しかし、ｍがＮの倍数であるか否かにかかわらず、ｍ（０），…，ｍ（Ｎ−１）がすべて同一でなくてもよい。例えば、ｍ（０），…，ｍ（Ｎ−１）の少なくとも一部が０であってもよい。ただしγ∈Ｆ０はヌル値を表す。ｍ（ｉ）＝０の場合、ｙｉ∈Ｆｍ（ｉ）はヌル値である。関数値ｙは要素ｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）（例えば、ｙ０，…，ｙＮ−１の列）によって表現される。例えば、関数値ｙはｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）を並べた列ｙ０｜…｜ｙＮ−１で表現される。ｍ＝１の場合、ｍ（０），…，ｍ（Ｎ−１）の何れか１個のみが１であり、他はすべて０である。このような場合、分割部１１３は関数値ｙを分割する必要はなく、要素ｙ０，…，ｙＮ−１の何れか１個の要素を関数値ｙとし、残りの要素を全てヌル値として出力する（ステップＳ１１３）。
【００１６】
分割部１１３から出力された要素ｙ０，…，ｙＮ−１およびシード生成部１１１から出力されたシードｓ０，…，ｓＮ−１はシェア生成部１１６に入力される。シェア生成部１１６は、要素ｙｉとｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを各シェア変換装置１２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）に割り当て、要素ｙｉとｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを含む情報を、秘密分散における平文ｘのシェアＳＳｉとして得て出力する。なお、ｉ≠０かつｉ≠Ｎ−１の場合、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄはシードｓ０，…，ｓｉ−１，ｓｉ＋１，…，ｓＮ−１である。ｉ＝０の場合、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄはシードｓ１，…，ｓＮ−１である。ｉ＝Ｎ−１の場合、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄはシードｓ０，…，ｓＮ−２である。各シェアＳＳｉは各シェア変換装置１２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）のシェアである。各シェアＳＳｉは他の情報を含んでもよいが、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについての要素ｙｄおよびシードｓｉを含まない。なお、ヌル値である要素ｙｉ∈Ｆ０とＮ−１個のシードｓｄとを含む情報とは、要素ｙｉがヌル値であることを示し、かつＮ−１個のシードｓｄを含む情報を意味する。ヌル値である要素ｙｉ∈Ｆ０とＮ−１個のシードｓｄとを含む情報は、Ｎ−１個のシードｓｄを含むが実質的には要素ｙｉを含まない。シードｓ１，…，ｓＮ−１のサイズおよびＮはｍに依存しない。平文のデータサイズｍに関する総シェアサイズのオーダーは、（２，Ｎ）−シャミア秘密分散ではＯ（Ｎｍ）となるところ、本形態ではＯ（ｍ）で済む。個々のシェアのサイズはＯ（ｍ／Ｎ）である。例えば、シェアＳＳ０，…，ＳＳＮ−１の総データ量は平文ｘのデータ量のＮ倍未満である。例えば、各シェアＳＳｉのデータ量は平文ｘのデータ量未満である（ステップＳ１１６）。
【００１７】
シェア生成部１１６から出力された各シェアＳＳｉは通信部１１７に入力される。通信部１１７は、各シェアＳＳｉを各シェア変換装置１２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）に対して出力する。出力された各シェアＳＳｉはネットワークを通じて各シェア変換装置１２−Ａｉに送信される。すなわち、シェアＳＳ０はシェア変換装置１２−Ａ０に送信され、シェアＳＳ１はシェア変換装置１２−Ａ１に送信され、・・・、シェアＳＳＮ−１はシェア変換装置１２−ＡＮ−１に送信される（ステップＳ１１７）。
【００１８】
＜シェア変換方法＞
図５を用い、本形態の各シェア変換装置１２−Ａｉが行うシェア変換方法を説明する。
シェア生成装置１１から出力された要素ｙｉとｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを含むシェアＳＳｉはシェア変換装置１２−Ａｉ（図３）の通信部１２０１−Ａｉ（第１入力部）に受信される（受け付けられる）。受信されたシェアＳＳｉは記憶部１２１０−Ａｉに格納される（ステップＳ１２１０−Ａｉ）。
【００１９】
共有部１２０２−Ａｉは、他のシェア変換装置１２−Ａｉ−１ ｍｏｄ Ｎの共有部１２０２−Ａｉ−１ ｍｏｄ Ｎとの間で任意値ｔｉ∈Ｆｍ（ｉ）を共有する。すなわち、共有部１２０２−Ａｉと共有部１２０２−Ａｉ−１ ｍｏｄ Ｎとは同一の任意値ｔｉを得る。共有部１２０２−Ａｉから任意値ｔｉまたは任意値ｔｉを特定する情報を共有部１２０２−Ａｉ−１ ｍｏｄ Ｎに送信して両者で任意値ｔｉが共有されてもよいし、共有部１２０２−Ａｉ−１ ｍｏｄ Ｎから任意値ｔｉまたは任意値ｔｉを特定する情報を共有部１２０２−Ａｉに送信して両者で任意値ｔｉが共有されてもよいし、共有部１２０２−Ａｉと共有部１２０２−Ａｉ−１ ｍｏｄ Ｎとで共有シード値を共有しておき、両者が共有シード値を用いた同一の処理を実行することで任意値ｔｉが共有されてもよい。任意値ｔｉは、乱数（擬似乱数または真正乱数）であってもよいし、他の処理で得られた値であってもよいし、予め定められた複数の値から選択された値であってもよい。任意値ｔｉ∈Ｆｍ（ｉ）の共有は、ステップＳ１２１０−Ａｉが実行されたことを契機として行われてもよいし、他の共有部１２０２−Ａｉ−１ ｍｏｄ Ｎからの要求を契機として行われてもよいし、その他の契機で行われてもよいし、予め行われていてもよい。共有部１２０２−Ａｉは得た任意値ｔｉを出力する。要素ｙｉがヌル値である場合には任意値ｔｉもヌル値に設定される（ステップＳ１２０２−Ａｉ）。
【００２０】
シェアＳＳｉに含まれた要素ｙｉおよび共有部１２０２−Ａｉから出力された任意値ｔｉは秘密分散部１２０３−Ａｉに入力される。秘密分散部１２０３−Ａｉは、シャミア（Shamir）秘密分散法に則って要素ｙｉを秘密分散することで各シェア変換装置１２−Ａｕ（ただし、ｕ＝０，…，Ｎ−１）のシェア［ｙｉ］ｕ∈Ｆｍ（ｉ）（Shamirシェア）を得て出力する。ただし、任意値ｔｉをシェア変換装置１２−Ａｉ−１ ｍｏｄ Ｎのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎとする。実施形態のシャミア秘密分散法は2-out-of-Nしきい値分散方式であり、任意の相違なる２個のシェアが与えられれば平文を復元できるが、任意の１個のシェア情報が与えられても平文の情報はまったく得られない。2-out-of-Nしきい値分散方式の場合、秘密分散対象の要素ｙｉと１つのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎ＝ｔｉとが定まれば他のシェアを求めることができる。例えば、秘密分散部１２０３−Ａｉは、任意値ｔｉをシェア変換装置１２−Ａｉ−１ ｍｏｄ Ｎのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎとし、ラグランジェ(Lagrange)の補間公式を用いて要素ｙｉとシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎ＝ｔｉと他のシェア［ｙｉ］ｕ’∈Ｆｍ（ｉ）（ただし、ｕ’∈｛０，…，Ｎ−１｝かつｕ’≠ｉ−１ ｍｏｄ Ｎ）との間に成り立つ方程式を特定し（例えば、当該方程式の各項の係数を特定し）、それを解くことで他のシェア［ｙｉ］ｕ’∈Ｆｍ（ｉ）を生成する。通信部１２０１−Ａｉ（第１出力部）は秘密分散部１２０３−Ａｉで得たシェア［ｙｉ］ｄを他のＮ−１個のシェア変換装置１２−Ａｄ（ただし、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉ）に対して出力（送信）する。ただし、シェア変換装置１２−Ａｉとシェア変換装置１２−Ａｉ−１ ｍｏｄ Ｎとは既にシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎ＝ｔｉを共有しているため（ステップＳ１２０２−Ａｉ）、シェア変換装置１２−Ａｉ−１ ｍｏｄ Ｎへのシェア［ｙｉ］ｉ−１ ｍｏｄ Ｎ＝ｔｉの更なる送信が省略されてもよい。要素ｙｉがヌル値である場合にはシェア［ｙｉ］ｕもヌル値に設定される。通信部１２０１−Ａｉ（第２入力部）は、同様に他のシェア変換装置１２−Ａｄから出力（送信）されたシェア［ｙｄ］ｉを受信する（受け付ける）（ステップＳ１２０３−Ａｉ）。
【００２１】
秘密分散部１２０３−Ａｉから出力されたシェア変換装置１２−Ａｉのシェア［ｙｉ］ｉおよび他のシェア変換装置１２−Ａｄ（ただし、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉ）から送信されたシェア［ｙｄ］ｉは秘密計算部１２０６−Ａｉ（第１秘密計算部）に入力される。秘密計算部１２０６−Ａｉは、公知の秘密計算によってシェア［ｙ０］ｉ，…，［ｙＮ−１］ｉを結合（連結）してシェア［ｙ］ｉ∈Ｆｍを得て出力する。シェア［ｙ］ｉはシャミア秘密分散法に則った関数値ｙのシェアである。関数値ｙはＮ個の要素ｙ０，…，ｙＮ−１を結合したものである。例えば、ｙ０∈Ｆｍ（０），…，ｙＮ−１∈Ｆｍ（Ｎ−１）を並べた列ｙ０｜…｜ｙＮ−１がｙである。秘密計算によって、シャミア秘密分散法に則ったシェア［ｙ０］ｉ，…，［ｙＮ−１］ｉを結合してシェア［ｙ］ｉ∈Ｆｍを得るには、例えばシェア［ｙ０］ｉ，…，［ｙＮ−１］ｉの列をシェア［ｙ］とすればよい。すなわち、シェア［ｙ］はシェア［ｙ０］ｉ∈Ｆｍ（０），…，［ｙＮ−１］ｉ∈Ｆｍ（Ｎ−１）によって表現される。例えば、シェア［ｙ０］ｉ，…，［ｙＮ−１］ｉを並べた列［ｙ０］ｉ｜…｜［ｙＮ−１］ｉがシェア［ｙ］である（ステップＳ１２０６−Ａｉ）。
【００２２】
シェアＳＳｉに含まれたＮ−１個のシードｓｄは演算部１２０７−Ａｉに入力される。演算部１２０７−Ａｉは、Ｎ−１個のシードｓｄのＮ−１個の関数値Ｐ（ｓｄ）∈Ｆｍ（例えば、擬似乱数）を得て出力する（ただし、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉ）。この演算に用いられる関数Ｐは、シェア生成装置１１の演算部１１２で関数値ｙを得るための関数Ｐと同一である。ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の関数値Ｐ（ｓｄ）の集合ＳＥＴｉ（すなわち、集合ＳＥＴｉはｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の関数値Ｐ（ｓｄ）を要素として持つ）は、Ｎ個のシードｓ０，…，ｓＮ−１の関数値Ｐ（ｓ０），…，Ｐ（ｓＮ−１）に対する関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））∈Ｆｍのシェアである。つまり、少なくとも２個の互いに異なる集合ＳＥＴｉ’およびＳＥＴｉ”（ただし、ｉ’，ｉ”∈｛０，…，Ｎ−１｝かつｉ’≠ｉ”）があれば、関数値ｅ＝ｆ（Ｐ（ｓ０），…，Ｐ（ｓＮ−１））を復元できる。すなわち、集合ＳＥＴｉは関数値ｅの（２，Ｎ）−複製秘密分散シェアである（ステップＳ１２０７−Ａｉ）。
【００２３】
ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の関数値Ｐ（ｓｄ）の集合ＳＥＴｉはシャミア変換部１２０８−Ａｉに入力される。シャミア変換部１２０８−Ａｉは、関数値ｅの（２，Ｎ）−複製秘密分散シェアである集合ＳＥＴｉを、公知のシャミア変換方法によって、シャミア秘密分散法に則った関数値ｅのシェア［ｅ］ｉに変換して出力する。（２，Ｎ）−複製秘密分散シェアをシャミア秘密分散法に則ったシェアに変換する方法としては、例えば、「Ronald Cramer, Ivan Damgard, Yuval Ishai: Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. TCC 2005: 342-362」（参考文献１）に記載された方法を例示できる（ステップＳ１２０８−Ａｉ）。
【００２４】
秘密計算部１２０６−Ａｉから出力されたシェア［ｙ］ｉおよびシャミア変換部１２０８−Ａｉから出力されたシェア［ｅ］ｉは、シェア生成部１２０９−Ａｉ（第１シェア生成部）に入力される。前述のように、シェア［ｙ］ｉは平文ｘおよび関数値ｅに対する関数値ｙ＝ｇ（ｘ，ｅ）∈Ｆｍのシャミア秘密分散法に則ったシェアである。ここでｙ＝ｇ（ｘ，ｅ）に対してｘ＝ｇ−１（ｙ，ｅ）∈Ｆｍを満たす関数をｇ−１：Ｆｍ×２→Ｆｍと定義する。例えば、ｙ＝ｘ−ｅの場合、ｘ＝ｙ＋ｅである。シェア生成部１２０９−Ａｉは、シェア［ｙ］ｉおよびシェア［ｅ］ｉを用いた秘密計算により、シャミア秘密分散法に則ったｘ＝ｇ−１（ｙ，ｅ）のシェア［ｘ］ｉ∈Ｆｍを得て出力する。例えば、ｘ＝ｙ＋ｅの場合、シェア生成部１２０９−Ａｉは、シェア［ｙ］ｉおよびシェア［ｅ］ｉを用いた秘密計算により、シェア［ｙ＋ｅ］ｉを得て出力する。シャミア秘密分散法に則ったシェアを用いた秘密計算は、例えば、「Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10」（参考文献２）に記載されている（ステップＳ１２０９−Ａｉ）。
【００２５】
＜本形態の特徴＞
シェア生成装置１１は、要素ｙｉ∈Ｆｍ（ｉ）およびｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄを含む情報をシェアＳＳｉとして各シェア変換装置１２−Ａｉに出力する。これにより、シャミア秘密分散法に則ったシェアよりも総通信データ量を小さくできる。各シェア変換装置１２−ＡｉはシェアＳＳｉをシャミア秘密分散法に則ったシェア［ｘ］ｉに変換できる。これにより、秘密計算を行うことができる。
【００２６】
［第２実施形態］
第２実施形態は第１実施形態の変形例である。本形態では、シェア生成の際にシェアに対応するチェックサムを生成し、シェア変換の際にチェックサムを用いてシェアを検証する。以下では、第１実施形態で既に説明した事項については第１実施形態と同じ参照番号を用い、説明を簡略化する場合がある。
【００２７】
＜構成＞
図１に例示するように、本形態の秘密計算システム２はシェア生成装置２１およびＮ個のシェア変換装置２２−Ａ０，…，２２−ＡＮ−１を有し、これらの装置はインターネット等のネットワークを通じて互いに通信可能である。図１には１個のシェア生成装置２１を図示しているが、秘密計算システム２が複数個のシェア生成装置を有していてもよい。
【００２８】
図２に例示するように、本形態のシェア生成装置２１は、シード生成部１１１、演算部１１２、分割部１１３、任意値生成部２１４、チェックサム生成部２１５、シェア生成部２１６、通信部１１７、記憶部１１８、および制御部１１９を有し、制御部１１９の制御のもとで各処理を実行する。各処理部から出力された情報は記憶部１１８に格納され、必要に応じて読み出されて他の処理部に入力される。
【００２９】
図３に例示するように、各シェア変換装置２２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）は、通信部１２０１−Ａｉ、共有部１２０２−Ａｉ、秘密分散部１２０３−Ａｉ、シェア生成部２２０４−Ａｉ、検証部２２０５−Ａｉ、秘密計算部１２０６−Ａｉ、演算部１２０７−Ａｉ、シャミア変換部１２０８−Ａｉ、シェア生成部１２０９−Ａｉ、記憶部１２１０−Ａｉ、および制御部１２１１−Ａｉを有し、制御部１２１１−Ａｉの制御のもとで各処理を実行する。各処理部から出力された情報は記憶部１２１０−Ａｉに格納され、必要に応じて読み出されて他の処理部に入力される。
【００３０】
＜シェア生成方法＞
図４を用い、シェア生成装置２１が行うシェア生成方法を説明する。まず、シェア生成装置１１に代えてシェア生成装置２１が、第１実施形態で説明したステップＳ１１１からＳ１１３の処理を実行する。
【００３１】
次に、任意値生成部２１４が、集合Ｆｖに属するＮ個の任意値ｒ０，…，ｒＮ−１∈Ｆｖを得て出力する。ただし、ｖは１以上の整数である。ｖがｍ以下である（例えば、ｖがｍよりも小さい）ほうがデータ量の削減効果が大きい。例えばｖ＝１である。集合Ｆｖの一例は体Ｆを基礎体とした拡大次数ｖの拡大体である。「任意値」は乱数（擬似乱数または真正乱数）であってもよいし、予め設定された複数の値から選択された値であってもよい。例えば、任意値生成部２１４は、Ｎ個の乱数を生成し、それらを任意値ｒ０，…，ｒＮ−１として出力する（ステップＳ２１４）。
【００３２】
分割部１１３から出力された要素ｙ０，…，ｙＮ−１および任意値生成部２１４から出力された任意値ｒ０，…，ｒＮ−１はチェックサム生成部２１５に入力される。ここで、各要素ｙｉ∈Ｆｍ（ｉ）はｍ（ｉ）個のサブ要素（ｙｉ）０，…，（ｙｉ）ｍ（ｉ）−１∈Ｆに分割可能である。例えば、各要素ｙｉはサブ要素（ｙｉ）０，…，（ｙｉ）ｍ（ｉ）−１を並べた列（ｙｉ）０｜…｜（ｙｉ）ｍ（ｉ）−１で表現される。また、ｍ’（ｉ）がｃｅｉｌ（ｍ（ｉ）／ｖ）であり、（ｙ’ｉ）ｊが集合Ｆｖに属する（（ｙｉ）ｖｊ，（ｙｉ）ｖｊ＋１，…，（ｙｉ）ｖ（ｊ＋１）−１）∈Ｆｖである。ただし、ｃｅｉｌは天井関数であり、ｍ’（ｉ）はｃｅｉｌ（ｍ（ｉ）／ｖ）（すなわち、ｍ’（ｉ）はｍ（ｉ）／ｖ以上の最小の整数）である。また、ｊ＝ｍ’（ｉ）−１について、（ｙ’ｉ）ｖ（ｍ’（ｉ）−１），（ｙｉ）ｖ（ｍ’（ｉ）−１）＋１，…，（ｙｉ）ｖｍ’（ｉ）−１がｖ個に満たない場合、（ｙ’ｉ）ｍ’（ｉ）−１＝（（ｙｉ）ｖ（ｍ’（ｉ）−１），（ｙｉ）ｖ（ｍ’（ｉ）−１）＋１，…，（ｙｉ）ｍ（ｉ）−１，０，…，０）∈Ｆｖとする。チェックサム生成部２１５は、要素ｙ０，…，ｙＮ−１および任意値ｒ０，…，ｒＮ−１を用い、各シェアＳＳｉに対応するチェックサムｃｉ＝Σ０≦ｊ＜ｍ’（ｉ）−１｛（ｙ’ｉ）ｊ ｒｉｊ＋１｝＋（ｙ’ｉ）ｍ’（ｉ）−１ｒｉｍ’（ｉ）＋１∈Ｆｖを得て出力する（ステップＳ２１５）。
【００３３】
分割部１１３から出力された要素ｙ０，…，ｙＮ−１、シード生成部１１１から出力されたシードｓ０，…，ｓＮ−１、任意値生成部２１４から出力された任意値ｒ０，…，ｒＮ−１、および、チェックサム生成部２１５から出力されたチェックサムｃ０，…，ｃＮ−１はシェア生成部２１６に入力される。シェア生成部２１６は、要素ｙｉ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の任意値ｒｄ、およびチェックサムｃｉ−１ ｍｏｄ Ｎを各シェア変換装置２２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）に割り当て、要素ｙｉ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の任意値ｒｄ、およびチェックサムｃｉ−１ ｍｏｄ Ｎを含む情報を、秘密分散における平文ｘのシェアＳＳｉとして得て出力する。各シェアＳＳｉは各シェア変換装置２２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）のシェアである。各シェアＳＳｉは他の情報を含んでもよいが、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについての要素ｙｄ、シードｓｉ、任意値ｒｉ、およびｃ０，…，ｃＮ−１のうちｃｉ−１ ｍｏｄ Ｎ以外のチェックサムを含まない。シードｓ１，…，ｓＮ−１のサイズおよびＮ，ｖはｍに依存しない。平文のデータサイズｍに関する総シェアサイズのオーダーは、（２，Ｎ）−シャミア秘密分散ではＯ（Ｎｍ）となるところ、本形態ではＯ（ｍ）で済む。個々のシェアのサイズはＯ（ｍ／Ｎ）である。例えば、シェアＳＳ０，…，ＳＳＮ−１の総データ量は平文ｘのデータ量のＮ倍未満である。例えば、各シェアＳＳｉのデータ量は平文ｘのデータ量未満である（ステップＳ２１６）。
【００３４】
シェア生成部２１６で得られた各シェアＳＳｉは通信部１１７に入力される。通信部１１７は、各シェアＳＳｉを各シェア変換装置２２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）に対して出力する。出力された各シェアＳＳｉはネットワークを通じて各シェア変換装置２２−Ａｉに送信される。すなわち、シェアＳＳ０はシェア変換装置２２−Ａ０に送信され、シェアＳＳ１はシェア変換装置２２−Ａ１に送信され、・・・、シェアＳＳＮ−１はシェア変換装置２２−ＡＮ−１に送信される（ステップＳ２１７）。
【００３５】
＜シェア変換方法＞
図５を用い、本形態の各シェア変換装置２２−Ａｉが行うシェア生成方法を説明する。
シェア生成装置２１から出力された要素ｙｉ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の任意値ｒｄ、およびチェックサムｃｉ−１ ｍｏｄ Ｎを含むシェアＳＳｉはシェア変換装置２２−Ａｉ（図３）の通信部１２０１−Ａｉ（第１入力部）に受信される（受け付けられる）。受信されたシェアＳＳｉは記憶部１２１０−Ａｉに格納される（ステップＳ２２１０−Ａｉ）。
【００３６】
次に、各シェア変換装置１２−Ａｉに代えて各シェア変換装置２２−Ａｉが、第１実施形態で説明したステップＳ１２０２−ＡｉおよびＳ１２０３−Ａｉの処理を実行する。
【００３７】
シェアＳＳｉに含まれた任意値ｒｄおよび通信部１２０１−Ａｉで受信されたシェア［ｙｄ］ｉ（ただし、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉ）（ステップＳ１２０３−Ａｉ）はシェア生成部２２０４−Ａｉ（第２シェア生成部）に入力される。シェア生成部２２０４−Ａｉは、任意値ｒｄおよびシェア［ｙｄ］ｉを用いた秘密計算（秘密計算による公開値倍算、および加算）により、シャミア秘密分散法に則ったチェックサムｃｄ＝Σ０≦ｊ＜ｍ’（ｄ）−１｛（ｙ’ｄ）ｊｒｄｊ＋１｝＋（ｙ’ｄ）ｍ’（ｄ）−１ｒｄｍ’（ｄ）＋１∈Ｆｖのシェア［ｃｄ］ｉを得て出力する。前述のように要素ｙｄはｍ（ｄ）個のサブ要素（ｙｄ）０，…，（ｙｉ）ｍ（ｄ）−１に分割できる。（ｙ’ｄ）ｊが集合Ｆｖに属する（（ｙｄ）ｖｊ，（ｙｄ）ｖｊ＋１，…，（ｙｄ）ｖ（ｊ＋１）−１）∈Ｆｖであり、ｍ’（ｄ）はｃｅｉｌ（ｍ（ｄ）／ｖ））である。また、ｊ＝ｍ’（ｉ）−１について、（ｙｄ）ｖ（ｍ’（ｄ）−１），（ｙｄ）ｖ（ｍ’（ｄ）−１）＋１，…，（ｙｄ）ｖｍ’（ｄ）−１がｖ個に満たない場合、（ｙ’ｄ）ｍ’（ｄ）−１＝（（ｙｄ）ｖ（ｍ’（ｄ）−１），（ｙｄ）ｖ（ｍ’（ｄ）−１）＋１，…，（ｙｄ）ｍ（ｄ）−１，０，…，０）∈Ｆｖとする。シャミア秘密分散法に則ったシェアを用いて秘密計算による公開値倍算、および加算を行う方法は、例えば、参考文献２（３ページのＬｅｍｍａ）に記載されている（ステップＳ２２０４−Ａｉ）。
【００３８】
シェア［ｃｄ］ｉは通信部１２０１−Ａｉに入力される。通信部１２０１−Ａｉ（第２出力部）はシェア［ｃｄ］ｉ（ただし、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉ）を他のシェア変換装置２２−Ａｄ＋１ ｍｏｄ Ｎに対して出力する。出力されたシェア［ｃｄ］ｉはネットワークを介してシェア変換装置２２−Ａｄ＋１ ｍｏｄ Ｎに送信され、シェア変換装置２２−Ａｄ＋１ｍｏｄ Ｎの通信部１２０１−Ａｄ＋１ ｍｏｄ Ｎで受信され、記憶部１２１０−Ａｄ＋１ ｍｏｄ Ｎに格納される。当該シェア［ｃｄ］ｉ、シェア生成部２２０４−Ａｄ＋１ ｍｏｄ Ｎで生成されたシェア［ｃｄ］ｄ＋１ ｍｏｄ Ｎ、シェアＳＳｄ＋１ ｍｏｄ Ｎに含まれたチェックサムｃｄは検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎに入力される。検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎは、チェックサムｃｄとシェア［ｃｄ］ｉが正しい関係にあるかを検証する。本形態の検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎは、チェックサムｃｄとＮ個のシェア［ｃｄ］０，…，［ｃｄ］Ｎ−１が正しい関係にあるかを検証する。例えば、検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎは、入力されたＮ個のシェア［ｃｄ］０，…［ｃｄ］Ｎ−１が互いに整合性を持つか否かを検証し（検証１：整合性検証）、さらに、入力されたＮ個のシェア［ｃｄ］０，…［ｃｄ］Ｎ−１の何れか２個のシェア［ｃｄ］ｉ’および［ｃｄ］ｉ”（ただし、ｉ’，ｉ”∈｛０，…，Ｎ−１｝かつｉ’≠ｉ”）から復元された値（実施形態のシャミア秘密分散法は2-out-of-Nしきい値分散方式である）とチェックサムｃｄとが互いに一致するかを検証する（検証２：同一性検証）。整合性検証は、例えば、何れか２個のシェア［ｃｄ］ｉ’および［ｃｄ］ｉ”からラグランジェの補間公式を用いて他のシェア［ｃｄ］ｉ’’’（ただし、ｉ’’’∈｛０，…，Ｎ−１｝かつｉ’’’≠ｉ”かつｉ’’’≠ｉ’）を計算してその計算結果を［ｂｄ］ｉ’’’とし、［ｂｄ］ｉ’’’と検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎに入力されたＮ個のシェア［ｃｄ］０，…［ｃｄ］Ｎ−１に含まれる［ｃｄ］ｉ’’’とが互いに一致するかを検証する処理である。すべてのｉ’’’について［ｂｄ］ｉ’’’＝［ｃｄ］ｉ’’’が成り立てば整合性検証は合格であり、そうでなければ整合性検証は不合格である。また、同一性検証では、２個のシェア［ｃｄ］ｉ’および［ｃｄ］ｉ”から復元された値とチェックサムｃｄとが互いに一致すれば同一性検証は合格であり、そうでなければ同一性検証は不合格である。整合性検証および同一性検証の両方に合格すれば検証合格であり、そうでない場合に検証不合格である。
【００３９】
同様に、他のシェア変換装置２２−Ａｄから出力されたシェア［ｃｉ−１ ｍｏｄ Ｎ］ｄは、通信部１２０１−Ａｉ（第２入力部）で受信され（受け付けられ）、記憶部１２１０−Ａｉに格納される。他のシェア変換装置２２−Ａｄから出力されたシェア［ｃｉ−１ ｍｏｄ Ｎ］ｄ、シェア生成部２２０４−Ａｉで生成されたシェア［ｃｉ−１ ｍｏｄ Ｎ］ｉ、シェアＳＳｉに含まれたチェックサムｃｉ−１ ｍｏｄ Ｎは検証部２２０５−Ａｉに入力される。検証部２２０５−Ａｉは、チェックサムｃｉ−１ ｍｏｄ Ｎとシェア［ｃｉ−１ ｍｏｄ Ｎ］ｄとが正しい関係にあるかを検証する。本形態の検証部２２０５−Ａｉは、入力されたチェックサムｃｉ−１ ｍｏｄ Ｎ、シェア［ｃｉ−１ ｍｏｄ Ｎ］ｄ、およびシェア［ｃｉ−１ ｍｏｄ Ｎ］ｉが正しい関係にあるかを検証する。例えば、検証部２２０５−Ａｉは、入力されたＮ個のシェア［ｃｉ−１ ｍｏｄ Ｎ］０，…，［ｃｉ−１ ｍｏｄ Ｎ］Ｎ−１が互いに整合性を持つか否かを検証し（検証１：整合性検証）、さらに、入力されたＮ個のシェア［ｃｉ−１ ｍｏｄ Ｎ］０，…，［ｃｉ−１ ｍｏｄ Ｎ］Ｎ−１の何れか２個のシェア［ｃｉ−１ ｍｏｄ Ｎ］ｉ’および［ｃｉ−１ ｍｏｄ Ｎ］ｉ”（ただし、ｉ’，ｉ”∈｛０，…，Ｎ−１｝かつｉ’≠ｉ”）から復元された値がチェックサムｃｉ−１ ｍｏｄ Ｎに一致するかを検証する（検証２：同一性検証）。整合性検証は、例えば、何れか２個のシェア［ｃｉ−１ ｍｏｄ Ｎ］ｉ’および［ｃｉ−１ ｍｏｄＮ］ｉ”からラグランジェの補間公式を用いて他のシェア［ｃｉ−１ ｍｏｄ Ｎ］ｉ’’’（ただし、ｉ’’’∈｛０，…，Ｎ−１｝かつｉ’’’≠ｉ”かつｉ’’’≠ｉ’）を計算してその計算結果を［ｂｉ−１ ｍｏｄ Ｎ］ｉ’’’とし、［ｂｉ−１ ｍｏｄ Ｎ］ｉ’’’と検証部２２０５−Ａｉに入力されたＮ個のシェア［ｃｉ−１ ｍｏｄ Ｎ］０，…，［ｃｉ−１ ｍｏｄ Ｎ］Ｎ−１に含まれる［ｃｉ−１ ｍｏｄ Ｎ］ｉ’’’とが互いに一致するかを検証する処理である。すべてのｉ’’’について［ｂｉ−１ ｍｏｄ Ｎ］ｉ’’’＝［ｃｉ−１ ｍｏｄ Ｎ］ｉ’’’が成り立てば整合性検証は合格であり、そうでなければ整合性検証は不合格である。また、同一性検証では、２個のシェア［ｃｉ−１ ｍｏｄ Ｎ］ｉ’および［ｃｉ−１ ｍｏｄ Ｎ］ｉ”から復元された値とチェックサムｃｉ−１ ｍｏｄ Ｎとが互いに一致すれば同一性検証は合格であり、そうでなければ同一性検証は不合格である。整合性検証および同一性検証の両方に合格すれば検証合格であり、そうでない場合に検証不合格である（ステップＳ２２０５−Ａｉ）。
【００４０】
検証部２２０５−Ａｉで検証合格であると判定された場合、各シェア変換装置１２−Ａｉに代えて各シェア変換装置２２−Ａｉが、第１実施形態で説明したステップＳ１２０６−ＡｉからＳ１２０９−Ａｉの処理を実行して処理を終了する。一方、検証部２２０５−Ａｉで検証不合格であると判定された場合、制御部１２１１−Ａｉは処理をエラー終了させる（ステップＳ２２０６−Ａｉ）。
【００４１】
＜本形態の特徴＞
本形態でもシャミア秘密分散法に則ったシェアよりも総通信データ量を小さくできる。また、各シェア変換装置２２−ＡｉはシェアＳＳｉをシャミア秘密分散法に則ったシェア［ｘ］ｉに変換できる。さらに、本形態ではシェアＳＳｉがチェックサムを含み、シェア変換の際に検証処理を行うことにしたため、シェア生成装置２１および／またはシェア変換装置２２−Ａｉで行われた不正な処理を検知できる。
【００４２】
なお、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、シェア生成装置および／またはシェア変換装置は、秘密計算を行う秘密計算装置の一部であってもよいし、秘密計算装置とは別個の装置であってもよい。
【００４３】
上記の各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００４４】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４５】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００４７】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【００４８】
「シェア生成方法」および「シェア変換方法」に係る発明は、特許法第２条第３項第３号に規定された「物を生産する方法の発明」に該当する。また、「シェア生成方法」および「シェア変換方法」によって得られるシェアは、同条第４項に規定された「プログラム等」に該当する。例えば、このようなシェアにはその後の処理のためヘッダや拡張子等が付され、これらを処理するコンピュータはシェアに付されたヘッダや拡張子等を参照しつつ、各シェアを用いた処理を実行する。
【符号の説明】
【００４９】
１，２  秘密計算システム
１１，２１  シェア生成装置
１２−Ａｉ，２２−Ａｉ  シェア変換装置
【図１】
2019039380.tif 000003
【図２】
2019039380.tif 000004
【図３】
2019039380.tif 000005
【図４】
2019039380.tif 000006
【図５】
2019039380.tif 000007
【手続補正書】
【提出日】令和2年2月18日(2020.2.18)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
分割部１１３から出力された要素ｙ０，…，ｙＮ−１およびシード生成部１１１から出力されたシードｓ０，…，ｓＮ−１はシェア生成部１１６に入力される。シェア生成部１１６は、要素ｙｉとｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを各シェア変換装置１２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）に割り当て、要素ｙｉとｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを含む情報を、秘密分散における平文ｘのシェアＳＳｉとして得て出力する。なお、ｉ≠０かつｉ≠Ｎ−１の場合、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄはシードｓ０，…，ｓｉ−１，ｓｉ＋１，…，ｓＮ−１である。ｉ＝０の場合、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄはシードｓ１，…，ｓＮ−１である。ｉ＝Ｎ−１の場合、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄはシードｓ０，…，ｓＮ−２である。各シェアＳＳｉは各シェア変換装置１２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）のシェアである。各シェアＳＳｉは他の情報を含んでもよいが、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについての要素ｙｄおよびシードｓｉを含まない。なお、ヌル値である要素ｙｉ∈Ｆ０とＮ−１個のシードｓｄとを含む情報とは、要素ｙｉがヌル値であることを示し、かつＮ−１個のシードｓｄを含む情報を意味する。ヌル値である要素ｙｉ∈Ｆ０とＮ−１個のシードｓｄとを含む情報は、Ｎ−１個のシードｓｄを含むが実質的には要素ｙｉを含まない。シードｓ１，…，ｓＮ−１のサイズおよびＮはｍに依存しない。平文ｘのデータサイズｍに関する総シェアサイズのオーダーは、（２，Ｎ）−シャミア秘密分散ではＯ（Ｎｍ）となるところ、本形態ではＯ（ｍ）で済む。個々のシェアのサイズはＯ（ｍ／Ｎ）である。例えば、シェアＳＳ０，…，ＳＳＮ−１の総データ量は平文ｘのデータ量のＮ倍未満である。例えば、各シェアＳＳｉのデータ量は平文ｘのデータ量未満である（ステップＳ１１６）。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
＜シェア変換方法＞
図５を用い、本形態の各シェア変換装置１２−Ａｉが行うシェア変換方法を説明する。
シェア生成装置１１から出力された要素ｙｉとｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄとを含むシェアＳＳｉはシェア変換装置１２−Ａｉ（図３）の通信部１２０１−Ａｉ（第１入力部）に受信される（受け付けられる）。受信されたシェアＳＳｉは記憶部１２１０−Ａｉに格納される（ステップＳ１２０１−Ａｉ）。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
共有部１２０２−Ａｉは、他のシェア変換装置１２−Ａｉ−１ ｍｏｄ Ｎの共有部１２０２−Ａｉ−１ ｍｏｄ Ｎとの間で任意値ｔｉ∈Ｆｍ（ｉ）を共有する。すなわち、共有部１２０２−Ａｉと共有部１２０２−Ａｉ−１ ｍｏｄ Ｎとは同一の任意値ｔｉを得る。共有部１２０２−Ａｉから任意値ｔｉまたは任意値ｔｉを特定する情報を共有部１２０２−Ａｉ−１ ｍｏｄ Ｎに送信して両者で任意値ｔｉが共有されてもよいし、共有部１２０２−Ａｉ−１ ｍｏｄ Ｎから任意値ｔｉまたは任意値ｔｉを特定する情報を共有部１２０２−Ａｉに送信して両者で任意値ｔｉが共有されてもよいし、共有部１２０２−Ａｉと共有部１２０２−Ａｉ−１ ｍｏｄ Ｎとで共有シード値を共有しておき、両者が共有シード値を用いた同一の処理を実行することで任意値ｔｉが共有されてもよい。任意値ｔｉは、乱数（擬似乱数または真正乱数）であってもよいし、他の処理で得られた値であってもよいし、予め定められた複数の値から選択された値であってもよい。任意値ｔｉ∈Ｆｍ（ｉ）の共有は、ステップＳ１２０１−Ａｉが実行されたことを契機として行われてもよいし、他の共有部１２０２−Ａｉ−１ ｍｏｄ Ｎからの要求を契機として行われてもよいし、その他の契機で行われてもよいし、予め行われていてもよい。共有部１２０２−Ａｉは得た任意値ｔｉを出力する。要素ｙｉがヌル値である場合には任意値ｔｉもヌル値に設定される（ステップＳ１２０２−Ａｉ）。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】変更
【補正の内容】
【００３３】
分割部１１３から出力された要素ｙ０，…，ｙＮ−１、シード生成部１１１から出力されたシードｓ０，…，ｓＮ−１、任意値生成部２１４から出力された任意値ｒ０，…，ｒＮ−１、および、チェックサム生成部２１５から出力されたチェックサムｃ０，…，ｃＮ−１はシェア生成部２１６に入力される。シェア生成部２１６は、要素ｙｉ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の任意値ｒｄ、およびチェックサムｃｉ−１ ｍｏｄ Ｎを各シェア変換装置２２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）に割り当て、要素ｙｉ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の任意値ｒｄ、およびチェックサムｃｉ−１ ｍｏｄ Ｎを含む情報を、秘密分散における平文ｘのシェアＳＳｉとして得て出力する。各シェアＳＳｉは各シェア変換装置２２−Ａｉ（ただし、ｉ＝０，…，Ｎ−１）のシェアである。各シェアＳＳｉは他の情報を含んでもよいが、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについての要素ｙｄ、シードｓｉ、任意値ｒｉ、およびｃ０，…，ｃＮ−１のうちｃｉ−１ ｍｏｄ Ｎ以外のチェックサムを含まない。シードｓ１，…，ｓＮ−１のサイズおよびＮ，ｖはｍに依存しない。平文ｘのデータサイズｍに関する総シェアサイズのオーダーは、（２，Ｎ）−シャミア秘密分散ではＯ（Ｎｍ）となるところ、本形態ではＯ（ｍ）で済む。個々のシェアのサイズはＯ（ｍ／Ｎ）である。例えば、シェアＳＳ０，…，ＳＳＮ−１の総データ量は平文ｘのデータ量のＮ倍未満である。例えば、各シェアＳＳｉのデータ量は平文ｘのデータ量未満である（ステップＳ２１６）。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
＜シェア変換方法＞
図５を用い、本形態の各シェア変換装置２２−Ａｉが行うシェア生成方法を説明する。
シェア生成装置２１から出力された要素ｙｉ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個のシードｓｄ、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉについてのＮ−１個の任意値ｒｄ、およびチェックサムｃｉ−１ ｍｏｄ Ｎを含むシェアＳＳｉはシェア変換装置２２−Ａｉ（図３）の通信部１２０１−Ａｉ（第１入力部）に受信される（受け付けられる）。受信されたシェアＳＳｉは記憶部１２１０−Ａｉに格納される（ステップＳ２２０１−Ａｉ）。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
シェアＳＳｉに含まれた任意値ｒｄおよび通信部１２０１−Ａｉで受信されたシェア［ｙｄ］ｉ（ただし、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉ）（ステップＳ１２０３−Ａｉ）はシェア生成部２２０４−Ａｉ（第２シェア生成部）に入力される。シェア生成部２２０４−Ａｉは、任意値ｒｄおよびシェア［ｙｄ］ｉを用いた秘密計算（秘密計算による公開値倍算、および加算）により、シャミア秘密分散法に則ったチェックサムｃｄ＝Σ０≦ｊ＜ｍ’（ｄ）−１｛（ｙ’ｄ）ｊｒｄｊ＋１｝＋（ｙ’ｄ）ｍ’（ｄ）−１ｒｄｍ’（ｄ）＋１∈Ｆｖのシェア［ｃｄ］ｉを得て出力する。前述のように要素ｙｄはｍ（ｄ）個のサブ要素（ｙｄ）０，…，（ｙｉ）ｍ（ｄ）−１に分割できる。（ｙ’ｄ）ｊが集合Ｆｖに属する（（ｙｄ）ｖｊ，（ｙｄ）ｖｊ＋１，…，（ｙｄ）ｖ（ｊ＋１）−１）∈Ｆｖであり、ｍ’（ｄ）はｃｅｉｌ（ｍ（ｄ）／ｖ）である。また、ｊ＝ｍ’（ｉ）−１について、（ｙｄ）ｖ（ｍ’（ｄ）−１），（ｙｄ）ｖ（ｍ’（ｄ）−１）＋１，…，（ｙｄ）ｖｍ’（ｄ）−１がｖ個に満たない場合、（ｙ’ｄ）ｍ’（ｄ）−１＝（（ｙｄ）ｖ（ｍ’（ｄ）−１），（ｙｄ）ｖ（ｍ’（ｄ）−１）＋１，…，（ｙｄ）ｍ（ｄ）−１，０，…，０）∈Ｆｖとする。シャミア秘密分散法に則ったシェアを用いて秘密計算による公開値倍算、および加算を行う方法は、例えば、参考文献２（３ページのＬｅｍｍａ）に記載されている（ステップＳ２２０４−Ａｉ）。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
シェア［ｃｄ］ｉは通信部１２０１−Ａｉに入力される。通信部１２０１−Ａｉ（第２出力部）はシェア［ｃｄ］ｉ（ただし、ｄ∈｛０，…，Ｎ−１｝かつｄ≠ｉ）を他のシェア変換装置２２−Ａｄ＋１ ｍｏｄ Ｎに対して出力する。出力されたシェア［ｃｄ］ｉはネットワークを介してシェア変換装置２２−Ａｄ＋１ ｍｏｄ Ｎに送信され、シェア変換装置２２−Ａｄ＋１ｍｏｄ Ｎの通信部１２０１−Ａｄ＋１ ｍｏｄ Ｎで受信され、記憶部１２１０−Ａｄ＋１ ｍｏｄ Ｎに格納される。当該シェア［ｃｄ］ｉ、シェア生成部２２０４−Ａｄ＋１ ｍｏｄ Ｎで生成されたシェア［ｃｄ］ｄ＋１ ｍｏｄ Ｎ、シェアＳＳｄ＋１ ｍｏｄ Ｎに含まれたチェックサムｃｄは検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎに入力される。検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎは、チェックサムｃｄとシェア［ｃｄ］ｉが正しい関係にあるかを検証する。本形態の検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎは、チェックサムｃｄとＮ個のシェア［ｃｄ］０，…，［ｃｄ］Ｎ−１が正しい関係にあるかを検証する。例えば、検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎは、入力されたＮ個のシェア［ｃｄ］０，…，［ｃｄ］Ｎ−１が互いに整合性を持つか否かを検証し（検証１：整合性検証）、さらに、入力されたＮ個のシェア［ｃｄ］０，…，［ｃｄ］Ｎ−１の何れか２個のシェア［ｃｄ］ｉ’および［ｃｄ］ｉ”（ただし、ｉ’，ｉ”∈｛０，…，Ｎ−１｝かつｉ’≠ｉ”）から復元された値（実施形態のシャミア秘密分散法は2-out-of-Nしきい値分散方式である）とチェックサムｃｄとが互いに一致するかを検証する（検証２：同一性検証）。整合性検証は、例えば、何れか２個のシェア［ｃｄ］ｉ’および［ｃｄ］ｉ”からラグランジェの補間公式を用いて他のシェア［ｃｄ］ｉ’’’（ただし、ｉ’’’∈｛０，…，Ｎ−１｝かつｉ’’’≠ｉ”かつｉ’’’≠ｉ’）を計算してその計算結果を［ｂｄ］ｉ’’’とし、［ｂｄ］ｉ’’’と検証部２２０５−Ａｄ＋１ ｍｏｄ Ｎに入力されたＮ個のシェア［ｃｄ］０，…，［ｃｄ］Ｎ−１に含まれる［ｃｄ］ｉ’’’とが互いに一致するかを検証する処理である。すべてのｉ’’’について［ｂｄ］ｉ’’’＝［ｃｄ］ｉ’’’が成り立てば整合性検証は合格であり、そうでなければ整合性検証は不合格である。また、同一性検証では、２個のシェア［ｃｄ］ｉ’および［ｃｄ］ｉ”から復元された値とチェックサムｃｄとが互いに一致すれば同一性検証は合格であり、そうでなければ同一性検証は不合格である。整合性検証および同一性検証の両方に合格すれば検証合格であり、そうでない場合に検証不合格である。
【国際調査報告】
2019039380.tif 000008
2019039380.tif 000009
2019039380.tif 000010