# Can a hash preimage be used to amplify BPP probabilities?

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]$$?

• 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)... – usul May 27 '19 at 16:23
• ...on the other hand, derandomization and success probability amplification are different issues. – usul May 27 '19 at 16:28
• Isn’t it equivalent to choosing a small subset from $S$ uniformly at random? – Dmitri Urbanowicz May 28 '19 at 7:54
• @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? – Mark S May 28 '19 at 12:05
• 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). – Dmitri Urbanowicz May 28 '19 at 14:22