プライバシー保護大規模データ分析を可能にする秘密分散ベース秘密計算手法の開発

当該年度は前年度に引き続き、correlated randomnessという乱数を事前計算で生成することを許す、CRモデルと呼ばれる２パーティ秘密計算における乱数長や通信量に関する理論研究を行い、以下の３つの成果を得た。１．前年度に行った、CRモデルのプロトコルの記述や安全性の特徴付けを用いて、入力空間が制限される場合のプロトコルにおける乱数長の削減可能性について考察した。具体的には、関数f: X×Y -> Zを安全に計算するプロトコルが与えられたとき、入力空間を制限したfの制限も元のプロトコルで安全に計算できるが、必要な乱数長や通信量を減らせる場合がある。本成果では、乱数空間にもとのプロトコルと制限された入力空間の情報からあるグラフ構造を導入することができ、かつその連続成分に対応する乱数だけを用いてもfの制限を安全に計算できることを示した。２．前年度に得られた、関数秘密分散と呼ばれる暗号技術の鍵長の下界の導出に関して、安全性を緩めた場合でも同様の下界が成立することを示した。具体的には、前年度はperfect securityと呼ばれる安全性のもとでの鍵長の下界が得られていたが、statistical securityと呼ばれる少し条件を緩めた安全性の下でも同様の下界を得られることを示した。３．CRモデルの２者間秘密計算において、通信量と通信回数が最適となるonline-optimalという性質を満たす場合、必要な乱数長が入力のビット長に対して指数サイズになる場合があることを示した。また、通信量のみが最適であっても必要な乱数長が指数サイズになる場合があることを示した。

当該年度は前年度に引き続き、correlated randomnessという乱数を事前計算で生成することを許す、CRモデルと呼ばれる２パーティ秘密計算における乱数長や通信量に関する理論研究を行い、以下の３つの成果を得た。１．前年度に行った、CRモデルのプロトコルの記述や安全性の特徴付けを用いて、入力空間が制限される場合のプロトコルにおける乱数長の削減可能性について考察した。具体的には、関数f: X×Y -> Zを安全に計算するプロトコルが与えられたとき、入力空間を制限したfの制限も元のプロトコルで安全に計算できるが、必要な乱数長や通信量を減らせる場合がある。本成果では、乱数空間にもとのプロトコルと制限された入力空間の情報からあるグラフ構造を導入することができ、かつその連続成分に対応する乱数だけを用いてもfの制限を安全に計算できることを示した。２．前年度に得られた、関数秘密分散と呼ばれる暗号技術の鍵長の下界の導出に関して、安全性を緩めた場合でも同様の下界が成立することを示した。具体的には、前年度はperfect securityと呼ばれる安全性のもとでの鍵長の下界が得られていたが、statistical securityと呼ばれる少し条件を緩めた安全性の下でも同様の下界を得られることを示した。３．CRモデルの２者間秘密計算において、通信量と通信回数が最適となるonline-optimalという性質を満たす場合、必要な乱数長が入力のビット長に対して指数サイズになる場合があることを示した。また、通信量のみが最適であっても必要な乱数長が指数サイズになる場合があることを示した。