0
$\begingroup$

Let $a ,$ $b ,$ $\alpha ,$ and $\beta$ be non-zero binary strings of length exactly $n$ where $ \beta = a \alpha + b. $

Now, consider the following scenario. Fix $a$ and $b.$ I give you $\alpha$ and $\beta,$ but keep $a$ and $b$ as secrets from you. What is the probability that you can modify both strings (same length, just alter some bits), such that the altered strings \alpha' and \beta' still satisfy \beta' = a \alpha' + b. A cryptography paper which I am reading mentions it is $2^{-n}$ but I couldn't convince myself why.

  • 0
    @Didier Piau: I see. My question formulation was very sloppy. Better wording would be: Let $a, b, \alpha, \beta \in \mathbb{N}$ have binary expansion of length $\le n.$2011-05-03

1 Answers 1

0

Answer was figured out in the comments by discussion with @Raskolnikov.

(Edit: It's better if a moderator can close the question.)