2
$\begingroup$

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$..

$\endgroup$
3
  • $\begingroup$ The simple argument, if $n$ is not the power of 2 then no! $\endgroup$
    – kelalaka
    Mar 22, 2022 at 22:34
  • $\begingroup$ 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? $\endgroup$
    – Panos
    Mar 23, 2022 at 3:10
  • $\begingroup$ Rephrased the question if it helps $\endgroup$
    – Panos
    Mar 24, 2022 at 17:39

1 Answer 1

1
+50
$\begingroup$

UPDATE 20220330: New answer following question clarification; old answer retained to make sense of the comments.

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'$.

Old answer.

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Panos
    Mar 28, 2022 at 19:37
  • $\begingroup$ 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$. $\endgroup$
    – Daniel S
    Mar 29, 2022 at 9:49
  • $\begingroup$ 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$.. $\endgroup$
    – Panos
    Mar 29, 2022 at 14:14
  • $\begingroup$ I think that I now understand your question and have amended my answer. $\endgroup$
    – Daniel S
    Mar 30, 2022 at 9:00
  • $\begingroup$ 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) $\endgroup$
    – Panos
    Mar 31, 2022 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.