期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a ``hidden'' element of a
finite field \Fp of p elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo p of t for several values of t selected
uniformly at random from \Fp. We use some recent bounds
of exponential sums to generalize this algorithm to the
case when t is selected from a quite small subgroup of
\Fp. Namely, our results apply to subgroups
of size at least p13+ for all primes p
and to subgroups of size at least p for
almost all primes p, for any fixed 0.
We also use this generalization to improve (and correct)
one of the statements of the aforementioned work about the
computational security of the most significant bits
of the Diffie--Hellman key.
关键词：Bit security, cryptography, Diffie-Hellman key, exponential sums, hidden number problem
