Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem

In the (preprocessing) Decisional Diffie-Hellman (DDH) problem, we are given a cyclic group G with a generator g and a prime order N, and want to prepare some advice of S, such that we can efficiently distinguish (gx,gy,gxy) from (gx,gy,gz) in time T for uniformly and independently chosen x,y,z from N. This is a central cryptographic problem whose computational hardness underpins many widely deployed schemes such as the Diffie–Hellman key exchange protocol.