Tìm các chuỗi $k$ $M_i$ sao cho XOR của các giá trị băm $k$ $H(i,M_i)$ bằng 0

Nếu bạn tính toán $2^{b/k}$ các giá trị của biểu mẫu $H(i,\cdot)$, cho mỗi $i$, thì khả năng cao sẽ có một số tập hợp các đại diện XOR bằng không. Bằng trực giác, sẽ có $(2^{b/k})^k$ cách chọn đại diện cho mỗi $i$, vì vậy một trong những cách này có khả năng XOR về 0. Thách thức là tìm ra một giải pháp như vậy một cách hiệu quả.

Vấn đề này được nghiên cứu bởi Wagner trong Một bài toán sinh nhật tổng quát. Anh ấy chỉ ra một thuật toán chạy trong thời gian $O(k \cdot 2^{b/(1+\log k)})$. Thật vậy, thuật toán không cải thiện nhiều như $k$ tăng, mặc dù đối với $k=4$ chúng tôi đã nhận được $O(2^{b/3})$ đó là một bước nhảy lớn từ $k=2$ trường hợp.

Tôi tìm thấy một bài viết tiếp theo của Brakerski, Stephens-Davidowitz & Vaikuntanathan, điều này đưa ra bằng chứng rằng thuật toán nhanh hơn khó có thể xảy ra.

Cũng lưu ý rằng khi $k \ge b$, các giải pháp có thể được tìm thấy trong thời gian đa thức thông qua đại số tuyến tính đơn giản. Xem Phụ lục A của tờ giấy này.