|
|||||
|
|
Security of the most significant bits of the Shamir message passing scheme |
|
| Authors: | Maria Isabel Gonzá lez Vasco Igor E Shparlinski |
| Institution: | Department of Mathematics, University of Oviedo, Oviedo, 33007, Spain ; Dept. of Computing, Macquarie University, Sydney, NSW 2109, Australia |
| Abstract: | Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a ``hidden' element |
| Keywords: | Shamir message passing scheme bit security exponential sums cryptography |
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 | |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 | |
of a finite field 
of 
elements from rather short strings of the most significant bits of the remainder modulo 
of 
for several values of 
selected uniformly at random from 
. Unfortunately the applications to the computational security of most significant bits of private keys of some finite field exponentiation based cryptosystems given by Boneh and Venkatesan are not quite correct. For the Diffie-Hellman cryptosystem the result of Boneh and Venkatesan has been corrected and generalized in our recent paper. Here a similar analysis is given for the Shamir message passing scheme. The results depend on some bounds of exponential sums.