Master of Computer Science
School of Computer Science and Software Engineering
Tourloupis, Vasilios Evangelos, Hermite normal forms and its cryptographic applications, Master of Computer Science thesis, School of Computer Science and Software Engineering, University of Wollongong, 2013. https://ro.uow.edu.au/theses/3788
Hermite Normal Form (HNF) matrices are a standard form of integer matrices used in applications such as lattice based cryptography and integer programming. Calculating the HNFs of randomly selected matrices, however, is not efficient and, although polynomial algorithms exist to address this issue, they do not address the private and public key selection process that attempts to search for a reduced public key size. At best, searching for a matrix (private key) whose HNF (public key) is in `minimal' form (that is, it can be expressed as a single column of values) is a trial and error process with only a 40% chance of success.
In this thesis, a way of reducing the trial and error associated with this process is studied. It does so by taking advantage of the incremental nature of Micciancio and Warinschi's algorithm for calculating HNF matrices row by column. The first contribution of this thesis reveals a stochastic observation relating to prime determinants. Specifically, if a leading principal minor of a matrix is prime (that is, if the determinant of a k x k sub-matrix of an n x n matrix is prime), it increases the probability of the next (or (k + 1)-th) leading principal minor also being prime. Test results have revealed a reduction in the average number of steps of selecting a matrix with a prime determinant by a factor of 12 when compared to the traditional trial and error techniques of selecting such a matrix.
Since the determinant of a matrix does not need to be prime in order for its HNF to be in `minimal' form, an alternative way of reducing the public key matrix is also studied, again taking advantage of the incremental nature of Micciancio and Warinschi's algorithm for calculating HNF matrices.
Finally, this thesis also looks at an alternative way of selecting private key matrices whose HNF public key matrices are in `minimal' form. It does so by using a simple sieving method, which filters prime (or probable prime) determinants of a matrix. With a success rate of about 99%, this method leads more directly to a solution rather than a subset of possible solutions.