特許
J-GLOBAL ID：201303050188662990
秘密計算システム、暗号化装置、秘密計算装置及びその方法、プログラム
発明者：
,
出願人/特許権者：
代理人 (3件)：
中尾 直樹
, 中村 幸雄
, 義村 宗洋
公報種別：公開公報
出願番号（国際出願番号）：特願2012-014214
公開番号（公開出願番号）：特開2013-157652
出願日： 2012年01月26日
公開日（公表日）： 2013年08月15日
要約：
【課題】暗号化されたn個の入力データに対して計算時間がO((m+n)logn)で秘密写像を計算できる技術を提供する。【解決手段】暗号行列の2列目と暗号列ベクトル[[0n]]と、n個の数値0からなる列ベクトルを暗号化したベクトルとを垂直に連結した像ベクトル[[a0]]と、m個の数値1からなる列ベクトル1mを暗号化したベクトルと、n個の数値0からなる列ベクトル0nを暗号化したベクトルとを垂直に連結した更新済ベクトル[[c0]]とを用いて、反復毎に計算済みの要素数が指数的に増加するように写像適用後の値を計算するような反復計算を作り、秘密計算する。【選択図】図5
請求項（抜粋）：
Nは3以上の整数とし、暗号化装置とN個の秘密計算装置とを含む秘密計算システムであって、
前記暗号化装置は、
m行2列の行列の各行の1列目の要素に対して同じ行の2列目の要素を指定する写像を、行列が表現する写像とし、写像を表現する行列Tの各要素を暗号化し、N個の暗号行列を生成する暗号行列生成部と、
nを入力データの個数とし、n個の要素を持つ列ベクトルである入力ベクトルの各要素を暗号化し、N個の暗号入力ベクトルを生成する暗号入力ベクトル生成部と、
m個の数値0と、数値1,2,...,nとからなる列ベクトルである目印ベクトルの各要素を暗号化し、N個の暗号目印ベクトルを生成する暗号目印ベクトル生成部と、
n個の数値0からなる列ベクトル0nを暗号化し、N個の前記暗号行列の2列目とN個の暗号列ベクトル[[0n]]とをそれぞれ垂直に連結したN個の像ベクトル[[a0]]を生成する像ベクトル生成部と、
m個の数値1からなる列ベクトル1mを暗号化し、n個の数値0からなる列ベクトル0nを暗号化し、N個の暗号ベクトル[[1m]]とN個の暗号列ベクトル[[0n]]とをそれぞれ垂直に連結したN個の更新済ベクトル[[c0]]を生成する更新済ベクトル生成部と、
N個の前記暗号行列の1列目からなる列ベクトル、N個の前記暗号入力ベクトル、N個の前記暗号目印ベクトル、N個の前記像ベクトル及びN個の前記更新済ベクトルをそれぞれN個の秘密計算装置に配布する送信部と、を含み、
各前記秘密計算装置は、
秘密計算により前記暗号行列の1列目からなる列ベクトルの各要素に2を乗じた列ベクトルと、秘密計算により前記暗号入力ベクトルの各要素に2を乗じたものに1を足した列ベクトルとを垂直に連結したソート用キーベクトルと、前記暗号目印ベクトル、前記像ベクトル及び前記更新済ベクトルを水平に連結した行列を、前記ソート用キーベクトルの各要素の大小関係に応じて行毎に秘密計算によりソートするソート部と、
入力データの個数に1を足した値の対数値以上の最小の整数を反復回数tとし、u[p...q]を列ベクトルuのp+1行目からq行目までとし、A||BはAとBとの論理和を表し、iは1以上t以下の整数であり、i=1からi=tまで
d=2i-1
[[ci]][0...d]=[[ci-1]][0...d]
[[ai]][0...d]=[[ai-1]][0...d]
[[ci]][d...(m+n)]=[[ci-1]][d...(m+n)]||[[ci-1]][0...(m+n-d)]
[[ai]][d...(m+n)]
=[[ai-1]][d...(m+n)]+[[ai-1]][0...(m+n-d)]×([[ci]][d...(m+n)]-[[ci-1]][d...(m+n)])
を秘密計算する反復計算部と、
前記暗号目印ベクトルと反復計算後の前記像ベクトルとの組合せを行毎に秘密計算によりランダム置換するランダム置換部と、
当該秘密計算装置が保管する前記暗号目印ベクトルと他の秘密計算装置が保管する前記暗号目印ベクトルとから前記目印ベクトルを復号する目印ベクトル復号部と、
目印ベクトルの要素の内、1からnまでの値を持つ要素と同じ行の像ベクトルの要素を1からnまで順に並べた列ベクトルを暗号出力ベクトルとして求める並び替え部と、を含む、
秘密計算システム。
IPC (1件)：
FI (1件)：
Fターム (3件)：
5J104JA03
, 5J104NA02
, 5J104NA39
