Noncommutative Grobner basis cryptosystems
LE3 .A278 2010
2010
Hooper, Jeff
Acadia University
Master of Science
Masters
Mathematics and Statistics
Mathematics & Statistics
A noncommutative version of the Grobner basis Polly Cracker cryptosystem was proposed in a doctoral thesis by Rai, \Innite Grobner Bases And Noncommutative Polly Cracker Cryptosystems." The description includes a conjecture designed to identify good sources of cryptographically suitable keys. We review the algebraic theory underpinning Grobner basis cryptosystems and describe the various systems that have been proposed. We discuss known attacks on these systems and the countermeasures to defend against their use. Rai's conjecture, designed to counter the problem of having a public key generating an ideal for which a Grobner basis can be found, is the focus of our work. Through computations using GAP software, we explore the viability of this conjecture. The results demonstrate that generating keys at random is not likely to produce suitable results; conversely, following the constraints recommended by Rai is computationally straightforward and produces useful keys. Attempts to nd Grobner bases for ideals generated by keys constructed using this method did not succeed.
The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.
https://scholar.acadiau.ca/islandora/object/theses:142