I'm reading A Gentle Introduction to Yao's Garbled Circuits, and I came across this passage:
Note that in order for this to work, Evan needs to know when decryption succeeds, and when it doesn’t. Otherwise, there’s no way for him to know which ciphertext yields the correct answer. So, simply XOR-ing the key with the encrypted value will not work here.
Essentially, Alice sent 4 values, each encrypted using different keys using symmetric-key encryption. Bob has one of the 4 keys and needs to know for which of the 4 values decryption succeeds. How does Bob accomplish this?
I figure since the unencrypted values are all either 0 or 1, the encryption could somehow be set up so that a failed decryption produces a non-0/1 value with really high probability, but I don't know if this is right.
How is failed symmetric key decryption detected in Yao's Garbled Circuits?