2
$\begingroup$

Consider the discrete Log Problem w.r.t. prime $p$. Given $b, p, r$ find $x$ where: $b^x\bmod p=r$.

We are promised that $b^{\frac{(p-1)}2}\bmod p=p-1$.

Q1: What is the complexity of calculating the second Least Significant Bit of $x$ in the worst case?

Q2 Is there a generic formula for calculating time complexity of $i^\text{th}$ Least significant bit and not just second in this promise case?

Edit: $1<x<p$

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ As the question stands now, the Second Least Significant Bit can be impossible to compute. Example: $b=2$, $p=19$, $r=4$, solutions include $x=2$ and $x=20$, and these have different Second Least Significant Bit. One fix is to add the constraint $1\le x<p$. Also, we want $b\not\equiv-1\pmod p$, and more generally that $b$ is a generator. $\endgroup$ Commented Nov 5 at 17:20
  • $\begingroup$ I have updated to add the constraint on $x$. b is any possible integer so I am unclear what else is needed to clarify. Please feel free to update. $\endgroup$ Commented Nov 5 at 18:35
  • $\begingroup$ Example of why we need restriction on $b$ [beside $b\ne p-1$ ]: $b=6$, $p=31$, $r=5$. Solution is $x\in\{8,14,20,26\}$ and again the Second Least Significant Bit in undefined. To fix this for good we can restrict to $b$ a generator as I first suggested [equivalently: such that $b^{(p-1)/s}\bmod p\ne1$ for all primes $s$ dividing $p-1$ ] and $1\le x<p$ [or $0\le x<p-1$ ]. Another option is to restrict to $1\le x\le\operatorname{ord}(b)$ [or $0\le x<\operatorname{ord}(b)$ ]. Yet another is to define that $x$ is the smallest positive [or non-negative] solution. $\endgroup$ Commented Nov 5 at 19:27

1 Answer 1

Reset to default
2
$\begingroup$

A1 In the language of cryptography, the second Least Significant Bit of $x$ is a hard-core predciate for $x$. In other words reliable computation of this bit is (polynomial time) equivalent to the full computation of $x$. This was established in Peralta's 1985 Eurocrypt paper Simultaneous security of bits in the discrete log. NB the worst case here is the case where $p\equiv 3\pmod 4$, or more specifically when $4\not\!|\mathrm{ord}(b)$. In the case $4|\mathrm{ord}(b)$ we can raise $r$ to the power $\mathrm{ord}(b)/4$ and compare to $1$, $b$, $b^2$, $b^3$ raised to the same power.

The proof in this simpler case is a very similar to the Blum-Micauli seminal proof of the hardness of the most significant bit of the discrete logarithm.

A2 Nor is there a generic formula for general bit positions see Claus Schnorr's paper Almost All Discrete Log Bits Are Simultaneously Secure.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. But is it also the same for the kind of numbers I specified above or only for the general case? $\endgroup$ Commented Nov 5 at 18:53
  • $\begingroup$ @TheoryQuest1 The result applies to number of the form that you describe. $\endgroup$ Commented Nov 5 at 18:59
  • $\begingroup$ @DanielsS: Call me picky but the result stated does not apply to the question as it stands now, because there is not enough to make the Second Least Significant Bit well-defined. That's obvious for $b=p-1$, but there are other cases. We want $1\le x<p$ and $b$ a generator, or is it $1\le x\le\operatorname{ord}(b)$. $\endgroup$ Commented Nov 6 at 4:05
  • 1
    $\begingroup$ @fgrieu You are correct and it is wise to be precise about these statements in order to avoid misuse. The above applies for $1\le x\le\operatorname{ord}(b)$. $\endgroup$ Commented Nov 6 at 7:06

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.