Hidden Number Problems

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.

Name thesis:degree_name

PhD

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Mathematics

Grantor dc:publisher

ResearchSpace@Auckland

Year dc:date.issued

2017

Author dc:creator

• Shani, Barak

Advisor dc:contributor.advisor

• Galbraith, S

Statement dc:rights

• Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.

Licence dc:rights.uri

• https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

Handle dc:identifier.uri

https://hdl.handle.net/2292/33133

OAI identifier oai:identifier

oai:researchspace.auckland.ac.nz:2292/33133