# How to compute the attacker's probability?

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)$.

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.

• 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? Jul 8, 2013 at 2:20
• 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}$. Jul 8, 2013 at 5:06