Hidden Number Problems

Abstract

The hidden number problem is the problem of recovering an unknown group element (the "hidden number") given evaluations of some function on products of the hidden number with known elements in the group. This problem enjoys a vast variety of applications, and provides cross-fertilisation among different areas of mathematics. Bit security is a research field in mathematical cryptology that studies leakage of information in cryptographic systems. Of particular interest are public-key cryptosystems, where the study revolves around the information about the private keys that the public keys leak. Ideally no information is leaked, or more precisely extraction of partial information about the secret keys is (polynomially) equivalent to extraction of the entire keys. Accordingly, studies in this field focus on reducing the problem of recovering the private key to the problem of recovering some information about it. This is done by designing algorithms that use the partial information to extract the keys. The hidden number problem was originated to study reductions of this kind. This thesis studies the hidden number problem in different groups, where the functions are taken to output partial information on the binary representation of the input. A special focus is directed towards the bit security of Diffie-Hellman key exchange. The study presented here provides new results on the hardness of extracting partial information about Diffie-Hellman keys.