Score:1

Crypto

Does generic group black box model prohibit MSB of discrete logarithm?

Turbo

7/24/23, 4:21 PM

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.

0 + 0

discrete-logarithm

algorithm-design

complexity

computational-complexity-theory

ggm

poncho

7/24/23, 4:42 PM

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.

Turbo

7/24/23, 4:53 PM

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?

Score:1

Crypto

poncho

7/24/23, 5:26 PM

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)

0 + 0

Turbo

7/24/23, 5:28 PM

Quick answer which addresses.

Turbo

7/28/23, 4:36 PM

So is the black box lower bound provided by DanielS invalid in https://crypto.stackexchange.com/questions/98988/common-exponent-problem-related-to-discrete-logarithms-assuming-diffie-hellman-o? 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$?

Turbo

7/30/23, 4:35 PM

any thoughts on above comment?

poncho

7/30/23, 4:56 PM

@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)

Turbo

7/30/23, 5:04 PM

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

Turbo

7/30/23, 6:05 PM

for the reason above I think his reasoning might not apply. Can you please double check?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does generic group black box model prohibit MSB of discrete logarithm?

TH: โมเดลกล่องดำของกลุ่มทั่วไปห้าม MSB ของลอการิทึมแยกหรือไม่

RO: Modelul de cutie neagră de grup generic interzice MSB de logaritm discret?

RU: Запрещает ли общая групповая модель черного ящика MSB дискретного логарифма?

VI: Mô hình hộp đen nhóm chung có cấm MSB logarit rời rạc không?

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.