Linking Decisional Diffie-Hellman, Discrete Logarithm, and Knowledge of Exponent Assumptions

Sean

10/29/22, 2:58 PM

I'm curious about the relation between the Discrete Logarithm and Decisional Diffie-Hellman. Is it safe to have an assumption like the following to link the two?

Given uniformly and independently chosen g^x and g^y, if there is an efficient algorithm that can distinguish g^(xy) and random g^r with non-negligible probability, then there is an extractor that can extract x or y with non-negligible probability?

This looks like a Knowledge of Exponent assumption, however, I want it to tackle the decisional problem. Also it is known that some elliptic curve groups could use pairing to break DDH, in this case, we'll restrict the discussion to groups such as the group of Quadratic Residue over Blum integers.

1 + 0

discrete-logarithm

diffie-hellman

hardness-assumptions

Score:0

Crypto

Ievgeni

10/29/22, 3:09 PM

I think that making this link is not common at all.

A good reason is that for example bilinear group with symmetric pairing (Type 1) can be considered as secure for the discrete-log assumption but it will be never the case for the DDH assumption.

If you receive $(g,x,y,z)$, you can easily check if $e(g,z)=e(x,y)$, and this equality is enough to decide if it is a Diffie-Hellman tuple or not.

To see a more theoretical reason, you can look the Gap-DH assumption (in this problem the adversary has to solve a CDH instance with a DDH oracle) : Thus it has been shown that if for any algebraic adversary, if DLog holds, then Gap-DH is also a hard problem (thus if you replace a CDH instance by a DLog instance it becomes still harder).

You can look this phd page 136 for more details

https://www.iacr.org/phds/index.php?p=detail&entry=1476

And because considering algebraic adversary seemed to me equivalent to the Knowledge of Exponent assumption, thus it would be really weird to make a such link (as far as I understood, it will imply that Dlog is easy, but I'm not completely sure about that).

0 + 5

Sean

10/29/22, 10:24 PM

Thanks for the insights!

Sean

10/29/22, 10:25 PM

Now, what if we restrict the discussion to those groups where the DDH problem is believed to be difficult (e.g., those non-Gap_DH groups)?

Ievgeni

10/30/22, 6:57 AM

I do not understand what do you mean. But do not hesitate to ask a new question with another post, it would be clearer.

Sean

10/30/22, 1:01 PM

I posted another question as below. This explains why I need to link it to Knowledge of Exponent assumption.

Sean

10/30/22, 1:01 PM

The link is below: https://crypto.stackexchange.com/questions/91834/decisional-diffie-hellman-assumption-over-group-of-quadratic-residue

Elon Musk

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

EN: Linking Decisional Diffie-Hellman, Discrete Logarithm, and Knowledge of Exponent Assumptions

TH: การเชื่อมโยงการตัดสินใจ Diffie-Hellman, ลอการิทึมแบบไม่ต่อเนื่องและความรู้เกี่ยวกับสมมติฐานที่เป็นเลขยกกำลัง

RO: Legătura dintre Diffie-Hellman decizional, logaritmul discret și cunoașterea ipotezelor exponenților

RU: Связь алгоритма принятия решений по методу Диффи-Хеллмана, дискретного логарифма и знания предположений об экспоненте

VI: Liên kết Diffie-Hellman quyết định, logarit rời rạc và kiến thức về giả định số mũ

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.