# Hard-core bits from RSA assumption

I am trying to understand better the hard-core bit property from the RSA assumption. The paper by Håstad and Nåslund shows that every single bit is hard-core. By the result itself, two or more bits can be correlated, but marginally a single bit is pseudorandom.

Is it possible to extend the result to the parity of an arbitrary non-empty subset of bits? That is, for every non-empty subset $$S$$, is the parity of $$x_S$$ hard-core given $$(e,N,x^e\mod N)$$? If not, then what property $$S$$ has to hold to conclude the parity of $$x_S$$ is pseudorandom?

Here is a partial result:

Assume that we have a way, given $$x^e \bmod N$$, to derive the parity of $$x_S$$. We further assume that $$2 > N / 2^k > 1.5$$ for some integer $$k$$, that is, the two msbits of $$N$$ is set (if the second msbit is clear, then a similar procedure will work, using the second msbit of $$x$$).

Then, to get a bit with a correlation to the msbit of $$x$$, we first derive the parity $$x_S$$. Then, we compute $$x^e \cdot 2^e = (2x)^e$$, and then the parity of $$2x_S$$.

We then guess that the msbit is a 0 if $$x_S = 2x_S$$, and 1 if they differ.

Now, if the value $$2x < N$$, that is, if the doubling does not cause an overflow, then the parity $$x_S$$ will be the same as the parity of $$2x_S$$; if $$2x > N$$, then the doubling is really the computation $$2x - N$$, and the parity of that value will be uncorrelated with the parity of $$x$$.

Now, if the msbit of $$x$$ is a 0, that is, if $$x < 2^k$$, then the doubling will cause an overflow with probability $$1 - N / 2^{k+1} < 0.25$$, and hence our procedure will guess '0' over 75% of the time. If the msbit is a 1, the doubling will always cause an overflow, and so our procedure will guess '1' 50 % of the time.

This gives a way to get the msbit in a probabilistic manner; the cited results show how that can be used to derive everything.

Note that this result is weaker than the original; we assumed that we have a error-free way of determining the parity of $$x$$; however the original result covered weakly probabilistic methods. It might sound like this could easily be adapted to cover weakly probabilistic methods as well, however it is possible that the errors in determining the parities of $$x_S$$ and $$2x_S$$ might be correlated (which would invalidate this argument unless the errors were constrained to be fairly small)

• Sorry I don't understand why the parity of $x_S$ has to be the same of $(2x)_S$ if $2x<N$. For example if $S=\{i: i=0\mod 2\}$, i.e., $x_S$ collects all bits of even index, then why do the parities of $x_S$ and $(2x)_S$ have to be correlated? Jun 11, 2020 at 1:56
• @user50394: I misunderstood your notation; I was thinking that $x_S$ meant the parity of the entire representation of $x$, not only selected bit positions... Jun 11, 2020 at 12:35