How to know when decryption fails in Yao's Garbled Circuits

Question

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?

Answer 1

Your intuition is correct, the encryption is set up to indicate a failed decryption when an incorrect key is used with the ciphertext. A very simple way of doing so can be as follow: when encrypting the message $m$ with the key $K$, encrypt $m||0^{\lambda}$ ($\lambda$ is a security parameter, e.g. 80 or 128). When decrypting a ciphertext, check whether the last $\lambda$ bits are $0$; if this is not the case, decryption failed.

Note that the paper you are reading describes also the point and permute technique, which allows to find out which ciphertext we should decrypt, without having to try them all. This is an important optimization for garbled circuits.