TY  - JOUR
A1  - Schnorr, Claus Peter
T1  - Small generic hardcore subsets for the discrete logarithm : short secret DL-keys
N2  - Let G be a group of prime order q with generator g. We study hardcore subsets H is include in G of the discrete logarithm (DL) log g in the model of generic algorithms. In this model we count group operations such as multiplication, division while computations with non-group data are for free. It is known from Nechaev (1994) and Shoup (1997) that generic DL-algorithms for the entire group G must perform p2q generic steps. We show that DL-algorithms for small subsets H is include in G require m/ 2 + o(m) generic steps for almost all H of size #H = m with m <= sqrt(q). Conversely, m/2 + 1 generic steps are su±cient for all H is include in G of even size m. Our main result justifies to generate secret DL-keys from seeds that are only 1/2 * log2 q bits long.
KW  - computational complexity
KW  - cryptography
KW  - discrete logarithm (DL)
KW  - generic algorithms
KW  - generic complexity
KW  - hardcore subsets
Y1  - 2000
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4288
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-12119
SN  - 0020-0190
N1  - Erschienen in: Information processing letters, 79.2001, S. 93-98
SP  - 1
EP  - 7
ER  -