Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample a number $r$ uniformly from $[0,S]$; we can plug $r$ into $P$ to see if $P(r)=0$. If we only perform the above test one time, we would be "fooled" into thinking the polynomial is $0$ when it's not only $d/S$ times. However, we can rinse and repeat $k$ times to amplify our success probability, and our probability of being "fooled" is at most $(d/S)^k$.

As an alternative to rinsing and repeating, suppose instead we draw $r$ uniformly at random where we also know that $H(r)\le 2^{-m}$ for some cryptographic hash $H$ and some target $m$. That is, $r$ is not merely chosen uniformly at random from $[0,S]$, it's also a special $r$ that is chosen from all $[0,S]$ that hash on to less than a small value.

If we know that $H(r)\le 2^{-m}$, and we also know that $P(r)=0$, can we conclude that our probability of being "fooled" is at most $(d/S)^m$?

If we only choose one $r\in[0,S]$ whose SHA256 hash begins with a leading $0$, and test that $P(r)=0$, is that "the same" as testing if $P(r_1)=P(r_2)=0$ for two different $r_1, r_2\in[0,S]$?

  • $\begingroup$ Hmm, this sounds strange at first, but it's not far from derandomization (finding pseudorandom inputs on which the algorithm mimics expected true random behavior)... $\endgroup$
    – usul
    May 27, 2019 at 16:23
  • $\begingroup$ ...on the other hand, derandomization and success probability amplification are different issues. $\endgroup$
    – usul
    May 27, 2019 at 16:28
  • $\begingroup$ Isn’t it equivalent to choosing a small subset from $S$ uniformly at random? $\endgroup$ May 28, 2019 at 7:54
  • $\begingroup$ @DmitriUrbanowicz yes I think so. I think it's a way of choosing from a small random subset $T\subset S$ where $\vert T\vert=\epsilon\vert S\vert$. If $\epsilon$ is small enough, is there a way to do this without inverting a hash? $\endgroup$
    – Mark S
    May 28, 2019 at 12:05
  • $\begingroup$ You first fix random $T$ and then take random element from $T$? I can’t see how this is different from sampling $S$ directly (as long as you take fewer than $|T|$ samples). $\endgroup$ May 28, 2019 at 14:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.