Decode All

略解

一般性を失わず, $y_1 <= y_2 <= ... <= y_n$として良いです.

また, $N = 1$の時は自明にYESです.[例えば,$(a , b) = (y_0 \oplus x_0, 0)$とすれば良いです.]

加えて,$b$が$0$以上という条件も無視して良いです.

なぜなら,$2$つの整数のペア(ただし $0 \le a$) $(a, b)$が仮に暗号データを完全に再現するならば,

十分大きい任意の整数$r$に対して$(a + 2 ^ r, b + 2 ^ r)$も条件を満たすからです.

以下では$2 \le N$かつ$y_1 <= y_2 <= ... <= y_n$を仮定し, $b$の正負に関しては考えないものとします.

---

このとき,キーの存在性は

▷$(a \oplus x_j) - (a \oplus x_0) = y_j - y_0 \{for \ all \ 1 \le i < N\}$ を満たす$key$が存在する

と同値であることは明らかです.

仮に条件を満たす$key$があると仮定し,$a$を上位ビットから決定してゆくことを考えます.

$V = [0, y_1 - y_0, ... y_n - y_0]$

と定義します.(これは,あくまで各要素において$y_0$との差分を収めた配列であり,ビットの変化に合わせて動的に変化してゆくことに注意します.)

さて,$a$のbit目が $0 / 1$と仮定した時, $V$はどのように更新されるかを考えます.

初めに,$M \:=$ 十分大きいビット桁数として, $M$ビットより上は全てのビットが$0$としてしまって良いです.

$r = M, M - 1, .... 0$の順に$a$の$r$ビット目を確定させてゆきます.

この時,解が存在するならば,以下のループ不変条件が成り立つ必要があります.

◉ $[-2 ^ {r + 1} < x < 2 ^ {r + 1} for \ all \ x \ in \ V]$

[証明は略しますが,簡単にその概要を述べると,仮に命題を否定すると最終的に$V$の要素で$0$にすることができないものが存在するという背理法によるものです ]

逆にこれが$r = 0$終了時まで保たれれば,それは十分条件でもあり,最終的に解が存在することと同値です.

またこの時, 条件を満たすために$a$の$r$ビット目がどちらになるかはループ不変条件を保つための必要条件から一意に定まります.

これらのことから,各$r$について$r = 0$まで条件に違反しないかどうか$O(N)$程度で判定できることがわかります.

$M$は十分大きくとしましたが,具体的には$M = log(max(y_i - y_0))$程度でよいので$M = 60$とすれば

全体に要する計算時間量は$O(MN)$です.

[余談]

$y = (a \oplus x) - b$の場合,解は無限に存在するか$0$かのいずれかです.

ですが,　$y = (a \oplus x) + b$の場合,解は明らかに有限しか存在しません.

このとき,上記の考え方を更新すれば,全ての解の個数を求め,なおかつ,列挙することができます.

(ただし,その個数分の時間/計算コストは必要になります.)

難易度はやや上がりますが考えてみてください.