A hidden number problem in small subgroups |
| |
Authors: | Igor Shparlinski Arne Winterhof |
| |
Institution: | Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia ; RICAM, Austrian Academy of Sciences, Altenbergerstrasse 69, 4040 Linz, Austria |
| |
Abstract: | Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element , where is prime, from rather short strings of the most significant bits of the residue of modulo for several randomly chosen . González Vasco and the first author have recently extended this result to subgroups of of order at least for all and to subgroups of order at least for almost all . Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the multipliers and thus extend this result to subgroups of order at least for all primes . As in the above works, we give applications of our result to the bit security of the Diffie-Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups. |
| |
Keywords: | Hidden number problem Diffie--Hellman key exchange lattice reduction exponential sums Waring problem in finite fields |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|