A system and method for exchanging a transformed message with enhanced privacy is presented. A set of input messages is defined. A set of output messages is defined. A message is selected from the input messages set. One or more words in the selected message are efficiently transformed directly into a transformed message different from the selected message, wherein the transformed message belongs to the set of output messages, at least one component of the selected message is recoverable from the transformed message, and the cost of determining whether the transformed message belongs to the input messages set or the output messages set exceeds a defined threshold.