Problem 1. Suppose an adversary A can win the decisional LWE game with probability 1/2+ for non-negligible > 0. Describe another adversary B which wins the decisional LWE game with probability 1 2(n). Problem 2. Suppose an adversary A can win the decisional LWE game with probability 12n.Describe another adversary B which wins the search LWE game with probability 1 2(n).

The Search LWE Game. Let n,qZ be integers such that q=poly(n) is prime, and let be an "error distribution" on Zq. The Search LWE game is played between an adversary A and challenger C as follows. - C chooses a random secret vector sZqn. - Now the game enters the "query phase" where it remains until A decides to move on. While in the query phase, A can request a sample. Every time A requests a sample, C sends back the sample (a,b)ZqnZq which is prepared as follows: aZqn and e are drawn; b=a,s+e. - After leaving the query phase, A sends sZqn to C which signals the completion of the game. We say A wins if s=s. The Decisional LWE Game. Let n,qZ be integers and let be an "error distribution" on Zq. The Search LWE game is played between an adversary A and challenger C as follows. - C chooses a random bit z{0,1}. If z=0,C also draws a random vector sZqn. - Now the game enters the "query phase" where it remains until A decides to move on. While in the query phase, A can request a sample. Every time A requests a sample, C sends back the sample (a,b)ZqnZq which is prepared as follows: - if z=0, then aZqn and e are drawn, and b=a,s+e . if z=1, then aZqn and bZq are drawn randomly. - After leaving the query phase, A sends z{0,1} to C which signals the completion of the game. We say A wins if z=z