(57)【要約】  アクセスした位置を明かすことなく配列に対するデータ読み込みやデータ書き込みを効率よく行う。秘密読み書き装置（１）は、読み込み命令もしくは書き込み命令を入力とし、読み込み命令が入力されたときは秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]を出力し、書き込み命令が入力されたときは秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]に秘匿文[d]を加算する。秘密読み込み部（１２）は、秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を読み込む。バッファ加算部（１３）は、未反映値cの秘匿文[c]を秘匿文[a[x]]へ加算する。バッファ追加部（１４）は、書き込みバッファ[b]へ秘匿文[x]と秘匿文[d]を追加する。秘密書き込み部（１５）は、書き込みバッファ[b]の要素数が所定の値を超えたとき、秘匿文の配列[a]の秘匿文のベクトル[b0]が示すアクセス位置へ秘匿文のベクトル[b1]が示す値を加算する。
2019059069.tif 000002
【特許請求の範囲】
【請求項１】
大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …,[a[n-1]])とアクセス位置xの秘匿文[x]とを含む読み込み命令、もしくは、上記秘匿文の配列[a]と上記秘匿文[x]と書き込む値dの秘匿文[d]とを含む書き込み命令を入力とし、上記読み込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]を出力し、上記書き込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]に秘匿文[d]を加算する秘密読み書き装置であって、
２個の秘匿文のベクトル[b0], [b1]からなる書き込みバッファ[b]=([b0], [b1])を記憶するバッファ記憶部と、
上記書き込み命令が入力されたとき、上記秘匿文のベクトル[b0]へ上記秘匿文[x]を追加し、上記秘匿文のベクトル[b1]へ上記秘匿文[d]を追加するバッファ追加部と、
上記書き込みバッファ[b]の要素数が所定の値を超えたとき、上記秘匿文の配列[a]のうち上記秘匿文のベクトル[b0]が示すアクセス位置へ上記秘匿文のベクトル[b1]が示す値を加算する秘密書き込み部と、
上記読み込み命令が入力されたとき、上記秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を読み込む秘密読み込み部と、
上記秘匿文のベクトル[b1]の要素のうち上記秘匿文のベクトル[b0]が示すアクセス位置が上記秘匿文[x]が示すアクセス位置と等しい要素の総和である未反映値cの秘匿文[c]を上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]へ加算するバッファ加算部と、
を含む秘密読み書き装置。
【請求項２】
請求項１に記載の秘密読み書き装置であって、
上記バッファ加算部は、次式により上記未反映値cの秘匿文[c]を計算するものである、
【数１５】
2019059069.tif 000017
秘密読み書き装置。
【請求項３】
請求項１に記載の秘密読み書き装置であって、
上記バッファ加算部は、次式により上記未反映値cの秘匿文[c]を計算するものである、
【数１６】
2019059069.tif 000018
秘密読み書き装置。
【請求項４】
請求項１に記載の秘密読み書き装置であって、
上記秘匿文の配列[a]と上記秘匿文[x]と上記秘匿文[d]は、tを1以上の整数とし、s≧2t-1とし、平文をs個に分割したシェアのうち、任意のt個のシェアが揃えば平文を復元でき、t個未満のシェアからは平文に関する一切の情報を得られない秘密分散により秘匿化したものであり、
上記秘密読み込み部は、上記秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を、アクセス位置xを明かすことなく読み込むものであり、
上記秘密書き込み部は、上記書き込みバッファの要素数が√nを超えたとき、上記秘匿文の配列[a]の上記秘匿文のベクトル[b0]が示すアクセス位置へ上記秘匿文のベクトル[b1]が示す値を、アクセス位置xを明かすことなく書き込むものである、
秘密読み書き装置。
【請求項５】
大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …,[a[n-1]])とアクセス位置xの秘匿文[x]とを含む読み込み命令、もしくは、上記秘匿文の配列[a]と上記秘匿文[x]と書き込む値dの秘匿文[d]とを含む書き込み命令を入力とし、上記読み込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]を出力し、上記書き込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]に秘匿文[d]を加算する秘密読み書き装置が実行する秘密読み書き方法であって、
バッファ記憶部に、２個の秘匿文のベクトル[b0], [b1]からなる書き込みバッファ[b]=([b0], [b1])が記憶されており、
バッファ追加部が、上記書き込み命令が入力されたとき、上記秘匿文のベクトル[b0]へ上記秘匿文[x]を追加し、上記秘匿文のベクトル[b1]へ上記秘匿文[d]を追加し、
秘密書き込み部が、上記書き込みバッファ[b]の要素数が所定の値を超えたとき、上記秘匿文の配列[a]のうち上記秘匿文のベクトル[b0]が示すアクセス位置へ上記秘匿文のベクトル[b1]が示す値を加算し、
秘密読み込み部が、上記読み込み命令が入力されたとき、上記秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を読み込み、
バッファ加算部が、上記秘匿文のベクトル[b1]の要素のうち上記秘匿文のベクトル[b0]が示すアクセス位置が上記秘匿文[x]が示すアクセス位置と等しい要素の総和である未反映値cの秘匿文[c]を上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]へ加算する、
秘密読み書き方法。
【請求項６】
請求項１から４のいずれかに記載の秘密読み書き装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号応用技術に関するものであり、特にアクセスした位置を明かすことなく配列に対するデータの読み込みや書き込みを行う技術に関する。
【背景技術】
【０００２】
暗号化された数値を復元することなく特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば、非特許文献１参照）。非特許文献１に記載された方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元することなく、加減算、定数加算、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。【０００３】
アクセスした位置iを明かすことなく、配列のi番目のデータの読み込みや配列のi番目のデータへの値dの書き込みを行う場合、すべての要素に対してアクセスしたように見せかけることがよく行われる（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克巳、“軽量検証可能3パーティ秘匿関数計算の再考”、CSS、2010年
【非特許文献２】Marcel Keller and Peter Scholl, "Efficient, oblivious data structures for MPC", Advances in Cryptology - ASIACRYPT 2014, Vol. 8874 of Lecture Notes in Computer Science, pp. 506-525, 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献２に記載された従来技術は、定数段の通信で大きさnの配列へデータの読み込みや書き込みを行うのに通信量Ω(n)が必要であった。【０００６】
この発明の目的は、上記のような点に鑑みて、定数段の通信でアクセスした位置を明かすことなく行う配列に対するデータ読み込みやデータ書き込みを従来よりも少ない通信量で効率よく行うことを可能とすることである。
【課題を解決するための手段】
【０００７】
上記の課題を解決するために、この発明の秘密読み書き装置は、大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …,[a[n-1]])とアクセス位置xの秘匿文[x]とを含む読み込み命令、もしくは、秘匿文の配列[a]と秘匿文[x]と書き込む値dの秘匿文[d]とを含む書き込み命令を入力とし、読み込み命令が入力されたときは秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]を出力し、書き込み命令が入力されたときは秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]に秘匿文[d]を加算する秘密読み書き装置であって、２個の秘匿文のベクトル[b0], [b1]からなる書き込みバッファ[b]=([b0], [b1])を記憶するバッファ記憶部と、書き込み命令が入力されたとき、秘匿文のベクトル[b0]へ秘匿文[x]を追加し、秘匿文のベクトル[b1]へ秘匿文[d]を追加するバッファ追加部と、書き込みバッファ[b]の要素数が所定の値を超えたとき、秘匿文の配列[a]のうち秘匿文のベクトル[b0]が示すアクセス位置へ秘匿文のベクトル[b1]が示す値を加算する秘密書き込み部と、読み込み命令が入力されたとき、秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を読み込む秘密読み込み部と、秘匿文のベクトル[b1]の要素のうち秘匿文のベクトル[b0]が示すアクセス位置が秘匿文[x]が示すアクセス位置と等しい要素の総和である未反映値cの秘匿文[c]を秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]へ加算するバッファ加算部と、を含む。
【発明の効果】
【０００８】
この発明の秘密読み書き技術によれば、定数段の通信でアクセスした位置を明かすことなく行う配列に対するデータ読み込みやデータ書き込みを従来よりも少ない通信量で効率よく行うことが可能となる。
【図面の簡単な説明】
【０００９】
【図１】図１は、秘密読み書き装置の機能構成を例示する図である。
【図２】図２は、秘密読み書き方法の処理手続きを例示する図である。
【図３】図３は、秘密読み込み部の処理手続きを例示する図である。
【図４】図４は、秘密書き込み部の処理手続きを例示する図である。
【発明を実施するための形態】
【００１０】
実施形態の説明に先立ち、この明細書における表記方法および用語の定義について説明する。
【００１１】
＜表記方法＞
ある値aを暗号化や秘密分散などにより秘匿化した値をaの秘匿文と呼び、[a]と表記する。また、aを[a]の平文と呼ぶ。秘匿化が秘密分散である場合は、[a]により各秘密計算装置が持つ秘密分散の断片の集合を参照する。ベクトルa=(a0, a1, …)のi番目の要素をa[i]により参照する。ベクトルaとベクトルbの結合をa||bと表記する。ベクトルaの要素の数を|a|と表記する。実数xの絶対値を|x|と表記する。
【００１２】
【数１】
2019059069.tif 000003
【００１３】
は床関数であり、実数x以下の最大の整数を表す。
【００１４】
【数２】
2019059069.tif 000004
【００１５】
は天井関数であり、実数x以上の最小の整数を表す。
【００１６】
＜加算、減算、乗算＞
秘匿文に対する加算、減算、乗算の各演算は、２つの値a, bの秘匿文[a], [b]を入力とし、それぞれa+b, a-b, abの計算結果c1, c2, c3の秘匿文[c1], [c2], [c3]を計算する。これらの演算の実行をそれぞれ次式のように記述する。
【００１７】
【数３】
2019059069.tif 000005
【００１８】
誤解を招く恐れのない場合は、Add([a], [b]), Sub([a], [b]), Mul([a], [b])をそれぞれ[a]+[b], [a]-[b], [a][b]と略記する。
【００１９】
＜等号判定＞
２つの値a, bの秘匿文[a], [b]を入力とし、a=bならばc=1、a≠bならばc=0となる秘匿文[c]を計算する処理を次式のように記述する。
【００２０】
【数４】
2019059069.tif 000006
【００２１】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２２】
実施形態の秘密読み書き装置１は、図１に例示するように、バッファ記憶部１０、命令判断部１１、秘密読み込み部１２、バッファ加算部１３、バッファ追加部１４、および秘密書き込み部１５を含む。この秘密読み書き装置１が、図２に例示する各ステップの処理を行うことにより実施形態の秘密読み書き方法が実現される。
【００２３】
秘密読み書き装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密読み書き装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密読み書き装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密読み書き装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００２４】
以下、図２を参照して、実施形態の秘密読み書き装置１が実行する秘密読み書き方法について説明する。
【００２５】
バッファ記憶部１０には、入力された書き込み命令を保持しておくための書き込みバッファ[b]=([b0], [b1])が記憶されている。[b0]はアクセス位置の秘匿文のベクトル[b0]=([b0[0]], [b0[1]], …,[b0[m-1]])である。[b1]は書き込む値の秘匿文のベクトル[b1]=([b1[0]], [b1[1]], …,[b1[m-1]])である。ただし、mは書き込みバッファ[b]の要素数であり、m=|[b]|である。
【００２６】
ステップＳ１−１において、命令判断部１１は、読み込み命令もしくは書き込み命令を入力として受け取る。読み込み命令は、大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …, [a[n-1]])とアクセス位置xの秘匿文[x]とを含む。書き込み命令は、大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …, [a[n-1]])とアクセス位置xの秘匿文[x]と書き込む値dの秘匿文[d]とを含む。
【００２７】
ステップＳ１−２において、命令判断部１１は、入力が読み込み命令であれば、秘匿文の配列[a]とアクセス位置の秘匿文[x]とを秘密読み込み部１２へ出力し、ステップＳ２へ処理を進める。また、入力が書き込み命令であれば、秘匿文の配列[a]とアクセス位置の秘匿文[x]と書き込む値の秘匿文[d]とをバッファ追加部１４へ出力し、ステップＳ４−１へ処理を進める。
【００２８】
ステップＳ２において、秘密読み込み部１２は、アクセス位置xを秘匿したまま秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を読み込む。アクセス位置を秘匿したまま配列から要素を読み込む方法は、例えば、非特許文献２に記載されている方法を用いることができる。また、後述する秘密読み込み方法を用いれば、より効率よく読み込みを行うことができる。秘密読み込み部１２は、読み出した配列[a]のx番目の要素である秘匿文[a[x]]をバッファ加算部１３へ出力する。
【００２９】
ステップＳ３−１において、バッファ加算部１３は、バッファ記憶部１０に記憶されている書き込みバッファ[b]を用いて未反映の値cの秘匿文[c]を計算する。具体的には、式（１）により秘匿文[c]を計算する。
【００３０】
【数５】
2019059069.tif 000007
【００３１】
もしくは、式（２）により未反映の値cの秘匿文[c]を計算する。
【００３２】
【数６】
2019059069.tif 000008
【００３３】
ステップＳ３−２において、バッファ加算部１３は、秘密読み込み部１２が出力した配列[a]のx番目の要素である秘匿文[a[x]]に未反映の値cの秘匿文[c]を加算して、秘匿文[a[x]]+[c]を配列[a]のx番目の要素である秘匿文[a[x]]として秘密読み書き装置１の出力とする。
【００３４】
ステップＳ４−１において、バッファ追加部１４は、バッファ記憶部１０に記憶されている書き込みバッファ[b]へアクセス位置の秘匿文[x]と書き込む値の秘匿文[d]とを追加する。具体的には、m=|[b]|とし、[b[m]]=([b0[m]], [b1[m]])=([x], [d])とする。
【００３５】
ステップＳ４−２において、バッファ追加部１４は、書き込みバッファ[b]の要素数|[b]|が√nを超えているか否かを判定する。書き込みバッファ[b]の要素数|[b]|が√nを超えている場合（すなわち、|[b]|>√n）はステップＳ５へ処理を進める。また、書き込みバッファ[b]の要素数|[b]|が√n以下の場合（すなわち、|[b]|≦√n）は処理を終了する。
【００３６】
ステップＳ５において、秘密書き込み部１５は、書き込みバッファ[b]に記憶されているアクセス位置の秘匿文のベクトル[b0]=([b0[0]], [b0[1]], …, [b0[m-1]])と書き込む値の秘匿文のベクトル[b1]=([b1[0]], [b1[1]], …, [b1[m-1]])とを用いて、アクセス位置xを秘匿したまま書き込む値の秘匿文[d]を配列のx番目の要素である秘匿文a[x]へ加算する。アクセス位置を秘匿したまま配列へ値を書き込む方法は、例えば、非特許文献２に記載されている方法を用いることができる。また、後述する秘密書き込み方法を用いれば、より効率よく書き込みを行うことができる。
【００３７】
以下、図３を参照して、秘密読み込み部１２が効率よく配列からのデータ読み込みを行う方法について説明する。
【００３８】
ステップＳ１２−１において、秘密読み込み部１２は、大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …, [a[n-1]])とアクセス位置xの秘匿文[x]とを入力として受け取る。
【００３９】
ステップＳ１２−２において、秘密読み込み部１２は、k個の秘匿文のベクトル[vj]を作成する。ただし、kは2以上の整数であり、jは1以上k以下の各整数である。具体的には、m1, m2, …, mkをn≦m1×m2×…×mkを満たす自然数とし、各整数jについて、xjを式（３）で定義される整数とし、(xjmod mj)番目の要素が1であり、他の要素が0である、大きさmjの秘匿文のベクトル[vj]を作成する。
【００４０】
【数７】
2019059069.tif 000009
【００４１】
特に、入力される各秘匿文が、(t, s)Shamir秘密分散によるシェアであれば、k, mi（i=1, 2, …, k）を式（４）とすることができる。なお、(t, s)Shamir秘密分散とは、入力された平文をs個に分割した分散値をs個の秘密計算装置に分散して保持しておき、任意のt個のシェアが揃えば平文を復元でき、t個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。このとき、tは1以上の整数であり、s≧2t-1である。
【００４２】
【数８】
2019059069.tif 000010
【００４３】
ステップＳ１２−３−１において、秘密読み込み部１２は、jを1に初期化する。
【００４４】
ステップＳ１２−３−２において、秘密読み込み部１２は、秘匿文の配列[aj-1]を用いてnj個の秘匿文のベクトル[bj,i]を作成する。このとき、秘匿文の配列[a]=([a[0]], [a[1]], …, [a[n-1]])は、秘匿文の配列[a0]=([a0[0]], [a0[1]], …, [a0[n-1]])として扱う。作成する秘匿文のベクトル[bj,i]の数njは、jの値により異なる。具体的には、njを式（５）で定義される整数とし、iを0以上nj未満の各整数とし、[bj,i]=([aj-1[mji+0]],[aj-1[mji+1]], …, [aj-1[mji+mj-1]])（ただし、λ≧|aj-1|のとき[aj-1[λ]]=0）として、秘匿文のベクトル[bj,j]を計算する。
【００４５】
【数９】
2019059069.tif 000011
【００４６】
ステップＳ１２−３−３において、秘密読み込み部１２は、秘匿文のベクトル[bj,j]と秘匿文のベクトル[vj]との内積を第i要素とする秘匿文の配列[aj]を計算する。
【００４７】
ステップＳ１２−３−４において、秘密読み込み部１２は、j+1がk以下（j+1≦k）であるか否かを判定し、j+1がk以下であれば、jをインクリメント（j←j+1）してステップＳ１２−３−２へ処理を戻し、j+1がkより大きければ（j+1>k）、秘匿文の配列[ak]を出力する。なお、このとき、秘匿文の配列[ak]は要素数が１の配列となっている。
【００４８】
ステップＳ１２−４において、秘密読み込み部１２は、要素数が１の秘匿文の配列[ak]を秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]として出力する。
【００４９】
以下、図４を参照して、秘密書き込み部１５が効率よく配列へデータ書き込みを行う方法について説明する。
【００５０】
ステップＳ１５−１において、秘密書き込み部１５は、大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …, [a[n-1]])と、アクセス位置の秘匿文のベクトル[b0]と、書き込む値の秘匿文のベクトル[b1]とを入力として受け取る。以下、アクセス位置の秘匿文のベクトル[b0]は秘匿文[xi]、書き込む値の秘匿文のベクトル[b1]は秘匿文[yi]として扱う。ただし、mを書き込みバッファ[b]の要素数|[b]|とし、iは0以上m未満の各整数である。
【００５１】
ステップＳ１５−２において、秘密書き込み部１５は、各値yiの書き込み先番地xiを表現する秘匿文のベクトル[wi]を作成する。具体的には、n1, n2をn1n2≧nを満たす自然数とし、pi[λ1]qi[λ2]が、n2λ1+λ2=xiのとき[yi]となり、他のときは0となる秘匿文のベクトル[pi], [qi]を作成し、その秘匿文のベクトル[pi], [qi]を結合して、秘匿文のベクトル[wi]=[pi]||[qi]を生成する。このとき、秘匿文のベクトル[pi]は、
【００５２】
【数１０】
2019059069.tif 000012
【００５３】
の要素が1であり、他の要素が0である大きさn1の秘匿文のベクトルとし、秘匿文のベクトル[qi]は、
【００５４】
【数１１】
2019059069.tif 000013
【００５５】
の要素が[yi]であり、他の要素が0である大きさn2の秘匿文のベクトルとしてもよい。
【００５６】
特に、入力される各秘匿文が、(t, s)Shamir秘密分散によるシェアであれば、n1, n2は、式（６）とすることができる。なお、(t, s)Shamir秘密分散とは、入力された平文をs個に分割した分散値をs個の秘密計算装置に分散して保持しておき、任意のt個のシェアが揃えば平文を復元でき、t個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。このとき、tは1以上の整数であり、s≧2t-1である。
【００５７】
【数１２】
2019059069.tif 000014
【００５８】
ステップＳ１５−３において、秘密書き込み部１５は、jを0以上n未満の各整数とし、秘匿文のベクトル[wi]から要素を選択して秘匿文のベクトル[uj], [vj]を生成する。具体的には、iを0以上m未満の各整数とし、jを0以上n未満の各整数とし、λ1, λ2を式（７）とし、
【００５９】
【数１３】
2019059069.tif 000015
【００６０】
式（８）のようにして秘匿文のベクトル[uj], [vj]を生成する。
【００６１】
【数１４】
2019059069.tif 000016
【００６２】
ステップＳ１５−４において、秘密書き込み部１５は、jを0以上n未満の各整数とし、秘匿文のベクトル[uj]と秘匿文のベクトル[vj]との内積を秘匿文の配列[a]のj番目の要素[a[j]]に加算する。
【００６３】
この発明は、バッファからの読み込みはバッファサイズに線形の通信量でできることと、秘密書き込み方法がバッファサイズO(√n)のときはO(n)の通信量でできることを利用することがポイントである。バッファサイズが√nを超えるまで実際の書き込みを保留することで、読み込みは必ずO(√n)の通信量で、書き込みは各回O(√n)に加えて１回だけO(n)の通信量で実現することができる。
【００６４】
以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６５】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００６６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６７】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019059069.tif 000019
【図２】
2019059069.tif 000020
【図３】
2019059069.tif 000021
【図４】
2019059069.tif 000022
【手続補正書】
【提出日】令和2年3月3日(2020.3.3)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
【数６】
2019059069.tif 000023
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
ステップＳ１５−２において、秘密書き込み部１５は、各値yiの書き込み番地xiを表現する秘匿文のベクトル[wi]を作成する。具体的には、n1, n2をn1n2≧nを満たす自然数とし、pi[λ1]qi[λ2]が、n2λ1+λ2=xiのとき[yi]となり、他のときは0となる秘匿文のベクトル[pi], [qi]を作成し、その秘匿文のベクトル[pi], [qi]を結合して、秘匿文のベクトル[wi]=[pi]||[qi]を生成する。このとき、秘匿文のベクトル[pi]は、
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …,[a[n-1]])とアクセス位置xの秘匿文[x]とを含む読み込み命令、もしくは、上記秘匿文の配列[a]と上記秘匿文[x]と書き込む値dの秘匿文[d]とを含む書き込み命令を入力とし、上記読み込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]を出力し、上記書き込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]に秘匿文[d]を加算する秘密読み書き装置であって、
２個の秘匿文のベクトル[b0], [b1]からなる書き込みバッファ[b]=([b0], [b1])を記憶するバッファ記憶部と、
上記書き込み命令が入力されたとき、上記秘匿文のベクトル[b0]へ上記秘匿文[x]を追加し、上記秘匿文のベクトル[b1]へ上記秘匿文[d]を追加するバッファ追加部と、
上記書き込みバッファ[b]の要素数が所定の値を超えたとき、上記秘匿文の配列[a]のうち上記秘匿文のベクトル[b0]が示すアクセス位置へ上記秘匿文のベクトル[b1]が示す値を加算する秘密書き込み部と、
上記読み込み命令が入力されたとき、上記秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を読み込む秘密読み込み部と、
上記秘匿文のベクトル[b1]の要素のうち上記秘匿文のベクトル[b0]が示すアクセス位置が上記秘匿文[x]が示すアクセス位置と等しい要素の総和である未反映値cの秘匿文[c]を上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]へ加算するバッファ加算部と、
を含む秘密読み書き装置。
【請求項２】
請求項１に記載の秘密読み書き装置であって、
上記バッファ加算部は、次式により上記未反映値cの秘匿文[c]を計算するものである、
【数１５】
2019059069.tif 000024
秘密読み書き装置。
【請求項３】
請求項１に記載の秘密読み書き装置であって、
上記バッファ加算部は、次式により上記未反映値cの秘匿文[c]を計算するものである、
【数１６】
2019059069.tif 000025
秘密読み書き装置。
【請求項４】
請求項１に記載の秘密読み書き装置であって、
上記秘匿文の配列[a]と上記秘匿文[x]と上記秘匿文[d]は、tを1以上の整数とし、s≧2t-1とし、平文をs個に分割したシェアのうち、任意のt個のシェアが揃えば平文を復元でき、t個未満のシェアからは平文に関する一切の情報を得られない秘密分散により秘匿化したものであり、
上記秘密読み込み部は、上記秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を、アクセス位置xを明かすことなく読み込むものであり、
上記秘密書き込み部は、上記書き込みバッファの要素数が√nを超えたとき、上記秘匿文の配列[a]の上記秘匿文のベクトル[b0]が示すアクセス位置へ上記秘匿文のベクトル[b1]が示す値を、アクセス位置xを明かすことなく書き込むものである、
秘密読み書き装置。
【請求項５】
大きさnの秘匿文の配列[a]=([a[0]], [a[1]], …,[a[n-1]])とアクセス位置xの秘匿文[x]とを含む読み込み命令、もしくは、上記秘匿文の配列[a]と上記秘匿文[x]と書き込む値dの秘匿文[d]とを含む書き込み命令を入力とし、上記読み込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]を出力し、上記書き込み命令が入力されたときは上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]に秘匿文[d]を加算する秘密読み書き装置が実行する秘密読み書き方法であって、
バッファ記憶部に、２個の秘匿文のベクトル[b0], [b1]からなる書き込みバッファ[b]=([b0], [b1])が記憶されており、
バッファ追加部が、上記書き込み命令が入力されたとき、上記秘匿文のベクトル[b0]へ上記秘匿文[x]を追加し、上記秘匿文のベクトル[b1]へ上記秘匿文[d]を追加し、
秘密書き込み部が、上記書き込みバッファ[b]の要素数が所定の値を超えたとき、上記秘匿文の配列[a]のうち上記秘匿文のベクトル[b0]が示すアクセス位置へ上記秘匿文のベクトル[b1]が示す値を加算し、
秘密読み込み部が、上記読み込み命令が入力されたとき、上記秘匿文の配列[a]からx番目の要素である秘匿文[a[x]]を読み込み、
バッファ加算部が、上記秘匿文のベクトル[b1]の要素のうち上記秘匿文のベクトル[b0]が示すアクセス位置が上記秘匿文[x]が示すアクセス位置と等しい要素の総和である未反映値cの秘匿文[c]を上記秘匿文の配列[a]のx番目の要素である秘匿文[a[x]]へ加算する、
秘密読み書き方法。
【請求項６】
請求項１から４のいずれかに記載の秘密読み書き装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2019059069.tif 000026
2019059069.tif 000027
2019059069.tif 000028
2019059069.tif 000029