## Abstract

We generalize and extend results obtained by Boneh and Venkatesan in 1996 and by González Vasco and Shparlinski in 2000 on the hardness of computing bits of the Diffie-Hellman key, given the public values. Specifically, while these results could only exclude (essentially) error-free predictions, we here exclude any non-negligible advantage, though for larger fractions of the bits. We can also demonstrate a trade-off between the tolerated error rate and the number of unpredictable bits. Moreover, by changing computational model, we show that even a very small proportion of the most significant bits of the Diffie-Hellman secret key cannot be retrieved from the public information by means of a Las Vegas type algorithm, unless the corresponding scheme is weak itself.

Original language | English |
---|---|

Pages (from-to) | 159-172 |

Number of pages | 14 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 2947 |

Publication status | Published - 2004 |