Probability and Data Integrity

124 Views Asked by At

This question is about probability and Security (i.e. data integrity). The scenario I am going to explain is a client-server case where the server may modify the client's data.


We define a field $\mathbb{F}_q$, where $q=2p+1$, $q$ and $p$ are large prime numbers (e.g. |p|= 256-bit).

The client who has value $b \in \mathbb{F}_q$, masks it as $M=(r_1\cdot b+r_2)\bmod q$, where $r_1$ and $r_2$ are picked uniformly random from the field, where $r_1,r_2>\frac{q}{2}$.

  • The client sends only $M$ to the server and it deletes $b$.
  • The client can download $M$ and check its data integrity:

    (1) $s_1=(M- r_2)\bmod q$

    (2) $s_2= (s_1\cdot (r_1)^{-1} )\bmod q=b$

    (3) If $s_2$ was a uniformly random value the client can (magically) detect it.

  • We know that if the server finds $k=c\cdot r_1, k<q$ it can modify value $b$ by computing $M+k$. So we would have $s_2=b+c$ and this attack cannot be detected.

  • Otherwise ($k\neq c\cdot r_1$), $s_2$ would be uniformly random value because $s_2=b+(r_1)^{-1}\cdot k\ $ is a uniformly random value.

Question: What is the probability that the server modifies $M$ without being detected?

1

There are 1 best solutions below

7
On BEST ANSWER

If the server modifies $M$, and replaces it with $M^{\prime}$, then $(M^{\prime} - r_{2})\cdot (r_{1})^{-1} \neq b$. Ever.

This is because, with $r_{1} \neq 0$, $f(x) = r_{1}\cdot x + r_{2}$ is a one-to-one function, therefore so is its inverse $f^{-1}(x) = (x- r_{2}) \cdot (r_{1})^{-1}$ and so you cannot have $f^{-1}(M^{\prime}) = f^{-1}(M) = b$ unless $M^{\prime} = M$.

Now, given that the server changes $M$ to $M^{\prime}$, the client will download and use $r_{1}$ and $r_{2}$ to "check" and obtain a $b^{\prime} = f^{-1}(M^{\prime})$. Each choice of $M^{\prime}$ leads to a unique $b^{\prime}$, so if $M^{\prime}$ is chosen uniformly randomly, then $b^{\prime}$ will be chosen uniformly randomly.

Note that there is no real way to say whether a single, fixed field element is "uniformly random" or not. So I can't say anything particular about the probability that you are asking about. (but as near as I can understand your question, I think it is always "uniformly random").