The comments in this recent question about the security of 3DES made me wonder if the key complement property of DES (which reduces its security by ~1 bit) can be used in the meet-in-the-middle attack on 3DES.
Can the complexity of the attack be reduced by 1-2 bits by making use of the complement property to rule out more keys than are being directly tested?
Sure, the difference between 112 and 110 bits probably does not matter in practice.
yes,it is possible because in meet in the middle attack on 3DES,see below
with Complementation Property of DES in red arrow,you can search $2^{55}$ key space instead of $2^{56}$,and for green arrow,you have $DEC_{K2}(ENC_{K1}(M))$ that without key Complementation Property,you need $2^{112}$ operations but with key Complementation Property of left ENC and middle DEC block,you need $2^{110}$ operation and in total you need $2^{55}+2^{110}\approx 2^{110}$ operations
NOTE: in green keyspace(arrow), you should calculate one encryption and then one decryption for your known plaintext,for both decryption and encryption of DES,if you test one pair key($K_{1}$ and $K_{2}$) and calculate the middle variable,because of Complementation Property of DES,you don't need to have a decryption and encryption for $K'_{1}$ and $K'_{2}$ so with every calculate of $DEC_{K2}(ENC_{K1}(M))$,you test 4=$2^2$ keys
