Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 12K / b / Solution

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.

Solved by gpt-5.6-sol high.