Security of equal discrete logs (over different bases)

crypcrypcryp

9/15/23, 9:12 AM

I am trying to find a reduction for the following DLOG problem in generic groups. It is a simple generalization but I'm not finding any reference (the closest being the Chaum-Pedersen signature scheme sec 3.2, and BLS signatures without the hashing).

Let $G$ be a cyclic group, and $g, h$ generators. The problem is to find $y$ given $g^y, h^y$.

Looking for any insight or reference.

292

0 + 0

discrete-logarithm

reference-request

Maeher

9/15/23, 9:49 AM

Given $g$ and challenge Choose random $r$ such that $g^r$ is a generator. (Easy in prime order groups.) Set $h:=g^r$ and let $h^y := (g^y)^r$.

crypcrypcryp

9/15/23, 10:13 AM

OK, but how does that help the attacker in finding $y$ (or am I misreading your argument) EDIT: Oh, I got it, thanks.

Maeher

9/15/23, 10:17 AM

It doesn't. That's the point. It's a short description of the reduction from dlog to your problem. This reduction (described in more detail in Daniel S' answer below) shows that your problem is no easier than dlog.

Score:5

Crypto

Daniel S

9/15/23, 9:47 AM

This is equivalent to the discrete logarithm problem.

Clearly if I can solve the discrete logarithm problem, I can solve your problem.

Given an instance of the discrete logarithm problem e.g. given $x=g^y$ find $y$, I can generate an instance of your problem by choosing a random $r$ coprime to the group order and setting $h=g^r$. In this case I can also compute $x^r$ which will be $h^r$.

Thus if I can solve your problem, I can solve the discrete logarithm problem for the group.

0 + 0

crypcrypcryp

9/15/23, 10:19 AM

This assumes that the attacker can select $h$.

Daniel S

9/15/23, 10:26 AM

No, the randomisation of $r$ gives a random instance of your problem conditioned on one of the generators being $g$.

Elon Musk

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

EN: Security of equal discrete logs (over different bases)

TH: ความปลอดภัยของบันทึกที่ไม่ต่อเนื่องเท่ากัน (บนฐานที่ต่างกัน)

RO: Securitatea jurnalelor discrete egale (pe baze diferite)

RU: Безопасность одинаковых дискретных журналов (по разным базам)

VI: Bảo mật các nhật ký rời rạc bằng nhau (trên các cơ sở khác nhau)

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.