Question

One-way functions and Pseudorandom Generators [12 Marks] Let G be a cyclic group of prime order q generated by g∈G. Consider the following Pseudorandom Generator defined over (Z²q ,G³) as G(α,β)=(g^α ,g^β ,g^αβ). Show that G is a secure Pseudorandom Generator assuming that the Decisional Diffie-Hellman assumption holds in G.

Answer 1

To show that G is a secure Pseudorandom Generator, we need to prove its one-way property and pseudorandomness property.

Step-by-step explanation:

In order to show that G is a secure Pseudorandom Generator assuming that the Decisional Diffie-Hellman assumption holds in G, we need to demonstrate that G satisfies the necessary conditions of a secure Pseudorandom Generator.

Step 1: One-Way Property

We need to prove that it is computationally difficult to compute the inputs (α,β) given the output (g^α, g^β, g^αβ). This can be done by assuming the existence of an adversary A who can efficiently invert the function.

Step 2: Pseudorandomness Property

We need to demonstrate that the output of the function G is indistinguishable from random. This can be proved using a statistical test, where we compare the distribution of the output with the uniform distribution over G³. If the output passes the test, it is considered pseudorandom.