Deterministic SMP equality costs Ω(n) bits

Alice's message map must be injective. If $x\mathrm{\ne }{x}^{\mathrm{\prime }}$ had the same Alice message, compare inputs $(x,x)$ and $(x^{\mathrm{\prime }},x)$. Bob's message is the same on both because Bob's input is $x$, and Alice's messages agree by assumption; the referee therefore receives identical transcripts although [F1] requires outputs $1$ and $0$. This contradiction proves injectivity.

With fixed length $b$, Alice has at most $2^b$ messages, so injectivity gives $2^n\le 2^b$ and $b\ge n$. If all strings of length at most $b$ are allowed, their number is ${\sum }_{j=0}^b{2}^j=2^{b+1}-1$; injectivity gives $2^n\le 2^{b+1}-1$, which forces $b\ge n$. Alice alone therefore sends at least $n$ bits in the worst case.