Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.
share|improve this question

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.

share|improve this answer
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? – Pigmann Jul 8 '13 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}$. – minar Jul 8 '13 at 5:06

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.