JP6534778B2 - 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム - Google Patents

Description

この発明は、暗号応用技術に関し、特に、入力データを明かすことなくフィッシャー正確検定（Fisher's exact test）を計算する技術に関する。

2×2の分割表として与えられた説明変数と目的変数との関連の有無に関して仮説検定を行う統計学的検定法の一つとして、フィッシャーの正確検定が広く知られている。非特許文献１には、フィッシャー正確検定の利用例として、ゲノムワイド関連解析（GWAS: Genome-Wide Association Study）が記載されている。

フィッシャー正確検定について説明する。次表はn人の被験者を変異の有無と特定の疾患の発症の有無で分類および数え上げした2×2分割表の例である。

表中のa, b, c, dは度数を、n_1●, n_2●, n_●1, n_●2は小計を表し、n_1●=a+b, n_2●=c+d, n_●1=a+c, n_●2=b+dである。a, b, c, d, n_1●, n_2●, n_●1, n_●2はすべて非負整数である。

このとき、非負整数iについて、式（１）で定義される確率p_iを計算し、式（２）に示す確率の和pと、有意水準と呼ばれる所定の値αとの大小関係により、説明変数（上表の例では変異の有無）と目的変数（上表の例では疾患の有無）との関連の有無を調査する。ここで、p_aは実際の集計値であるa, b, c, dを度数とする分割表について式（１）により算出した確率値である。

暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば非特許文献２参照）。非特許文献２の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元すること無く、加減算、定数加算、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。

ゲノム情報の機微性や機密性から、ゲノム情報を暗号技術によって秘匿しつつゲノムワイド関連解析を行う先行研究がある（例えば非特許文献３参照）。非特許文献３ではゲノム情報を秘匿しつつカイ二乗検定を行う方法が提案されている。

Konrad Karczewski, "How to do a GWAS", Lecture note in GENE 210: Genomics and Personalized Medicine, 2015. 千田浩司、濱田浩気、五十嵐大、高橋克巳、"軽量検証可能3パーティ秘匿関数計算の再考"、CSS2010、2010 Yihua Zhang, Marina Blanton, and Ghada Almashaqbeh, "Secure distributed genome analysis for gwas and sequence comparison computation", BMC medical informatics and decision making, Vol. 15, No. Suppl 5, p. S4, 2015.

フィッシャー正確検定で各確率p_iを計算する際には、x!やlog(x!)などの同じ計算が多数現れる。この計算を関数f(x)として、関数f(x)の計算結果…, f(-1), f(0), f(1), f(2), …をあらかじめ計算しておいて、必要に応じて計算結果の値を参照することで効率化することができる。しかしながら、従来技術はa_i=a+i, b_i=b-i, c_i=c-i, d_i=d+iとして、f(a+b), f(c+d), f(a+c), f(b+d), f(a+b+c+d), f(a_i), f(b_i), f(c_i), f(d_i)を計算する際に計算結果の値をm種類、計算する確率p_iをn種類（すなわち、i=0, …, n-1）とすると、大きさmの表の参照を4n+5回行う必要があった。特に、秘密計算でこれを実現しようとする場合、大きさmの表の参照にO(m)の計算量を要するため、全体の計算量がO(mn)となっていた。

この発明の秘密計算技術は、上述のような点に鑑みて、フィッシャー正確検定を秘密計算により効率よく計算することを目的とする。

上記の課題を解決するために、この発明の秘密計算システムは、3台以上の秘密計算装置を含む秘密計算システムであって、秘密計算装置は、a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを分割表における第1行第2列の度数とし、cを分割表における第2行第1列の度数とし、dを分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j₀, …, j_m-1)は大きさnの配列の秘匿文<α>=(<α[0]>,<α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j₀mod n]>, …, <α[β+j_m-1 mod n]>)を生成する関数を表し、i₀≦i₁, x₀≦x₁を満たすi₀, i₁, x₀, x₁を決定する計算範囲決定部と、任意の関数f(x)について、f(x₀), …, f(x₁)を計算し、配列M=(f(x₀), …, f(x₁))を生成する事前計算部と、配列Mを秘匿化して秘匿文の配列<M>=(<f(x₀)>, …, <f(x₁)>)を生成する秘匿化部と、次式を実行して、関数値の秘匿文(<f(a_i)>, <f(b_i)>, <f(c_i)>, <f(d_i)>)（i₀≦i≦i₁）を生成する一括読み込み部と、を含むものである。

