URGENT SOLUTION REQUIRED.

COURSE: Information security aur topic cryptography

5. Random Self Reducibility of QRm (10 points) We complete the proof of the random self reducibility of QRm from the tutorial. Recall that p and q are primes with p=3mod4 and q=3mod4, and m=pq. Let B be an adversary that for every zQRmQNRm+returns the correct answer to whether zQRm or zQNRm+ with probability 1/2+. Construct an adversary C that for every zQRmQNRm+returns the correct answer with probability 0.99. What is the running time of C as a function of the running time of B and ? You should use the following concentration bound (also known as Chernoff bound): Let 1,,n be i.i.d. Bernoulli random variables with expectation p:=E[1]==E[n]. Then for every 0]