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