計算量理論的安全な秘密分散法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/06 17:03 UTC 版)
「秘密分散」の記事における「計算量理論的安全な秘密分散法」の解説
情報理論的安全な（完全な）秘密分散法の欠点は、n 個のシェアを保存するのに必要なストレージサイズが、秘密情報をそのまま保存する場合の n 倍になってしまうことである。また、シェアを秘密裏に送る際の通信量も同様である。例えば、秘密情報が1GBであり、シェア数が10のとき、10GBのデータを（10か所に分けて）保存しなければならない。秘密分散法の効率を大幅に改善する方法としては、安全性を計算量的なものに緩和させることが提案されている。 代表的な計算量理論的安全な秘密分散法は、Krawczykによる (t,n)-しきい値法である。この方式は、ラビンのIDA（Information Dispersal Algorithm） をシャミアのしきい値法と組み合わせてできている。秘密のデータは、まず何らかの共通鍵暗号で暗号化される。用いる暗号鍵はランダムに選ぶ。次に、暗号文をIDAで n 個の断片に分ける。IDAは、しきい値法と同様に n 個に分けた断片のうち t 個集まれば元のデータを復元できるが、しきい値法と違って各断片のサイズ（ビット長）は分ける前のデータの 1/t になる。例えば、しきい値が5のときは、各断片は元のデータの 1/5 である。最後に、暗号化に使った鍵をシャミアのしきい値法で分散する。各参加者には、しきい値法のシェア1つとIDAの断片1つを渡す。暗号鍵の各シェアは鍵と同じ長さであるが、通常、鍵の長さは16～20バイトと小さいため、参加者に必要なストレージサイズは、ほぼIDAの断片の分だけである。 関連したアプローチとして、AONT-RSと呼ばれるでは、IDAで処理するまでのステップとして、All-or-nothing transformを使っている。All-or-nothing transform は、しきい値未満のシェアでは、データを復号できないことが保証されている。
※この「計算量理論的安全な秘密分散法」の解説は、「秘密分散」の解説の一部です。
「計算量理論的安全な秘密分散法」を含む「秘密分散」の記事については、「秘密分散」の概要を参照ください。
- 計算量理論的安全な秘密分散法のページへのリンク
