はじめに
この記事では、一般化された誕生日問題である k-sum 問題を解くための k-tree アルゴリズムを紹介します。まず、この記事で多用する排他的論理和の性質と記号の定義を挙げ、k=4
のときの k-sum 問題と k-tree アルゴリズムについて述べます。最後に、一般的な k-tree アルゴリズムについて述べます。
排他的論理和の性質と記号の定義
-
a⊕b=0
ならば a=b
-
a⊕b⊕...
のように複数個の排他的論理和をとる場合、a,b,...
の中で 1
であるものの個数が奇数個ならば結果は 1
、偶数個ならば 0
となる。
-
listS,listT
に対し S▹◃T
は S,T
の共通要素から成る list
である。
-
lowl(x)
は x
の最下位 l
ビットとする。
-
L1▹◃lL2
は L1×L2
から最下位 l
ビットが一致する全てのペアを含む list
である。
-
x1⊕x2=x3⊕x4
ならば x1⊕x2⊕x3⊕x4=0
k=4 の k-sum 問題
x1⊕x2⊕x3⊕x4=0
となるような x1,x2,x3,x4
の list
を見つける。
k-tree アルゴリズムによる解法
L1,L2,L3,L4
は要素をそれぞれ 2l
個含む list
とする。
lowl(x1⊕x2)=0
となるような x1⊕x2
の list
である L12
を作る。同様に lowl(x3⊕x4)=0
となるような x3⊕x4
の list
である L34
を作る。
性質
x1⊕x2=x3⊕x4
ならば x1⊕x2⊕x3⊕x4=0
より
L12
と L34
から x1⊕x2⊕x3⊕x4=0
となるような x1,x2,x3,x4
の list
を見つけられる。
計算量について
lowl(x1⊕x2)=0
となるような確率は 1/2l
E[∣L12∣]=∣L1∣×∣L2∣÷2l=22l÷2l=2l
同様にL34
のサイズも2l
性質
lowl(x1⊕x2)=0
かつ lowl(x3⊕x4)=0
ならば
lowl(x1⊕x2⊕x3⊕x4)=0
となる確率は 2l/2n
より、
L12
と L34
の共通要素の個数は ∣L12∣×∣L34∣÷2n−l
と見積もれる。
ここで ∣L12∣×∣L34∣÷2n−l=2l×2l÷2n−l=23l−n
より
l≥n/3
(逆だと確率が1
を超えてしまうから)
手順の始まりに l=n/3
とすると、k=4
の birthday problem を自明でない確率で解けることになる。
一般的な k に対する k-tree アルゴリズム
-
k が 2 の累乗の時
k=4
のアルゴリズムで用いた、list
の分割を log2k
回行って同様の操作を行えば良い。(以下、log2k=lgk
と表す。) O(k・2n/(1+lgk))
時間で解ける。
-
k が 2 の累乗ではない時
k′=2⌊lgk⌋
として list
分割を行えば良い。ただし、k=2i+j
の場合は、k=2i
の場合よりも基本的に速く解くことは出来ない。
α 個の解を見つけるためにかかる計算量
α≤2n/(⌊lgk⌋(⌊1+lgk⌋)
の場合、 α
個の解を見つけるには、計算量は α
倍になる。
まとめ
[2] はこの k-tree アルゴリズムを用いた一部のマルチシグへの攻撃を論じたホワイトペーパーなので、興味のある方は是非ご覧下さい。
参考文献
[1] https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf
[2] https://eprint.iacr.org/2018/417.pdf