Small generic hardcore subsets for the discrete logarithm: Short secret DL-keys
| Autor: | Claus-Peter Schnorr |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Computational complexity theory
Generator (category theory) business.industry Group (mathematics) Cryptography Division (mathematics) Information theory Computer Science Applications Theoretical Computer Science Combinatorics Discrete logarithm Signal Processing Multiplication ddc:510 business Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 79:93-98 |
| ISSN: | 0020-0190 |
| Popis: | Let G be a group of prime order q with generator g. We study hardcore subsets H⊂G of the discrete logarithm (DL) logg 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 2q generic steps. We show that DL-algorithms for small subsets H⊂G require 12m+o(m) generic steps for almost all H of size #H=m with m⩽q. Conversely, 12m+1 generic steps are sufficient for all H⊂G of even size m. Our main result justifies to generate secret DL-keys from seeds that are only 12 log2q bits long. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect