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.

  • 1
    How many strings of length $n$ are there? How many pairs of strings of length $n$ are there? And from these, how many could satisfy a linear relationship?2011-03-03
  • 0
    'the probability that you can modify both strings'... Your question is not well formulated, pls revise it.2011-03-03
  • 0
    @leonbloy Sorry I'm an ESL speaker. I will revise it.2011-03-03
  • 0
    @Raskolnikov There are $2^n$ different $\alpha$s and same number of $\beta$s. So, there are $2^{2n}$ different pairs $(\alpha',\beta')$. Now, I need to count how many of those $2^{2n}$ pairs satisfy the linear relation $\beta' = a \alpha' + b$. And the probability of choosing an element randomly from the $2^{2n}$ such that it satisfies the linear relation. Right?2011-03-03
  • 0
    @M.S.: You got it!2011-03-03
  • 0
    How do you define $a\alpha$ for binary strings $a$ and $\alpha$?2011-05-03
  • 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.)