Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

A modern trend in cryptography consists of defining security as rigorously as possible, and then designing schemes which are secure according to those definitions. Proving security comes in the form of reducing one scheme to a more basic problem or scheme. Furthermore, there are many different ways of formalizing security, and equivalence between security definitions is shown via reductions as well.

The concrete security approach for reductions, as introduced by Bellare, Desai, Jokipii, and Rogaway in FOCS '97, moves away from polynomial reductions and instead focuses on finding concrete bounds, so as to provide a more nuanced view of security. They discuss various formalizations of security for symmetric encryption schemes, including indistinguishability under chosen plaintext attacks (IND-CPA). Two variants of IND-CPA they come up with are left-or-right (LoR) and real-or-random (RoR), which they prove to be equivalent in the following sense:

Let $\mathcal{E}$ be an encryption scheme. For all adversaries with time complexity $t$ making at most $q$ queries to $\mathcal{E}$ totalling at most $\mu$ bits, $$\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu) \le \mathbf{Adv}_{\mathcal{E}}^{\text{lor-cpa}}(t,q,\mu) \le 2\cdot\mathbf{Adv}_{\mathcal{E}}^{\text{ror-cpa}}(t,q,\mu)\enspace.$$ Note that the bound on the right-hand side includes a factor 2.

My question is, is it possible to get rid of the factor 2, or does there exist an encryption scheme for which the LoR-cpa security is double its RoR-cpa security?

share|improve this question

1 Answer 1

One can't "get rid of" the factor 2.
However, there might be a way to replace it with $\:2\hspace{-0.03 in}-\hspace{-0.03 in}o(1)\:$ where that depends on $q$ and the advantage.

$||$ is concatenation.
Start with some encryption scheme $\mathcal{E}'\hspace{-0.04 in}$, and for any integer $n$ and probability $p$, let $\mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}$ be given by
$\;\;\;\;\;\;\;$ if $m$ has no ones and at least $n$ zeros then with probability $p$, $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.03 in}(m) \: = \: 00\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;\;\;\;\;$ else if $m$ has no zeros and at least $n$ ones then with probability $p$, $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}(m) \: = \: 1\hspace{-0.03 in}1\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$
$\;\;\;\;\;\;\;$ else $\;\;\; \mathcal{E}_{\hspace{.02 in}n,\hspace{.02 in}p}\hspace{-0.02 in}(m) \: = \: 0\hspace{-0.02 in}1\hspace{.04 in}||\hspace{.04 in}\mathcal{E}'\hspace{-0.03 in}(m)$

(Decryption just removes the first two bits and then applies $\mathcal{D}\hspace{.02 in}'$.)

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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