Dissertation/Thesis Abstract

On efficient computation of Grobner bases
by Gash, Justin M., Ph.D., Indiana University, 2008, 206; 3330795
Abstract (Summary)

On October 2, 2000 the National Institute of Standards and Technology chose to adopt a new cryptographic algorithm as the standard for the United States government. This new system was called Rijndael, named after its creators Vincent Rijmen and Joan Daemon. Though it remains unbroken, cryptanalysts are using so-called Grobner-basis attacks in an attempt to break it. Thus, the onus is now on finding Grobner bases quickly.

In 2002 J.C. Faugere published an algorithm called F5 that found Grobner bases dramatically quicker in most cases; however, in some cases, his program failed to terminate. The problem posed is two-fold: (1) Can F5 be improved so that it terminates? (2) Can the hypotheses for termination be tightened?

My research has produced a modified F5 algorithm (called F5t) that guarantees termination in all cases. In addition I demonstrate a current accepted major theorem in Grobner basis theory is false. I replace the erroneous theorem by a new theorem, proving that a slightly modified F5 can be made to terminate (correctly) over finite fields.

Indexing (document details)
Advisor: Koh, Jee
Commitee: Dadok, Jiri, Haile, Darrell, Leivant, Daniel
School: Indiana University
Department: Mathematics
School Location: United States -- Indiana
Source: DAI-B 69/10, Dissertation Abstracts International
Subjects: Mathematics, Computer science
Keywords: F5, F5t, Grobner bases, Rewritten, S-polynomial
Publication Number: 3330795
ISBN: 978-0-549-86939-9
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy