(C) costs little more than an extra round-trip - a verifying call from Alice to Bob, before she acts. After receiving the message from Mallory who is impersonat

(C) costs little more than an extra round-trip - a verifying call from Alice to Bob, before she acts. After receiving the message from Mallory who is impersonating Bob, Alice simply sends Bob a nonce encrypted under Bob's public key. Bob performs a simple operation on the nonce, re-encrypts it with Alice's public key and sends it back to her, thereby verifying that he holds his private key. Or am I missing something?