Nova Patents
JP6973634B2

System, apparatus, method and program for secure aggregate median computation

Abstract

This record has no abstract on file.

JP6973634B2, drawing sheet 1
Sheet 1 of 4

Term

12.6 yearsleft in the term

Expires 22 April 2039.

  1. Priority
  2. Filed
  3. Granted
  4. Today
  5. Expires

5 claims: 3 independent, 2 dependent

  1. 1
    複数の秘密計算装置を含む秘密集約中央値システムであって、 mは2以上の整数であり、[v]:=[v 0 ], ..., [v m-1 ]はキー属性とバリュー属性とからなるテーブルを所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソートしたときの所望のバリュー属性v:=v 0 , ..., v m-1 を秘密分散したシェアであり、[a]:=[a 0 ], ..., [a m-1 ]は所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソート済みの上記テーブルを上記キー属性の値に基づいてグループ分けしたときに上記vのグループ内での昇順順位を表すベクトルa:=a 0 , ..., a m-1 を秘密分散したシェアであり、[d]:=[d 0 ], ..., [d m-1 ]は所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソート済みの上記テーブルを上記キー属性の値に基づいてグループ分けしたときに上記vのグループ内での降順順位を表すベクトルd:=d 0 , ..., d m-1 を秘密分散したシェアであり、|・|は等式・の真偽を返却する記号であり、 上記秘密計算装置は、 上記シェア[a]と上記シェア[d]とを用いて、2 λ mを満たすλに対する[2 λ +a-d], [2 λ +d-a]の計算結果をλビットにビット分解して、復元するとビット列a-dとなるシェア{a-d}と、復元するとビット列d-aとなるシェア{d-a}とを生成する減算部と、 上記シェア{a-d}と上記シェア{d-a}とを用いて、復元するとa-dの最下位ビットを除いたビット列a'となるシェア{a'}と、復元するとd-aの最下位ビットを除いたビット列d'となるシェア{d'}とを生成するビット削除部と、 上記シェア{a'}と上記シェア{d'}とを用いて、{a"}:={|a'=0|}, {d"}:={|d'=0|}を計算し、復元するとフラグa", d"となるシェア{a"}, {d"}を生成する等号判定部と、 上記シェア[v]と上記シェア{a"}, {d"}とを用いて、[v a ]:=[va"], [v d ]:=[vd"]を計算し、復元するとベクトルv a , v d となるシェア[v a ], [v d ]を生成するフラグ適用部と、 上記シェア{a"}, {d"}を用いて、復元するとフラグa", d"の否定¬a", ¬d"をソートする置換σ a , σ d となるシェア{{σ a }}, {{σ d }}を生成する置換生成部と、 上記シェア[v a ], [v d ]と上記シェア{{σ a }}, {{σ d }}とを用いて、[x]:=[σ a (v a )+σ d (v d )]を計算し、復元すると各グループの中央値を表すベクトルxとなるシェア[x]を生成する中央値計算部と、 を含む秘密集約中央値システム。
  2. 2
    請求項1に記載の秘密集約中央値システムであって、 Fは任意の環であり、n k は1以上の整数であり、[k 0 ], ..., [k nk-1 ]はキー属性k 0 , ..., k nk-1 ∈F m を秘密分散したシェアであり、[v']は上記テーブルを上記キー属性の値に基づいてソートする前の所望のバリュー属性v'∈F m を秘密分散したシェアであり、 上記秘密計算装置は、 上記シェア[k 0 ], ..., [k nk-1 ]を用いて、復元すると上記キー属性k 0 , ..., k nk-1 をビット分解して結合したビット列b:=b 0 , ..., b m-1 となるシェア{b}から、復元すると上記ビット列bを昇順に安定ソートする置換σ 0 となるシェア{{σ 0 }}を生成するグループソート生成部と、 上記シェア{b}と上記シェア{{σ 0 }}とを用いて、復元すると上記ビット列bを上記置換σ 0 でソートしたソート済みビット列b':=b' 0 , ..., b' m-1 となるシェア{b'}を生成するビット列ソート部と、 上記シェア{b'}を用いて、0以上m-2以下の各整数iについて{e i }:={b' i ≠b' i+1 }を設定し、かつ、{e m-1 }:={1}を設定して、復元すると上記フラグe:=e 0 , ..., e m-1 となる上記シェア{e}を生成するフラグ生成部と、 上記シェア{e}を用いて、復元すると上記フラグeの否定¬eを昇順に安定ソートする置換σとなるシェア{{σ}}を生成するキー集約ソート生成部と、 上記シェア[v']と上記シェア{{σ 0 }}とを用いて、復元すると上記バリュー属性v'を上記置換σ 0 でソートした上記バリュー属性vとなる上記シェア[v]を生成するバリューソート部と、 をさらに含む秘密集約中央値システム。
  3. 3
    mは2以上の整数であり、[v]:=[v 0 ], ..., [v m-1 ]はキー属性とバリュー属性とからなるテーブルを所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソートしたときの所望のバリュー属性v:=v 0 , ..., v m-1 を秘密分散したシェアであり、[a]:=[a 0 ], ..., [a m-1 ]は所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソート済みの上記テーブルを上記キー属性の値に基づいてグループ分けしたときに上記vのグループ内での昇順順位を表すベクトルa:=a 0 , ..., a m-1 を秘密分散したシェアであり、[d]:=[d 0 ], ..., [d m-1 ]は所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソート済みの上記テーブルを上記キー属性の値に基づいてグループ分けしたときに上記vのグループ内での降順順位を表すベクトルd:=d 0 , ..., d m-1 を秘密分散したシェアであり、|・|は等式・の真偽を返却する記号であり、 上記シェア[a]と上記シェア[d]とを用いて、2 λ mを満たすλに対する[2 λ +a-d], [2 λ +d-a]の計算結果をλビットにビット分解して、復元するとビット列a-dとなるシェア{a-d}と、復元するとビット列d-aとなるシェア{d-a}とを生成する減算部と、 上記シェア{a-d}と上記シェア{d-a}とを用いて、復元するとa-dの最下位ビットを除いたビット列a'となるシェア{a'}と、復元するとd-aの最下位ビットを除いたビット列d'となるシェア{d'}とを生成するビット削除部と、 上記シェア{a'}と上記シェア{d'}とを用いて、{a"}:={|a'=0|}, {d"}:={|d'=0|}を計算し、復元するとフラグa", d"となるシェア{a"}, {d"}を生成する等号判定部と、 上記シェア[v]と上記シェア{a"}, {d"}とを用いて、[v a ]:=[va"], [v d ]:=[vd"]を計算し、復元するとベクトルv a , v d となるシェア[v a ], [v d ]を生成するフラグ適用部と、 上記シェア{a"}, {d"}を用いて、復元するとフラグa", d"の否定¬a", ¬d"をソートする置換σ a , σ d となるシェア{{σ a }}, {{σ d }}を生成する置換生成部と、 上記シェア[v a ], [v d ]と上記シェア{{σ a }}, {{σ d }}とを用いて、[x]:=[σ a (v a )+σ d (v d )]を計算し、復元すると各グループの中央値を表すベクトルxとなるシェア[x]を生成する中央値計算部と、 を含む秘密計算装置。
  4. 4
    複数の秘密計算装置を含む秘密集約中央値システムが実行する秘密集約中央値方法であって、 mは2以上の整数であり、[v]:=[v 0 ], ..., [v m-1 ]はキー属性とバリュー属性とからなるテーブルを所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソートしたときの所望のバリュー属性v:=v 0 , ..., v m-1 を秘密分散したシェアであり、[a]:=[a 0 ], ..., [a m-1 ]は所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソート済みの上記テーブルを上記キー属性の値に基づいてグループ分けしたときに上記vのグループ内での昇順順位を表すベクトルa:=a 0 , ..., a m-1 を秘密分散したシェアであり、[d]:=[d 0 ], ..., [d m-1 ]は所望のバリュー属性の値と上記キー属性の値とに基づいて安定ソート済みの上記テーブルを上記キー属性の値に基づいてグループ分けしたときに上記vのグループ内での降順順位を表すベクトルd:=d 0 , ..., d m-1 を秘密分散したシェアであり、|・|は等式・の真偽を返却する記号であり、 上記秘密計算装置の減算部が、上記シェア[a]と上記シェア[d]とを用いて、2 λ mを満たすλに対する[2 λ +a-d], [2 λ +d-a]の計算結果をλビットにビット分解して、復元するとビット列a-dとなるシェア{a-d}と、復元するとビット列d-aとなるシェア{d-a}とを生成し、 上記秘密計算装置のビット削除部が、上記シェア{a-d}と上記シェア{d-a}とを用いて、復元するとa-dの最下位ビットを除いたビット列a'となるシェア{a'}と、復元するとd-aの最下位ビットを除いたビット列d'となるシェア{d'}とを生成し、 上記秘密計算装置の等号判定部が、上記シェア{a'}と上記シェア{d'}とを用いて、{a"}:={|a'=0|}, {d"}:={|d'=0|}を計算し、復元するとフラグa", d"となるシェア{a"}, {d"}を生成し、 上記秘密計算装置のフラグ適用部が、上記シェア[v]と上記シェア{a"}, {d"}とを用いて、[v a ]:=[va"], [v d ]:=[vd"]を計算し、復元するとベクトルv a , v d となるシェア[v a ], [v d ]を生成し、 上記秘密計算装置の置換生成部が、上記シェア{a"}, {d"}を用いて、復元するとフラグa", d"の否定¬a", ¬d"をソートする置換σ a , σ d となるシェア{{σ a }}, {{σ d }}を生成し、 上記秘密計算装置の中央値計算部が、上記シェア[v a ], [v d ]と上記シェア{{σ a }}, {{σ d }}とを用いて、[x]:=[σ a (v a )+σ d (v d )]を計算し、復元すると各グループの中央値を表すベクトルxとなるシェア[x]を生成する、 を含む秘密集約中央値方法。
  5. 5
    請求項3に記載の秘密計算装置としてコンピュータを機能させるためのプログラム。
Independent claims5