Difference left-or-right CPA security, IND-CPA security

Question

I am trying to understand the notion of left-or-right-CPA (LOR-CPA) security for private-key encryption schemes introduced in my lecture. If I understood it correctly so far, the only difference to the standard IND-CPA game is that the encryption oracle always encrypts either the left or the right given message and that the attacker can query the oracle as often as it likes.

I am given the following game definition:

1. Generate key by running KeyGen $k \leftarrow KeyGen(1^n)$

2. Choose random hidden bit $h \leftarrow \{0,1\}$

3. Prepare an oracle $O_{LOR}$ called left-or-right oracle. When called with $m_0, m_1 \in M$ returns $c \leftarrow Enc_k(m_h)$

4. Call attacker A with $1^n$, attacker outputs two messages $m_0, m_1$ of same length

5. Call $O_{LOR}$ that returns $c \leftarrow Enc_k(m_h)$, give c to A, and await guess h'

6. If h' = h ACCEPT, else REJECT

My questions are:

• In what sense is this security notion stronger than the notion of IND-CPA security?
• Doesn't the standard IND-CPA game also always encrypts the left or the right message, dependent on the hidden bit?

Answer 1

As you are giving your adversary an access to an encryption oracle, I suppose that you implicitly consider the security of a symmetric encryption scheme. In the asymmetric setting, the definitions are slightly different. Here is my understanding of it (disclaimer: I'm by no mean a specialist on security for symmetric encryption scheme).

IND-CPA is the standard name for asymmetric semantic security. The adversary chooses two messages, the challenger encrypts one of them at random and the adversary tries to guess which one was encrypted. An important difference with the symmetric setting is that one does not have to define precisely the kind of oracle access given to the adversary, as he can just encrypt whatever he wants by himself (he is given the public key of the scheme).

Hence, when it comes to symmetric security, one has to be more precise as the oracle access to an encryption oracle is necessary (the adversary cannot encrypt by himself), and can come in different flavors.

So, to me, if one refers to IND-CPA security for a symmetric scheme, it's essentially a shorthand for "one of the security definitions in the CPA model" which are "essentially equivalent". More precisely, here are the four security definitions considered in this seminal paper:

-Left-or-Right CPA security. The oracle always encrypts the left ciphertext or he always encrypts the right ciphertext; you try to guess whether you see a left oracle or a right oracle.

-Real-or-Random CPA security. The oracle always encrypts the message you sent, or always encrypt a uniformly random message (independently of your message). You try to guess whether it's a real oracle or a random oracle.

-Find-Then-Guess CPA security. That one is the closest to the IND-CPA security notion in the asymmetric case: you give two plaintexts to the oracle, who encrypts one of them chosen at random, you have to guess which one.

-Semantic security. Given an encryption of some x drawn according to a distribution D you've chosen, find "some information" about x, id est, some f(x) for a function f of your choice.

Now, to answer your question, here are the security comparisons:

-Left-or-Right CPA security and Real-or-Random CPA security are equivalent (there is a security preserving reduction in both direction)

-Semantic security and Find-Then-Guess CPA security are equivalent

-There is a security preserving reduction from Left-or-Right CPA security to Find-Then-Guess CPA security. This does not hold in the other direction. This means that if an adversary breaks one of the two last security properties, he must also break the two first, but the convert is not true.

EDIT: if by IND-CPA, you mean the security notion I defined with the name Find-then-Guess CPA, then as stated above, if one can break IND-CPA, one can break LOR-CPA, but the converse is not true. Hence, LoR-CPA security is a stronger security notion than IND-CPA (and the proof for this statement is in this paper) Doesn't that answer your question?

For your last question: if IND-CPA is indeed find-then-guess CPA, then the difference is the following. In LOR, the oracle picks a bit once and always answer with an encryption of the plaintext indexed by this bit, for all the encryption requests. In IND-CPA, each time you submit a pair of plaintext to the oracle, the oracle picks a random bit and encrypts the corresponding plaintext.

Answer 2

My definitions of IND-CPA and LOR-CPA call the attacker only once and instead of two phases a one-time test oracle will supply the challenge. As the left-or-right oracle is the test oracle for LOR-CPA that makes no difference here. But for IND-CPA it allows the attacker to query more encryption after receiving the challenge. This may lead to a slightly stronger security notion but I believe that the two-phase model is artificial anyways.

Now back to your question:

• In what sense is this security notion stronger than the notion of IND-CPA security?

Actually, (t,e)-IND-CPA security does imply (t,l e)-LOR-CPA security where l is a bound on the number of calls to the left-or-right oracle in the LOR-CPA game. This can be proved by Yao's approach. You lose the factor l however.

In the other direction you do not lose anything (but a tiny amount of time for the reduction).

• Doesn't the standard IND-CPA game also always encrypts the left or the right message, dependent on the hidden bit?

No. The IND-CPA game has an oracle for encryption. It encrypts a given message but does not access the hidden bit. The attacker only has access to the hidden bit when asking for the challenge (via a one-time oracle as I prefer, or via a two-phase model as you wrote above).

To emphasize the difference: In the LOR-CPA game the attacker gets something depending on the hidden bit on every oracle call. In IND-CPA game the attacker only gets access to the hidden bit once.