Refine
Language
- English (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
- computational complexity (3) (remove)
Institute
- Mathematik (3)
- Informatik (2)
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.
We call a vector x/spl isin/R/sup n/ highly regular if it satisfies =0 for some short, non-zero integer vector m where <...> is the inner product. We present an algorithm which given x/spl isin/R/sup n/ and /spl alpha//spl isin/N finds a highly regular nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no short relation m~ of length less than /spl alpha//2 exists for points x~ within half the x'-distance from x. The integer relation m for x' is for random x up to an average factor 2/sup /spl alpha//2/ a shortest integer relation for x'. Our algorithm uses, for arbitrary real input x, at most O(n/sup 4/(n+log A)) many arithmetical operations on real numbers. If a is rational the algorithm operates on integers having at most O(n/sup 5/+n/sup 3/(log /spl alpha/)/sup 2/+log(/spl par/qx/spl par//sup 2/)) many bits where q is the common denominator for x.
We show lower bounds for the signature size of incremental schemes which are secure against substitution attacks and support single block replacement. We prove that for documents of n blocks such schemes produce signatures of \Omega(n^(1/(2+c))) bits for any constant c>0. For schemes accessing only a single block resp. a constant number of blocks for each replacement this bound can be raised to \Omega(n) resp. \Omega(sqrt(n)). Additionally, we show that our technique yields a new lower bound for memory checkers.