Show simple item record

dc.contributor.authorRai, Tapan S.en
dc.date.accessioned2014-03-14T20:08:31Zen
dc.date.available2014-03-14T20:08:31Zen
dc.date.issued2004-03-23en
dc.identifier.otheretd-03262004-082608en
dc.identifier.urihttp://hdl.handle.net/10919/26504en
dc.description.abstractWe develop a public key cryptosystem whose security is based on the intractability of the ideal membership problem for a noncommutative algebra over a finite field. We show that this system, which is the noncommutative analogue of the Polly Cracker cryptosystem, is more secure than the commutative version. This is due to the fact that there are a number of ideals of noncommutative algebras (over finite fields) that have infinite reduced Groebner bases, and can be used to generate a public key. We present classes of such ideals and prove that they do not have a finite Groebner basis under any admissible order. We also examine various techniques to realize finite Groebner bases, in order to determine whether these ideals can be used effectively in the design of a public key cryptosystem.

We then show how some of these classes of ideals, which have infinite reduced Groebner bases, can be used to design a public key cryptosystem. We also study various techniques of encryption. Finally, we study techniques of cryptanalysis that may be used to attack the cryptosystems that we present. We show how poorly constructed public keys can in fact, reveal the private key, and discuss techniques to design public keys that adequately conceal the private key. We also show how linear algebra can be used in ciphertext attacks and present a technique to overcome such attacks. This is different from the commutative version of the Polly Cracker cryptosystem, which is believed to be susceptible to "intelligent" linear algebra attacks.
en
dc.publisherVirginia Techen
dc.relation.haspartrai_etd.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectComputational Algebraen
dc.subjectPublic Key Cryptographyen
dc.subjectNoncommutative Groebner Basesen
dc.subjectInformation Securityen
dc.subjectPolly Crackeren
dc.titleInfinite Groebner Bases And Noncommutative Polly Cracker Cryptosystemsen
dc.typeDissertationen
dc.contributor.departmentMathematicsen
dc.description.degreePh. D.en
thesis.degree.namePh. D.en
thesis.degree.leveldoctoralen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.disciplineMathematicsen
dc.contributor.committeechairGreen, Edward L.en
dc.contributor.committeememberBrown, Ezra A.en
dc.contributor.committeememberHaskell, Peter E.en
dc.contributor.committeememberLinnell, Peter A.en
dc.contributor.committeememberRossi, John F.en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-03262004-082608/en
dc.date.sdate2004-03-26en
dc.date.rdate2004-03-30en
dc.date.adate2004-03-30en


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record