Communication Lower Bounds for Collision Problems via Density Increment Arguments

Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works by Bauer, Farshim and Mazaheri (CRYPTO 2018), Itsykson and Riazanov (CCC 2021), Göös and Jain (RANDOM 2022) independently proposed the communication version of collision problems.

In the communication setting, both Alice and Bob receive 𝑘 uniformly random sets: 𝑆 1 , . . . , 𝑆 𝑘 and 𝑇 1 , . . . ,𝑇 𝑘 with each of size roughly √ 𝑁 , where a typical choice of 𝑘 is in the order of √ 𝑁 for applications. Then Alice and Bob aim to find a pair (𝑥, 𝑥 ′ ) such that 𝑥, 𝑥 ′ ∈ 𝑆 𝑖 ∩ 𝑇 𝑗 for some 𝑆 𝑖 and 𝑇 𝑗 . A simple protocol that solves this problem with 𝑂 (𝑁 1/4 ) communication bits can be the following: Alice sends to Bob a random subset of 𝑆 1 of size 𝑁 1/4 and Bob checks if there is a set 𝑇 𝑗 that has more than two intersections to this subset. All the papers mentioned above believe this bound should be tight up to some log factors.

In this paper, we prove an Ω(𝑁 1/4 ) randomized communication lower bound, affirming the conjecture above. Previously, only an Ω(𝑁 1/12 ) was known by a work of Göös and Jain (RANDOM 2022). Our lower bound provides direct applications to cryptography and proof complexity via connections by Bauer, Farshim, and Mazaheri (CRYPTO 2018) and Itsykson and Riazanov (CCC 2021).

Our proof technique could be of independent interest as it is an extension of simulation methods to non-lifted functions. Previously, simulations have been widely applied to lifted functions (a.k.a composed functions), which leads to beautiful query-to-communication lifting theorems. However, many important communication problems are not lifted functions. We believe our methods could give more applications. In particular, it may have applications to communication search problems with many solutions. Note that many existing methods do not apply to this setting.