この発明によれば、フィッシャー正確検定の入力となる分割表の度数a, b, c, dを明かすことなく、計算対象となる度数の関数値f(a_i), f(b_i), f(c_i), f(d_i)を効率よく求めることができる。したがって、フィッシャー正確検定を秘密計算により効率よく計算することができる。さらには、ゲノム情報を秘匿しつつフィッシャー正確検定を実行することができる。これは例えば、複数の研究機関が所持するゲノムデータを秘匿したまま相互に開示することなく、統合されたデータのフィッシャー正確検定の実行結果を得ることができ、極めてセキュリティレベルの高いゲノム解析の実行環境の提供、ひいては医療の更なる発展へとつながることが期待できる。

図１は、秘密計算システムの機能構成を例示する図である。 図２は、秘密計算装置の機能構成を例示する図である。 図３は、秘密計算方法の処理手続きを例示する図である。

実施形態の説明に先立ち、この明細書における表記方法およびこの明細書において用いる用語の定義について説明する。

＜表記方法＞
ある値aを暗号化や秘密分散などにより秘匿化した値をaの秘匿文と呼び、<a>と表記する。また、aを<a>の平文と呼ぶ。秘匿化が秘密分散である場合は、<a>により各パーティが持つ秘密分散の断片の集合を参照する。

＜秘匿シフト＞
大きさnの秘匿文の配列<a>=(<a[0]>, <a[1]>, …, <a[n-1]>)とシフト量dの秘匿文<d>とを入力とし、<a>を左にdだけシフトした秘匿文の配列<a'>=(<a[d]>, <a[d+1]>, …, <a[n-1]>, <a[0]>, <a[1]>, …, <a[d-1]>)を計算する処理を秘匿シフトと呼び、次式で記述する。

秘匿シフトを実現する方法は、下記参考文献１に記載されている。
〔参考文献１〕濱田浩気、桐淵直人、五十嵐大、“ラウンド効率のよい秘密計算パターンマッチング”、コンピュータセキュリティシンポジウム2014論文集、第2014巻、pp. 674-681、2014年10月

＜一括読み込みアルゴリズム＞
一括読み込みアルゴリズムは、大きさnの秘匿文の配列<a>=(<a[0]>, <a[1]>, …, <a[n-1]>)、位置を表す自然数xの秘匿文<x>、およびxからの相対的な位置を表すm個の平文j₀,j₁, …, j_m-1を入力とし、xやa[0], a[1], …, a[n-1]の値を明らかにすることなく、m個の秘匿文<b>=(<a[x+j₀ mod n]>, <a[x+j₁ mod n]>, …, <a[x+j_m-1mod n]>)を得る方法である。以下、一括読み込みアルゴリズムは次式で記述する。

