CMP.11:5.3 - Expose information hidden in a message

One agent has an n-bit string x and sends one fixed-length binary message to another agent holding y. The receiver must decide whether x=y with no error. If two different strings x and x’ produce the same message, take the common receiver input y=x. The receiver sees identical information in both cases but must answer differently. All 2^n strings therefore need distinct messages, requiring at least n bits. Sending x achieves it.

If public independent random masks and an error probability are admitted, the task changes. For each mask r, send the parity of the positions where both x and r are one; the receiver compares with its parity from y. Equal strings always match. For unequal strings, choose one differing position: toggling its independent mask bit pairs masks with opposite comparison outcomes, so the parities match with probability 1/2. After k independent masks, falsely accepting equality has probability 2^-k and the message has k bits. The shared random masks and local parity-computation cost are explicit resources, not information transmitted by the message.