一般誕生日問題 k-sum を解くための k-tree アルゴリズム

サンプル お知らせ
Table of Content

はじめに

この記事では、一般化された誕生日問題である k-sum 問題を解くための k-tree アルゴリズムを紹介します。まず、この記事で多用する排他的論理和の性質と記号の定義を挙げ、k=4のときの k-sum 問題と k-tree アルゴリズムについて述べます。最後に、一般的な k-tree アルゴリズムについて述べます。

排他的論理和の性質と記号の定義

  • a\oplus b = 0ならば a = b

  • a \oplus b \oplus ... のように複数個の排他的論理和をとる場合、a, b, ... の中で 1 であるものの個数が奇数個ならば結果は 1、偶数個ならば 0 となる。

  • list S,listT に対し S \triangleright\triangleleft TS,T の共通要素から成る list である。

  • low_l(x)x の最下位 l ビットとする。

  • L_1\triangleright \triangleleft_l L_2L_1 \times L_2 から最下位 l ビットが一致する全てのペアを含む list である。

  • x_1 \oplus x_2 = x_3 \oplus x_4 ならば x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0

k=4 の k-sum 問題

x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0 となるような x_1,x_2,x_3,x_4list を見つける。

k-tree アルゴリズムによる解法

L_1,L_2,L_3,L_4 は要素をそれぞれ 2^l 個含む list とする。

low_l(x_1 \oplus x_2)=0 となるような x_1 \oplus x_2list である L_{12} を作る。同様に low_l(x_3 \oplus x_4)=0 となるような x_3 \oplus x_4list である L_{34} を作る。

性質

x_1 \oplus x_2 = x_3 \oplus x_4 ならば x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0

より

L_{12}L_{34} から x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0 となるような x_1,x_2,x_3,x_4list を見つけられる。

計算量について

low_l(x_1 \oplus x_2)=0 となるような確率は 1/2^l

E[|L_{12}|]=|L_1|\times|L_2|\div2^l=2^{2l}\div2^l=2^l

同様にL_{34}のサイズも2^l

性質

low_l(x_1 \oplus x_2)=0 かつ low_l(x_3 \oplus x_4)=0 ならば 
low_l(x_1 \oplus x_2 \oplus x_3 \oplus x_4)=0 となる確率は 2^l/2^n

より、
L_{12}L_{34} の共通要素の個数は |L_{12}|\times|L_{34}|\div 2^{n-l} と見積もれる。

ここで |L_{12}|\times|L_{34}|\div 2^{n-l}= 2^l ×2^l \div 2^{n-l} =2^{3l-n} より
l \ge n / 3(逆だと確率が1を超えてしまうから)

手順の始まりに l = n / 3 とすると、k=4 の birthday problem を自明でない確率で解けることになる。

一般的な k に対する k-tree アルゴリズム

  • k が 2 の累乗の時
    k=4 のアルゴリズムで用いた、list の分割を \log_2k 回行って同様の操作を行えば良い。(以下、\log_2k=lgk と表す。) O(k・2^{n/(1+lgk)}) 時間で解ける。

  • k が 2 の累乗ではない時
    k' = 2^{\lfloor lg k \rfloor} として list 分割を行えば良い。ただし、k = 2^i+j の場合は、k = 2^i の場合よりも基本的に速く解くことは出来ない。

α 個の解を見つけるためにかかる計算量

α \le 2^{n/(\lfloor lgk \rfloor(\lfloor 1+lgk \rfloor)} の場合、 α 個の解を見つけるには、計算量は α 倍になる。

まとめ

[2] はこの k-tree アルゴリズムを用いた一部のマルチシグへの攻撃を論じたホワイトペーパーなので、興味のある方は是非ご覧下さい。

参考文献

[1] https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf
[2] https://eprint.iacr.org/2018/417.pdf

タイトルとURLをコピーしました