Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 12K (Coding and Cryptography)

In the Rabin cryptosystem, the public key is $N=pq$ and encryption sends an encoded message $m$ toKnowing $p,q$, the receiver finds the two square roots modulo each prime and combines them with the Chinese remainder theorem to obtain four roots modulo $N$; prescribed redundancy identifies the intended one.

Omicron hasThe Chinese remainder theorem determines $m^2$ uniquely modulo $N{N}^{\prime }$ (assuming the independently generated moduli are coprime; a nontrivial gcd would itself factor them). Since $1\le m<N<N^{\prime }$, one has $m^2<N{N}^{\prime }$, so this residue is the ordinary integer $m^2$. Taking its positive integer square root recovers $m$.

This does not normally decrypt another ciphertext sent under only one modulus. The recovered pair reveals no nontrivial square root collision modulo that modulus and hence supplies no factorization; breaking a single Rabin instance remains equivalent to factoring its modulus.

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.