Articles Comments

ちからの備忘録的日記 » secret share » しきい値型秘密分散法のバリエーションについて

しきい値型秘密分散法のバリエーションについて




最近、秘密分散法にはまってます。今日はしきい値型秘密分散法のバリエーションについて少し整理しておきます。

勉強に利用した論文は、こちら。

» 秘密分散法とそのバリエーション (符号と暗号の代数的数理) 山本 博資

しきい値型完全秘密分散法

(k, n) しきい値型秘密分散法ともいわれる。シェアの情報から1bitの情報も復元できない秘密分散法であることから、完全という名称が使われている。

シェアのファイルサイズが、秘密分散する元のファイルサイズ以上にとなり、全シェアのファイルサイズが元のファイルサイズのシェア数倍となり、効率が悪い。

たとえば、10MBのファイルを (3,4)で秘密分散すると、ひとつのシェアのサイズは10MB 以上となり、シェア全部で40MB以上となる。実用化する際に、秘密分散処理のオーバーヘッドに加えて、ファイルサイズ増大に伴うディスク容量、I/Oパフォーマンス問題が発生する。

従って、暗号化鍵などを小さなファイルの秘密分散に向いている。

しきい値ランプ型秘密分散法

(k, L, n) しきい値ランプ型秘密分散法ともいわれる。シェアのファイルサイズが元ファイルサイズ以上になるというしきい値型完全秘密分散法の欠点を改善するために考案された秘密分散法。k-L個のシェアからは全く情報を復元できないが、k-L+1個からk-1個の場合は、情報を少しは復元できる。

実用化されている秘密分散の実装では、ほとんどこちらの方式が利用されている。

まとめ

秘密分散法の実装にも種類があることがわかりました。シェアからは元の情報が一切わからないがファイルサイズが大きくなる完全型、シェアのサイズは小さくできるが特定の条件下において元の情報が一部復元できるランプ型の大きく2つに分類されます。

実際、shamir の多項式を用いた実装はマシンパワーがとても必要となり、実用化が難しいです。こういう状況にあるため、shamir の多項式に変わり、排他論理和(XOR) を使って秘密分散処理を高速化するという実装が増えています。

Related Posts Plugin for WordPress, Blogger...

Filed under: secret share · Tags: , ,

Leave a Reply

*