Again, let G be a group with a generator g and order n. Let be the bit length of
ID: 3872406 • Letter: A
Question
Again, let G be a group with a generator g and order n. Let be the bit length of n; assume group operations take time that is polynomial in . Suppose you have an algorithm F0 that runs in time t and computes discrete logarithms for 1% of G: that is, there is a subset H G of size n/100 such that if h H, F0(h) produces logg h. For the remaining 99% of inputs, F0 outputs “fail”. (a) (30 points) Design an algorithm F1 that runs time t+poly() and outputs the discrete logarithm of its input h with probability at least 1% for every h G. The difference between F0 and F1 is that F0 works always for some inputs, while F1 will work sometimes for all inputs. Hint: re-randomize h, then use F0. The previous problem will be useful. (b) (30 points) Now design an algorithm F2 that runs time 500t + poly() and outputs the discrete logarithm of its input h with probability at least 99% for every h G
Explanation / Answer
Suppose that G is a group,
g is a generator,
n is order
hence g G has finite order n. Then for each t <g> the integers m with gm=t form a residue class mod n. Denote it by Log g t.
The discrete logarithm problem is the computational task of finding a representative of this residue class; that is, finding an integer m with gm=t.
here in this problem we are supposed to assume a group operationa that take time that is in polynomial
given in the question that is a bit length of n size
Polynomial-time indexing:
Gen(1n)returns
(f0,f1,...,fk)
where the fi are the descriptions of permutations on a same domain
D,that are chosen uniformly randomly in the set of all permutations of domain
D(we suppose that the description of D is implicitly contained in the description of the permutations)
Generic methods solving the discrete logarithm problem (BSGS, Pollard, Pohlig-Hellman) run in exponential time. The hardness of DLP highly de-pends on the group G but not on the choice of the generator; it is believed to be hard in the multiplicative group of finite fields of large characteristic p
With p1 = 2q and q is prime, in large extension fields of F2, and in elliptic curve and some hyperelliptic curve Jacobian groups