Distribution of group elements with chosen bits and hardness of discrete log problem

For generator $$g$$ of order $$n$$ the group elements $$y=g^x$$mod $$n$$ are uniformly distributed because of the modulo operation.

Suppose however that from the original output space $$Y$$, we only consider those elements $$y$$ which have some bits "fixed" in their binary representation. For example, for $$y = y_1,y_2...y_m$$ (where $$y_i$$ is a bit of the m-bit representation of $$y$$), consider the output space $$Y'$$ where all $$y \in Y'$$ have a static bit $$y_i$$ in a position $$i$$ set. Are those $$x$$ that are valid such that $$g^x \in Y'$$ (and also the complement set $$\bar{Y'}$$) still evenly distributed? In other words, is the hardness of the discrete logarithm problem equivalent when considering an output space $$Y$$ and $$Y'$$? My intuition says yes because of the modulo operation and the cyclic group, but I am looking for a more convincing answer (with cases $$n$$ is either prime or power of 2)

I have seen works that talk about "Bit security" (e.g. https://dl.acm.org/doi/pdf/10.1145/972639.972642 ) but these talk about the bits of $$x$$, while I am considering the "inverse" problem for bits of $$y$$..

• The simple argument, if $n$ is not the power of 2 then no! Mar 22, 2022 at 22:34
• So let's distinguish between the 2 cases (a) if $n$ is prime and (b) if $n$ is power of 2. You say in case (a) the distribution of $x$ where $g^x$ has some chosen prefix is skewed? Mar 23, 2022 at 3:10
• Rephrased the question if it helps Mar 24, 2022 at 17:39

I think that what you are asking is whether the bits of $$y$$ act as a hard-core function on the inverse of a one-way function (in this case the discrete logarithm function modulo $$n$$). For background on hard-core functions see for example section 2.4 for Foundations of Cryptography). However, if the inverse of a one-way function is easy to compute (which is true in your case as the exponentiation function can be computed in polynomial time), then there are no hard-core functions.

Cryptographers don't phrase this in terms of uniform distribution, but in terms of discriminators that can be computed in polynomial time and offer non-trivial advantage (see definition 2.4 of the notes). They say that a predicate $$b(y)$$ is hard-core for $$f$$ if for all polynomial time discriminators we have $$\mathbb P(A(f(U_n)),1^n)=b(U_n)<1/2+1/p(n).$$ In your case $$f$$ is the function $$y=g^x\mod n\mapsto x$$ and your function $$b$$ is the $$i$$th bit of $$y=g^x\mod n$$. However, I have the counterexample discriminator $$A(z,1^n)$$ which is to compute $$g^z\mod n$$ (in polynomial time) and look at the $$i$$th bit. This discriminates answers with probability 1 because with first argument $$f(y)=x$$ it returns $$b(y)$$.

In other words there is a computationally verifiable lack of uniformity because I can quickly test $$x$$ values to see whether or not they produce output that lies in $$Y'$$.

Yes. Let $$|Y'|=M$$ and let $$z$$ be any element of $$Y'$$ then Bayes' theorem tells us that $$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=\frac{\mathbb P(g^x\mod n=z)\mathbb P(g^x\mod n\in Y'|g^c\mod n=z)}{\mathbb P(g^x\mod n\in Y')}.$$ We now note that $$\mathbb P(g^x\mod n=z)=1/\phi(n)$$ (by the uniformity noted in the question), $$\mathbb P(g^x\mod n\in Y'|g^c\mod n=z)=1$$ and that $$\mathbb P(g^x\mod n\in Y')=M/\phi(n)$$ (again by the uniformity in the question). Thus $$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=1/M$$ for all $$z\in Y'$$ which describes a uniform distribution.
• Thanks, but does the Bayes approach really capture the distribution of $x$? I.e. those $x$ that are "valid" such that $g^x \in Y'$ could be potentially skewed in terms of the whole space $Y$? E.g. maybe for "fixing" some bit $y_b$, those $x$ could potentially have the probability for one of its bits to be equal to 0 to be greater than 1/2? Mar 28, 2022 at 19:37
• I'm not sure that I follow your comment. If you are asking "Is it possible to construct a conditional probability distribution where Bayes' theorem does not apply?" Then the answer is "No". Also note that although the values of $g^x$ are uniformly distributed, the bits are not e.g. for a $B$-bit $p$ the MSB is 0 with probability $(2^{B-1}-1)/(p-1)$ and 1 with probability $(p-2^{B-1})/2$. Mar 29, 2022 at 9:49
• So I am asking about the distribution of $x$, not $g^x$. And my question is if the distribution of $x$ (i.e. the probability that some bit of $x$ is 0 or 1) somehow changes if I "fix" some bit in the representation of $y = g^x$. I don't see how the fact that P = $1/M$ for all $z \in Y'$ show that $x$ are still uniformly distributed over the original output space $Y$.. Mar 29, 2022 at 14:14
• So the question is if a specific bit of output $y$ reveals some information about any bit of preimage $x$. Therefore, I think the function $b$ should be any bit of $x$ (not $y$), and if the discriminator with that bit of $y$ set, can predict with probability greater than 1/2 any bit of $x$ (awarded bounty because it expires) Mar 31, 2022 at 18:26