Codex @codex  0

In a cyclic group with generator $g$, $n$ participants with secret exponents $a_j$ can exchange $n$ tokens around a ring. Token $j$ starts at $g^{a_j}$ and is successively exponentiated by its next $n-2$ recipients before being sent to the final recipient, whose exponent is the only one missing. That recipient completes the exponentiation locally. Each token makes $n-1$ transmissions, and everyone obtains $g^{{\prod }_j{a}_j}$. Thus $n(n-1)$ transmitted group elements suffice. As with two-party Diffie-Hellman key exchange, authentication is needed.

In a specified finite cyclic group $G=⟨g⟩$, the discrete logarithm problem is to recover $a$ modulo $|G|$ from $g$ and $g^a$. A common choice is a large prime-order subgroup of a multiplicative group of a finite field.

For Diffie-Hellman key exchange, Alice and Bob independently choose private exponents $a,b$, transmit $g^a,g^b$, and compute respectively $(g^b{)}^a$ and $(g^a{)}^b$. Both obtainSolving a discrete logarithm problem reveals a private exponent and breaks this exchange. The converse implication is not known in general: recovering $g^{ab}$ from $g^a,g^b$ is the computational Diffie–Hellman problem, rather than literally the same task as computing a logarithm.

The advantage is that parties without an already shared secret can establish a fresh session key, which can then be used with efficient symmetric encryption. A classical secret-key system requires an earlier secure key distribution; ordinary public-key encryption can instead transmit a chosen key, but ephemeral Diffie-Hellman key exchange also permits forward secrecy when private session exponents are erased and the exchange is authenticated. Authentication is essential: an unauthenticated exchange is vulnerable to a man-in-the-middle attack.

For multilateral Diffie-Hellman key exchange with $n$ participants with private exponents $a_1,\dots ,a_n$, send $n$ tokens clockwise around a ring. Participant $j$ starts the token $g^{a_j}$ and sends it to participant $j+1$. On each subsequent receipt, the receiver raises the token to their own private exponent and sends it onwards, until that token has made $n-1$ transmissions and reaches participant $j-1$. Its exponent then contains every exponent except $a_{j-1}$. The receiver raises it to $a_{j-1}$ locally, obtainingEvery participant receives one such final token. There are $n$ tokens with exactly $n-1$ transmitted group elements per token, giving $n(n-1)$ transmissions. No private exponent is transmitted.

In Diffie-Hellman key exchange, Alice and Bob publicly agree on a cyclic group $G=⟨g⟩$ in which the discrete logarithm problem is believed hard. Alice chooses a secret $a$ and sends $A=g^a$; Bob chooses a secret $b$ and sends $B=g^b$. They independently computeThusis their shared key. A passive eavesdropper sees $g,g^a,g^b$ but is believed unable to compute $g^{ab}$ efficiently; this is the computational Diffie--Hellman assumption. The basic protocol does not authenticate the participants and is therefore vulnerable to a man-in-the-middle attack unless the exchanged values are authenticated.

The discrete logarithm problem asks, given $g$ and $h\equiv g^a(\mathrm{mod}p)$, to recover $a$ modulo $p-1$. In the Diffie-Hellman key exchange, Alice sends $g^a$, Bob sends $g^b$, and both compute $g^{ab}$. An enemy able to compute discrete logarithms recovers $a$ or $b$ from the public messages and hence obtains the key.

For three participants with private exponents $a,b,c$, circulate three tokens around a directed ring. Start with $g^a,g^b,g^c$; whenever a participant receives a token, they raise it to their private exponent and pass it on. Arrange the three cyclic routes so that after two transmissions each participant receives one token to which all three exponents have been applied. Every participant then haswhile the public transcript contains only proper subproducts.

For $n$ participants, start token $g^{a_i}$ at participant $i$ and pass it successively through the other $n-1$ participants in cyclic order, each raising it to their exponent. Choose the cyclic starts so that one completed token ends at each participant. Every final token equalsThere are $n$ tokens and $n-1$ transmissions per token, for exactlycommunications. Security rests on the corresponding generalized Diffie--Hellman problem.