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 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.
Volltext Dateien herunterladen
Weitere Dienste
| Verfasserangaben: | Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30-12119 |
| ISSN: | 0020-0190 |
| Dokumentart: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Jahr der Fertigstellung: | 2000 |
| Datum der Erstveröffentlichung: | 27.09.2000 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 04.07.2005 |
| Freies Schlagwort / Tag: | computational complexity; cryptography; discrete logarithm (DL); generic algorithms; generic complexity; hardcore subsets |
| Seitenzahl: | 7 |
| Erste Seite: | 1 |
| Letzte Seite: | 7 |
| Bemerkung: | Erschienen in: Information processing letters, 79.2001, S. 93-98 |
| Quelle: | Publ. in Information Processing Letter 79 (2001), pp. 93-98 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| HeBIS-PPN: | 400057387 |
| Institute: | Informatik und Mathematik / Mathematik |
| DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
