Security Definitions

 Security Definitions

 So far we have used the terms “secure” and “break the system” quite loosely. What do we really mean? It is clear that a minimal requirement of security would be that: any adversary who can see the ciphertext and knows which encryption and decryption algorithms are being used, can not recover the entire cleartext. But, many more properties may be desirable. To name a few: 1. It should be hard to recover the messages from the ciphertext when the messages are drawn from arbitrary probability distributions defined on the set of all strings (i.e arbitrary message spaces). A few examples of message spaces are: the English language, the set {0, 1}). We must assume that the message space is known to the adversary. 2. It should be hard to compute partial information about messages from the ciphertext. 3. It should be hard to detect simple but useful facts about traffic of messages, such as when the same message is sent twice. 4. The above properties should hold with high probability. In short, it would be desirable for the encryption scheme to be the mathematical analogy of opaque envelopes containing a piece of paper on which the message is written. The envelopes should be such that all legal senders can fill it, but only the legal recipient can open it. We must answer a few questions: Cryptography: Lecture Notes 15 • How can “opaque envelopes” be captured in a precise mathematical definition? Much of Chapters 6 and 7 is dedicated to discussing the precise definition of security in presence of a computationally bounded adversary. • Are “opaque envelopes” achievable mathematically? The answer is positive . We will describe the the proposals of private (and public) encryption schemes which we prove secure under various assumptions We note that the simple example of a public-key encryptions system based on trapdoor function, described in the previous section, does not satisfy the above properties. We will show later, however, probabilistic variants of the simple system which do satisfy the new security requirements under the assumption that trapdoor functions exist. More specifically, we will show probabilistic variants of RSA which satisfy the new security requirement under, the assumption that the original RSA function is a trapdoor function, and are similar in efficiency to the original RSA public-key encryption proposal.