Score:2

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

do flag

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

kelalaka avatar
in flag
The simple argument, if $n$ is not the power of 2 then no!
do flag
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?
do flag
Rephrased the question if it helps
Score:1
ru flag

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.

do flag
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?
Daniel S avatar
ru flag
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$.
do flag
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$..
Daniel S avatar
ru flag
I think that I now understand your question and have amended my answer.
do flag
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)
Daniel S avatar
ru flag
If we restrict ourselves to single bit linear approximations as you describe, then any mutual information between a single bit of $y$ and a single bit of $x$ works both ways with both predicates being easy to compute. Other than the bias on bits due to the modulus, any further information would be a hard predicate on the bits of the discrete logarithm which we do not believe exists.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.