Do kleptographic attacks only work against probabilistic cryptosystems?
No. Kleptographic attacks have been devised for symmetric encryption algorithms that are deterministic [RP97,PG97,YY98,YY03] (however, some of these have been cryptanalyzed [WBDY98,DKZ99,Bi00]). This question is addressed in this FAQ since it encompasses relatively recent results and is therefore likely to be of interest to cryptographers. It might seem counter-intuitive that information can be leaked within a keyed bijection. However, recall that a block cipher is considered to be secure only if it can withstand a chosen-plaintext attack (or an adaptive chosen plaintext attack). So, it may be assumed that the adversary has plaintext/ciphertext pairs at his or her disposal. In the case of pseudorandom one-time pad encryption (akin to the Vernam cipher), this implies that the pad is known under the bitwise XOR operation. Hence, there can be information transmission outside the black-box cryptosystem. This intuitive explanation closely resembles the principles behind that attacks present
