3
$\begingroup$

Given a random bit string $R=r_1r_2\cdots r_n$, let us encrypt each bit $c_i=E(r_i,k_i)$ where $k_i$ is taken from the stream of encryption keys. Suppose that an attacker can guess the correct $r_i$ from $c_i$ with probability $p>1/2$. Then, the probability that the attacker can recover correct $R$ from $C=(c_1,\cdots,c_n)$ is $p^n$.

Now, suppose that we use the following encryption diagram (given below). Is the attacker's probability of recovering the correct $R$ from $C'=(c'_1,\cdots,c'_n)$ still $p^n$?

  1. Let $r'_i=r_1\oplus r_2\oplus\cdots\oplus r_{i-1}\oplus r_i$.
  2. Let $c'_i=E(r'_i,k_i)$.
$\endgroup$

1 Answer 1

3
$\begingroup$

The probability of recovering the string $R$ is the same with both of your scheme. The reason is that your second scheme can be separated into two independent parts. In the first part, you just transform $R$ into $R'$ using only your step 1 (this is invertible and from $R'$ you can recover $R$).

In the second part, you just encrypt $R'$ with the previous scheme. As a consequence, the probability of recovering $R'$ is the same as in the first scheme and due to the invertibility of the first part, this is equivalent to recovering $R$.

I am wondering about why you want to use this scheme. Did you consider (in your context) attacks that would approximate $R$ instead of predicting it exactly ? I ask this because this would greatly increase the probability of success.

$\endgroup$
2
  • $\begingroup$ Thanks for your excellent answer. Why do you think the approximate attack would succeed with higher probability? Would you like give me a detailed analysis? $\endgroup$
    – Pigmann
    Jul 8, 2013 at 2:20
  • $\begingroup$ For example, if the attacker is happy with predicting $R$ within Hamming distance 1 (0 or 1 position in error), the number of acceptable answers is $n+1$ which multiplies the probability. If you accept up to $\delta$ error, the multiplier is the sum of binomials $\sum_{i=0}^{\delta}{i \choose n}$. $\endgroup$
    – minar
    Jul 8, 2013 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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