Loading [MathJax]/extensions/tex2jax.js

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

サンプル お知らせ
Table of Contents

はじめに

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

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

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

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

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

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

  • L1lL2L_1\triangleright \triangleleft_l L_2L1×L2L_1 \times L_2 から最下位 ll ビットが一致する全てのペアを含む listlist である。

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

k=4 の k-sum 問題

x1x2x3x4=0x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0 となるような x1,x2,x3,x4x_1,x_2,x_3,x_4listlist を見つける。

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

L1,L2,L3,L4L_1,L_2,L_3,L_4 は要素をそれぞれ 2l2^l 個含む listlist とする。

lowl(x1x2)=0low_l(x_1 \oplus x_2)=0 となるような x1x2x_1 \oplus x_2listlist である L12L_{12} を作る。同様に lowl(x3x4)=0low_l(x_3 \oplus x_4)=0 となるような x3x4x_3 \oplus x_4listlist である L34L_{34} を作る。

性質

x1x2=x3x4x_1 \oplus x_2 = x_3 \oplus x_4 ならば x1x2x3x4=0x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0

より

L12L_{12}L34L_{34} から x1x2x3x4=0x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0 となるような x1,x2,x3,x4x_1,x_2,x_3,x_4listlist を見つけられる。

計算量について

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

E[L12]=L1×L2÷2l=22l÷2l=2lE[|L_{12}|]=|L_1|\times|L_2|\div2^l=2^{2l}\div2^l=2^l

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

性質

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

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

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

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

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

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

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

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

α2n/(lgk(1+lgk)α \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をコピーしました