This question is related to data integrity.

Let a finite field be $\mathbb{F}_p$, where $p$ is a prime number.

I have a fixed value $y$ and two uniformly random values $a$ and $b$.

Hypothesis: $a,b,y,v \neq0$

I consider the server as an attacker who may modify the value $v$. The change to value $v$ may apply a clever change to value $y$ (see below).

I compute $v=a\cdot y+b$, and send it to the server. The server can do any change to $v$. So it computes a function of $v$, as $f(v)$.

Assume that I can magically detect if $y$ becomes a uniformly random value. So as long as the server cannot change $y$ to an arbitrary value $y'$ the security property is satisfied.

I can download $f(v)$ and remove the random values to obtain $y$, so I can do: $y=(a)^{−1}\cdot (f(v)−b)$

Question: How can I prove that ANY change to $v$ makes $y$ a uniformly random value?

To clarify I want to make sure the server cannot modify $v$ to apply an arbitrary change to $y$. In other word, my security needs would be satisfied if the server only can change $y$ to a uniformly random $y'$ (by changing $v$)

  • 1
    $\begingroup$ This nonsensical question has been asked repeatedly in different guises on math.SE, and the OP (who apparently has several pseudonyms) insists that they are all different. In one case, in a now-deleted question on math.SE, the OP said "@DilipSarwate I posted that one too. But I was at home and I did not access to my original account . If you think I must remove it, please give me a short answer to the above question and then I will delete it. – user13676" $\endgroup$ – Dilip Sarwate Sep 7 '15 at 13:27
  • $\begingroup$ Thank you for the serial down-votes on my answers on this site. $\endgroup$ – Dilip Sarwate Sep 7 '15 at 14:14
  • 2
    $\begingroup$ Please do not ask nearly identical questions on multiple sites of the stackexchange network. How To prove Any Change to v=a⋅y+b maks y=(a)−1(v−b) Uni. random value on math.se should suffice. $\endgroup$ – CodesInChaos Sep 7 '15 at 21:01
  • $\begingroup$ @CodesInChaos Read the answer over there please. If you get convinced I'd be too. If you got convinced it means you understand it completely and the answer is correct. In this case I have some questions about the answer and I can ask you. Let me know please. $\endgroup$ – user13676 Sep 8 '15 at 10:09
  • $\begingroup$ Well you do NOT know answer that is why vote it down.... $\endgroup$ – user13676 Sep 8 '15 at 12:29

Well, there is not much to prove.

The server can do any change to $v$.

So actually, this means the server with throw away your $v$ and just choose a new random number. Or alternatively, he chooses $w$ uniformaly random and sets $v'=v+w$, which is now also uniformly random.

When you get back that value, you have your (for you known/fixed) values $a,b$ and do your calculation $y' = a^{-1}(v'-b)$. With he existence of $a^{-1}$ (i.e. $a\neq0$), this is also uniformly distributed for fixed values $a,b$.

| improve this answer | |
  • $\begingroup$ Thank you for the answer. I do agree with you. But how could we answer the question that what if the server does anything other than Adding a value? because in the answer we only consider adding a value $w$. As we know it might do any change to $v$, (including addtion). $\endgroup$ – user13676 Sep 7 '15 at 11:39
  • $\begingroup$ Also $w$ may NOT be picked uniformly random by the server. $\endgroup$ – user13676 Sep 7 '15 at 11:45
  • $\begingroup$ Well, then you have to specify what the server can and can't do. If you just say "he can change something" then he could just throw away the old number and choose a new one. You can not prove that he didn't do that. And worse, he can't prove that he didn't do that either. $\endgroup$ – tylo Sep 7 '15 at 12:01
  • $\begingroup$ Yes, you're right. The scenario you explained is what I want, but there is not guarantee for that. Therefore it may not replace the value $v$ with a uniformly random one, instead it may do some clever attack. As you may have noticed that the above scheme (if we can say that way) is for data integrity. $\endgroup$ – user13676 Sep 7 '15 at 12:05
  • $\begingroup$ Maybe you should clarity your setup. Who is the attacker? The server? What is the exact goal, and do you have a special security property in mind? The more clearly your statements in the question are, the more likely you get a fitting answer. $\endgroup$ – tylo Sep 7 '15 at 14:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.