7
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ You have to provide an encryption oracle if you are targeting CPA security $\endgroup$ – cygnusv Mar 2 '16 at 10:25
  • $\begingroup$ What do you mean exactly? That the attacker has access to $O_{LOR}$? I'm just repeating the definition I was given, my goal is to understand it. $\endgroup$ – Lemon Mar 2 '16 at 13:34
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry but I don't see how that answers any of my questions. Could you be more precise about: 1. How LoR-CPA is different from IND-CPA and 2. In what sense it is a stronger security notion? I am specifically asking about those two notions for private-key encryption schemes, not about others. $\endgroup$ – Lemon Mar 2 '16 at 13:38
  • $\begingroup$ Could you therefore define what you mean when you say IND-CPA? To me it's a standard name for asymetric crypto, but not one I'm used to in symmetric crypto. Does this corresponds to any of the notions I defined? It seems to me that IND-CPA refers to what I called "Find-then-Guess" CPA. If yes, then you have your answer as I gave the reductions between the notions; else, could you please define precisely IND-CPA as explained in your lecture? I edited my answer. $\endgroup$ – Geoffroy Couteau Mar 2 '16 at 13:50
  • $\begingroup$ I believe it means the same as "Find-then-Guess" CPA. But then it doesn't make sense since we were told that LOR-CPA is stronger than IND-CPA... $\endgroup$ – Lemon Mar 3 '16 at 17:11
  • $\begingroup$ Yes sorry, my answer is correct but I wrote the wrong conclusion (I exchanged IND-CPA and LoR-CPA in my conclusion). If a scheme is secure in the Left-or-Right sense, then it is also secure in the Find-then-Guess sense, which means that being secure in the Left-or-Right sense is a stronger security property than being secure in the Find-then-Guess sense. Equivalently, an adversary breaking the Find-then-Guess security property of a scheme does also break its Left-or-Right security, hence the ability to break IND-CPA is a stronger ability than the ability to break LoR-CPA. Answer edited. $\endgroup$ – Geoffroy Couteau Mar 3 '16 at 17:44
  • $\begingroup$ @GeoffroyCouteau What do you mean that there is no sense of defining the oracle in asymmetric IND-CPA? Since the adversary has access to the public key then it only makes sens when the oracle provides decryption? encryption can be performed by him/herself.Am i right? $\endgroup$ – curious Jun 1 '16 at 19:57
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.