巡回置換行列を用いずm次元数ベクトル空間を用いてXOR演算だけで構成可能な（2,2~m）-閾値秘密分散法

摘要

排他的論理和演算を用いた高速な（K, n）-閾値秘密分散法は栗原ら，藤井らによって独立に提案されている．彼らの方式はともにシェアのサイズが分散対象データのサイズに等しい理想的な方式であり，分散·復元時にXOR演算のみを用いるため非常に高速に処理できるメリットを持つ．一方で素数位数の巡回置換行列を用いて構成しているため，シェア数nは素数であるという制限があった．ここで分散対象データはn-1個に等分割されている．この制約に対しCSS2012にて素数pに対し，分散対象データをp-1個に等分割して（2，p+1）-閾値秘密分散法を一般的に構成する方法が提案された．本稿はさらにこれを拡張し，任意の2以上の整数mに対して分散対象データをm個に等分割して（2，2~m）-閾値秘密分散法の構成方法について提案する．提案方式の構成にはある条件を満たした基底を持つz_2上のm一次元数ベクトル空間が用いられる．ここで，構成に用いられる基底集合として2－伝播基底集合という新しい概念を定義する．さらに（2，2~m）-閾値秘密分散法の存在性を保証するために，2－伝播基底集合の存在性についても触れる．