一括読み込みアルゴリズムは上記の秘匿シフトを用いて以下のように実装することで、より効率的に実行することができる。ただし、この発明で適用可能な一括読み込みアルゴリズムはこれに限定されず、上述の入出力を実現することができるアルゴリズムであればどのようなものであってもよい。まず、大きさnの秘匿文の配列<a>=(<a[0]>, <a[1]>, …, <a[n-1]>)、位置を表す0以上n未満の整数xの秘匿文<x>、およびxからの相対的な位置を表すm個の平文j₀, …, j_m-1が入力される。次に、<a'>←Shift(<a>, <x>)により、配列<a>を<x>だけ左シフトした配列<a'>=(<a'[0]>, <a'[1]>, …, <a'[n-1]>)を得る。そして、<b[k]>=<a'[j_k]>（0≦k<m）として、秘匿文の配列<b>=(<b[0]>, <b[1]>, …, <b[m-1]>)=(<a'[j₀]>, <a'[j₁]>, …, <a'[j_m-1]>)を生成する。

以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

＜第一実施形態＞
第一実施形態の秘密計算システムは、図１に例示するように、n（≧3）台の秘密計算装置１₁, …, １_nを含む。この実施形態では、秘密計算装置１₁, …, １_nはそれぞれ通信網２へ接続される。通信網２は、秘密計算装置１₁, …, １_nそれぞれが相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密計算装置１_i（i∈{1, …, n}）へ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで入力するように構成してもよい。

秘密計算装置１は、図２に例示するように、入力部１１、計算範囲決定部１２、事前計算部１３、秘匿化部１４、一括読み込み部１５、および出力部１６を含む。この秘密計算装置１が、図３に例示する各ステップの処理を行うことにより第一実施形態の秘密計算方法が実現される。

秘密計算装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密計算装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密計算装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密計算装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。

図３を参照して、第一実施形態の秘密計算方法の処理手続きを説明する。

ステップＳ１１において、入力部１１へ、2×2分割表の度数の組(a, b, c, d)の秘匿文(<a>, <b>, <c>, <d>)が入力される。ここで、2×2分割表は次表で定義され、a, b, c, dは非負整数である。

ステップＳ１２において、計算範囲決定部１２は、i₀≦i₁, x₀≦x₁を満たす値i₀, i₁, x₀, x₁を決定する。ここでは、i₀=-n, i₁=n, x₀=-n, x₁=2nと決定するものとする。値x₀,x₁は事前計算部１３へ送られる。値i₀, i₁は一括読み込み部１５へ送られる。

ステップＳ１３において、事前計算部１３は、関数f(x)について、f(x₀), f(x₀+1),…,f(x₁)を計算し、配列M=(f(x₀), f(x₀+1),…, f(x₁))を生成する。第一実施形態では、次式で定義される確率p_i（i₀≦i≦i₁）を計算するために、関数f(x)はf(x):=x!とする。

ステップＳ１４において、秘匿化部１４は、配列Mを秘匿化した秘匿文の配列<M>=(<f(x₀)>, <f(x₀+1)>, …, <f(x₁)>)を生成する。秘匿文の配列<M>は一括読み込み部１５へ送られる。

ステップＳ１５において、一括読み込み部１５は、次式を実行して、関数値の秘匿文(<f(a_i)>, <f(b_i)>, <f(c_i)>, <f(d_i)>)（i=i₀, …, i₁）を生成する。

ステップＳ１６において、出力部１６から、関数値の秘匿文(<f(a_i)>, <f(b_i)>, <f(c_i)>, <f(d_i)>)が出力される。

＜第二実施形態＞
図３を参照して、第二実施形態の秘密計算方法の処理手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。

ステップＳ１３において、事前計算部１３は、関数f(x)について、f(x₀), f(x₀+1),…,f(x₁)を計算し、配列M=(f(x₀), f(x₀+1),…, f(x₁))を生成する。第二実施形態では、次式で定義される確率log p_i（i₀≦i≦i₁）を計算した後に確率p_i=exp(log p_i)を計算するために、関数f(x)はf(x):=log(x!)とする。

この発明のポイントは、関数値f(a_i0), f(a_i0+1), …, f(a_i1)の入力a_i0, a_i0+1, …, a_i1の差が公開してもよい情報であることを利用して、関数値の秘匿文<f(a_i0)>, <f(a_i0+1)>, …, <f(a_i1)>の計算を、一括読み込みアルゴリズムを使って効率よく実現することである。

このように構成することにより、この発明の秘密計算技術によれば、複数の表参照を一括で実行することにより、フィッシャー正確検定を秘密計算で効率的に計算できる。大きさnの配列からの一括読み込みがO(n)の計算量であるので、1+i₁-i₀=K, 1+x₁-x₀=Lとして、全体の計算量がO(KL)からO(L)に改善される。

以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。

［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

この発明の秘密計算技術は、例えば、機微情報を取り扱うゲノムワイド関連解析において、ゲノム情報を秘匿したまま秘密計算によりフィッシャー正確検定を行うことに適用することが可能である。

Claims (6)

1. 3台以上の秘密計算装置を含む秘密計算システムであって、
   上記秘密計算装置は、
   a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを上記分割表における第1行第2列の度数とし、cを上記分割表における第2行第1列の度数とし、dを上記分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j₀, …, j_m-1)は大きさnの配列の秘匿文<α>=(<α[0]>, <α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j₀mod n]>, …, <α[β+j_m-1 mod n]>)を生成する関数を表し、
   i₀≦i₁, x₀≦x₁を満たすi₀, i₁, x₀, x₁を決定する計算範囲決定部と、
   任意の関数f(x)について、f(x₀), …, f(x₁)を計算し、配列M=(f(x₀), …, f(x₁))を生成する事前計算部と、
   上記配列Mを秘匿化して秘匿文の配列<M>=(<f(x₀)>, …, <f(x₁)>)を生成する秘匿化部と、
   次式を実行して、関数値の秘匿文(<f(a_i)>, <f(b_i)>, <f(c_i)>, <f(d_i)>)（i₀≦i≦i₁）を生成する一括読み込み部と、
   

   

   
   を含むものである秘密計算システム。
