1
$\begingroup$

Black box generic models prohibit calculation of discrete logarithm in groups of order $q=2p+1$ where $p,q$ are random primes to $\Omega(\sqrt{p})$ steps (refer Discrete Logarithm in the generic group model is hard - Theorem by Shoup).

Do the black box generic models also prohibit MSB of discrete logarithm to $\Omega(\sqrt{p})$ steps or is it possible black box generic algorithms can get MSB of discrete logarithms in $polylog(p)$ steps?

Note to compute discrete logarithm once you know MSB is trivial but there is interaction (branching depending on MSB is $0$ or $1$) which I am not sure the Black Box models forbid.

Improve this question
$\endgroup$
2
  • $\begingroup$ Actually, if $p = 2^k + \epsilon$, then computing the msbit is easy (you just keep track of the $\epsilon$ values for which the dlog is $\ge 2^k$ - if you see anything else, the msbit is zero). You need to structure the 'compute the msbit' problem to avoid such trivial answers. $\endgroup$
    – poncho
    Mar 24, 2022 at 16:42
  • $\begingroup$ Ah I see.. assume $p$ is random prime. My main point is we have branching which is not in the generic algorithm model. So perhaps black box algorithms can give MSB polynomial time? Is this gap allowed in the known results on black box models? $\endgroup$
    – Turbo
    Mar 24, 2022 at 16:53

1 Answer 1

Reset to default
1
$\begingroup$

which I am not sure the Black Box models forbid"

What the Black Box model forbids is performing any operation on the group elements other than a specific set of operations. In your case, the allowed operations would be:

  • The group operation (given $A$ and $B$, return $A \times B$)

  • The group inversion operation.

  • Comparing two group elements for equality.

  • Your msbit oracle (because you're extending the black box model to contain this operation).

Any other operations on group elements are forbidden.

On the other hand, any operations are things which are not group elements are fair game. For example, your msbit oracle returns a bit; this bit is not a group element, and so doing things such as:

 if (oracle_returned_a_one) {
     do_this();
 } else {
     do_that();
 }

are perfectly in play.

So, unless the prime is just above a power of 2, that is, $p = 2^k + \ell$ for $2^k / \text{polylog}(p) < \ell < 2^k$, it should be obvious that you can compute the discrete log with a polynomial number of queries (specifically, $k + \text{polylog}(p)$ queries)

Improve this answer
$\endgroup$
6
  • $\begingroup$ Quick answer which addresses. $\endgroup$
    – Turbo
    Mar 24, 2022 at 17:28
  • $\begingroup$ So is the black box lower bound provided by DanielS invalid in crypto.stackexchange.com/questions/98988/…? We are extracting $a,k$ in $O(q^{1/4})$ steps and extracting bits of $a,k$ are not part of group operations. Correct? Black box lower bound only applies to not able to get $a+km_1$ directly in $o(q^{1/2})$ steps. correct? and not through intermediate steps of extracting bits of $a,k$? $\endgroup$
    – Turbo
    Mar 28, 2022 at 16:36
  • $\begingroup$ any thoughts on above comment? $\endgroup$
    – Turbo
    Mar 30, 2022 at 16:35
  • $\begingroup$ @Turbo: I thought DanielS was using the provable lower bounds for the black box to show that attacking a specific problem also had provable lower bounds (in the black box model) $\endgroup$
    – poncho
    Mar 30, 2022 at 16:56
  • $\begingroup$ His technique actually shows discrete log bound.. if the specific problem can be done then discrete log has $O(q^{1/4})$ bound is his result. It is why I think his bound is invalid because we are getting portions bits of exponent and doing something (similar to portion of bits here (which is MSB) and doing something). $\endgroup$
    – Turbo
    Mar 30, 2022 at 17:04

Your Answer

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

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