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

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

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

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

CC BY-SA 4.0
2019-05-27T16:23:08.650Z
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
CC BY-SA 4.0
2019-05-27T16:28:33.343Z
...on the other hand, derandomization and success probability amplification are different issues.
usul
CC BY-SA 4.0
2019-05-28T07:54:28.687Z
Isn’t it equivalent to choosing a small subset from $S$ uniformly at random?
Dmitri Urbanowicz
CC BY-SA 4.0
2019-05-28T12:05:20.167Z
@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
CC BY-SA 4.0
2019-05-28T14:22:10.607Z
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
CC BY-SA 4.0
2019-05-28T16:28:29.120Z
@DmitriUrbanowicz thanks for your interest.  How can you first fix a random $T\subset S$ with $\vert T \vert=\epsilon \vert S\vert$?  You could choose every $2^{72}$'th element of $S$ but that's not a *random* subset.  Or you could choose an $x$ from $S$ with probability $2^{-72}$ - but that requires $O(2^{72})$ queries before you'd have a chance of even getting one hit. But we have this large  database of bitcoin preimages that are already pre-selected for us.
Mark S
<cc.complexity-theory><polynomials><hash-function>
Can a hash preimage be used to amplify BPP probabilities?
Mark S
# Can a hash preimage be used to amplify BPP probabilities?

(Asked by: username_0 on 2019-05-27)

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

**Tags:** cc.complexity-theory, polynomials, hash-function

> **Comments:**
> **username_1**: 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)...  
> **username_1**: ...on the other hand, derandomization and success probability amplification are different issues.  
> **username_2**: Isn’t it equivalent to choosing a small subset from $S$ uniformly at random?  
> **username_0**: @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?  
> **username_2**: 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).  
> **username_0**: @DmitriUrbanowicz thanks for your interest.  How can you first fix a random $T\subset S$ with $\vert T \vert=\epsilon \vert S\vert$?  You could choose every $2^{72}$'th element of $S$ but that's not a *random* subset.  Or you could choose an $x$ from $S$ with probability $2^{-72}$ - but that requires $O(2^{72})$ queries before you'd have a chance of even getting one hit. But we have this large  database of bitcoin preimages that are already pre-selected for us.  

---

## 0 answers

