SIM-CPA security

From CRYPTUTOR

SIM-CPA security is a security definition for private- or public-key encryption schemes. At a high level, SIM-CPA security means that sending messages over an insecure channel via the encryption scheme is equivalent to sending those messages through a secure channel, from the point of view of a certain class of adversaries. SIM-CPA security can be shown to be equivalent to the more technical IND-CPA security.

The "SIM" part of the name SIM-CPA comes from the fact that it is a simulation-based security definition. The "CPA" part stands for chosen plaintext attack, because in the SIM-CPA model, adversaries may have arbitrary influence over which plaintext messages are encrypted in the system.

Definition

Consider the following two experiments among two honest parties Alice and Bob, an adversary Eve, and an environment, in which Alice gets a message from the environment and tries to send it to Bob. The behaviors of Alice and Bob in each experiment are fixed, but Eve and the environment may be any arbitrary non-uniform PPT machines (polynomial in the encryption scheme's security parameter).

The environment models an arbitrary influence Eve might have over the messages that Alice sends to Bob, as well as arbitrary criteria for whether Eve has succeeded in doing something "malicious."

Real world experiment:

1. In the case of private-key encryption, Alice and Bob share a key k chosen according to the encryption scheme's key generation algorithm . In the case of public-key encryption, Bob generates a public-key/private-key pair, so that the public-key k is made available to both Alice and the adversary.
2. Repeatedly do:
   • The adversary Eve arbitrarily interacts with the environment (i.e, to influence its choice of message in the next step).
   • The environment sends a message m to Alice.
   • Alice sends to Bob.
   • Eve receives a copy of the ciphertext, and then arbitrarily interacts with the environment (to influence the behavior of the environment).
3. The environment outputs a bit (whether Eve caused a particular observable effect on the environment).

The adversary is said to "succeed" in the experiment if the environment outputs 1.

Ideal world experiment:

1. Repeatedly do:
   • The adversary Eve arbitrarily interacts with the environment.
   • The environment sends a message m to Alice.
   • Alice sends the message m to Bob through a secure channel.
   • Eve receives notification that a message was sent through the channel (but does not receive a ciphertext). (Here we assume that the messages come from a finite message space. Otherwise, Eve is notified the length of the message as well.) Eve continues to arbitrarily interact with the environment.
2. The environment outputs a bit (whether Eve caused a particular observable effect -- same as above -- on the environment).

The adversary is said to "succeed" in the experiment if the environment outputs 1.

The encryption scheme is SIM-CPA secure if:

For all real-world adversaries , there exists an ideal-world adversary , such that for all environments, the success probabilities in these two experiments differ by a negligible amount (in the scheme's security parameter).

It is convenient to interpret this definition in the following way: for all ways to "do something malicious" in the presence of the encryption scheme (i.e, an adversary ), there is another way to do the same malicious thing (i.e, the corresponding ) without looking at the ciphertexts at all!

Simulation-based definition of the full encryption functionality

This definition can be modified to take into account not only the secrecy requirement, but the entire functionality of an encryption scheme (which includes the ability to communicate messages without error, except, possibly, with negligible probability). For this the Real world and Ideal world experiments are modified as follows:

Modification to the Real world experiment:

• When Bob receives a ciphertext from Alice, he decrypts it (using the shared key in the private-key scenario, or his secret key in the public-key scenario) and outputs the resulting message to the environment.

Modification to the Ideal world experiment:

• When Bob receives a message from Alice through the secure channel, he outputs it to the environment.

Note that this modification models the fact that Bob somehow uses the messages he recieves. The usage is modeled as sending the message to the environment (which incorporates Bob's "local environment").

See also

• IND-CPA security
• Equivalence of IND-CPA and SIM-CPA
• SIM-CCA security