[lorenzhs]

That's still not the problem considered here. You're not asking "does anyone have the key I'm seeing here", you're asking "does this person next to me have the key I'm seeing here". No birthday paradoxes of any kind involved.

[lenish]

Forgive me, as I haven't used signal, but I don't see how whether they are sitting next to you or not changes the problem.

If I can generate a key that hashes to the same value as your key, I can convince anyone I am you. If I can generate a second collision for a third party's key, I can convince you you are talking to that third party, as well. Generating hash collisions is, as I understand it, pretty well modelled with the birthday paradox (and variations like the one I linked). Physical proximity seems entirely unrelated.

[lorenzhs]

Right, sorry, I misunderstood. A preimage attack (that's the technical term for this) could indeed be modeled as a birthday problem with a fixed day ("someone with the same birthday as me"). This is much harder than finding a normal collision (two objects with the same hash, two people with the same birthday), though.