We show software agents that operate on input plaintext, transmit the result, and have the property that characterizes the operation as theft of plaintext amounts to solving a hard cryptographic problem. Such agents employ what we call a "questionable encryption scheme" in which it is computationally intractable to determine if the output is an asymmetric ciphertext or nonce. We therefore show a fundamental computational limitation of information forensics

The area of "computing with encrypted data" has been studied by numerous authors in the past twenty years since it is fundamental to understanding properties of encryption and it has many practical applications. The related fundamental area of "secure function evaluation" has been studied since the mid 80's. In its basic two-party case, two parties (Alice and Bob) evaluate a known circuit over private inputs (or a private input and a private circuit). Much attention has been paid to the important issue of minimizing rounds of computation in this model. Namely, the number of communication rounds in which Alice and Bob need to engage in to evaluate a circuit on encrypted data securely. Advancements in these areas have been recognized as open problems and have remained open for a number of years. In this paper we give a one round, and thus round optimal, protocol for secure evaluation of circuits which is in polynomial time for NC/sup 1/ circuits. The protocol involves an input party sending encrypted input to a second party, a cryptocomputer, which evaluates the circuit (or a known circuit over its additional private input) non-interactively, securely and obliviously, and provides the output to the input party without learning it. This improves on previous (general) results that are specialized to the case of NC/sup 1/ circuits and require a constant number of communication rounds. We further suggest applications to network and mobile computing.

Cryptovirology has recently been introduced as a means of mounting active viral attacks using public key cryptography. It has been shown to be a tool for extortion attacks and "electronic warfare", where attacks are mounted against information resources. The natural question to ask is whether Cryptovirology is also useful in the area of spying via malware. We demonstrate that Cryptovirology does help in "electronic espionage" and allows the spy to conceal his or her identity (as well as past collected information). Specifically, we present an attack that can be mounted by a cryptotrojan that allows the attacker to gather information (passwords) from a system in such a way that the attacker cannot be proven guilty beyond reasonable doubt. That is, even if the attacker is under surveillance on the local machine from when he first attacks the target machine, to when he obtains the passwords, and even if the leaked information is made available to the attacker exclusively, he still cannot be caught. The threat is made possible by the combination of public key cryptography, probabilistic encryption, and the use of public information (I/O or communication) channels which together form a "secure receiver-anonymous channel". The machine can be standalone or networked. What we learn from the attack is extracted as general tools and basic principles for "espionage attacks".

Traditionally, cryptography and its applications are defensive in nature, and provide privacy, authentication, and security to users. In this paper we present the idea of Cryptovirology which employs a twist on cryptography, showing that it can also be used offensively. By being offensive we mean that it can be used to mount extortion based attacks that cause loss of access to information, loss of confidentiality, and information leakage, tasks which cryptography typically prevents. In this paper we analyze potential threats and attacks that rogue use of cryptography can cause when combined with rogue software (viruses, Trojan horses), and demonstrate them experimentally by presenting an implementation of a cryptovirus that we have tested (we took careful precautions in the process to insure that the virus remained contained). Public-key cryptography is essential to the attacks that we demonstrate (which we call "cryptovirological attacks"). We also suggest countermeasures and mechanisms to cope with and prevent such attacks. These attacks have implications on how the use of cryptographic tools should be managed and audited in general purpose computing environments, and imply that access to cryptographic tools should be well controlled. The experimental virus demonstrates how cryptographic packages can be condensed into a small space, which may have independent applications (e.g., cryptographic module design in small mobile devices).