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.

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
add comment

1 Answer

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
add comment

Your Answer

 
discard

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.