, 2020

The smallest $N = 63$.
Let $n = 187$, and the binary representation of $187$ is $10111011$. First we note that the $n$-th difference gives $\sum_{i=0}^{n} (-1)^i \binom{n}{i} f(i) = 0$. By Lucas' theorem we know that $\binom{n}{i}$ is odd if and only if the positions of the $1$'s in the binary representation of $i$ are a subset of the positions of the $1$'s in the binary representation of $n$, so
$$0 \equiv \sum_{B \subseteq A} f\left(\sum_{i \in B} 2^i\right) \pmod{2}$$
where $A$ is the set of positions of the $1$'s in the binary representation of $n$. From this it follows that Alice only needs to know
$S := \{\sum_{i \in B} 2^i \mid \varnothing \neq B \subseteq A\}$, and she can then determine the parity of $f(0)$.
On the other hand, if some $t$ in $S$ has not yet been queried, then Alice cannot distinguish between $f(0)$ and $f(0)+g_t(0)$, where $g_t$ is a polynomial of degree at most $n-1$ satisfying $g_t(t) = 1$ and $g_t(t') = 0, \forall t' \in \{1, 2, \dots, n\} - \{t\}$. It is well known that $g_t$ also sends integers to integers. However, applying the identity modulo two obtained in the previous paragraph, we know that $g_t(0)$ is an odd number, so in this case Alice cannot determine the parity of $f(0)$.
In summary, Alice must ask at least $|S| = 2^{|A|} - 1 = 63$ times.