Small generic hardcore subsets for the discrete logarithm: Short secret DL-keys

Let G be a group of prime order q with generator g. We study hardcore subsets H subset of G of the discrete logarithm (DL) log(g) in the model of generic algorithms. In this model we count group operations such as multiplication and division, while computations with non-group data are for free. It is known from Nechaev {[}Math. Notes 55 (1994) 165] and Shoup {[}Lecture Notes in Comp. Sci., Vol. 1233, Springer, Berlin, 1997, p. 256] that generic DL-algorithms for the entire group G must perform root 2q generic steps. We show that DL-algorithms for small subsets H subset of G require 1/2m + o(m) generic steps for almost all H of size #H = m with m less than or equal to rootq. Conversely, 1/2m + 1 generic steps are sufficient for all H subset of G of even size m. Our main result justifies to generate secret DL-keys from seeds that are only 1/2 log(2) q bits long. (C) 2001 Elsevier Science B.V. All rights reserved.