2. 請求項１に記載の秘密計算システムであって、
   上記事前計算部は、上記関数f(x)をf(x):=x!として、次式で定義される確率p_i（i₀≦i≦i₁）を計算するためにf(x₀), …, f(x₁)を計算するものである、
   

   

   
   秘密計算システム。
3. 請求項１に記載の秘密計算システムであって、
   上記事前計算部は、上記関数f(x)をf(x):=log(x!)として、次式で定義されるlog p_i（i₀≦i≦i₁）を計算した後に確率p_i=exp(log p_i)を計算するためにf(x₀), …, f(x₁)を計算するものである、
   

   

   
   秘密計算システム。
4. a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを上記分割表における第1行第2列の度数とし、cを上記分割表における第2行第1列の度数とし、dを上記分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j₀, …, j_m-1)は大きさnの配列の秘匿文<α>=(<α[0]>, <α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j₀mod n]>, …, <α[β+j_m-1 mod n]>)を生成する関数を表し、
   i₀≦i₁, x₀≦x₁を満たすi₀, i₁, x₀, x₁を決定する計算範囲決定部と、
   任意の関数f(x)について、f(x₀), …, f(x₁)を計算し、配列M=(f(x₀), …, f(x₁))を生成する事前計算部と、
   上記配列Mを秘匿化して秘匿文の配列<M>=(<f(x₀)>, …, <f(x₁)>)を生成する秘匿化部と、
   次式を実行して、関数値の秘匿文(<f(a_i)>, <f(b_i)>, <f(c_i)>, <f(d_i)>)（i₀≦i≦i₁）を生成する一括読み込み部と、
   

   

   
   を含む秘密計算装置。
5. a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを上記分割表における第1行第2列の度数とし、cを上記分割表における第2行第1列の度数とし、dを上記分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j₀, …, j_m-1)は大きさnの配列の秘匿文<α>=(<α[0]>, <α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j₀mod n]>, …, <α[β+j_m-1 mod n]>)を生成する関数を表し、
   計算範囲決定部が、i₀≦i₁, x₀≦x₁を満たすi₀, i₁, x₀, x₁を決定し、
   事前計算部が、任意の関数f(x)について、f(x₀), …, f(x₁)を計算し、配列M=(f(x₀), …, f(x₁))を生成し、
   秘匿化部が、上記配列Mを秘匿化して秘匿文の配列<M>=(<f(x₀)>, …, <f(x₁)>)を生成し、
   一括読み込み部が、次式を実行して、関数値の秘匿文(<f(a_i)>, <f(b_i)>, <f(c_i)>, <f(d_i)>)（i₀≦i≦i₁）を生成する、
   

   

   
   秘密計算方法。
6. 請求項４に記載の秘密計算装置としてコンピュータを機能させるためのプログラム。

Images