Weyl Gröbner basis cryptosystems [Elektronische Ressource] / Rashid Ali

DissertationWeylGrobner¨ BasisCryptosystemsRashidAliEingereicht anderFakultat¨ fur¨ InformatikundMathematikderUniversitat¨ PassaualsDissertationzurErlangungdesGradeseinesDoktorsderNaturwissenschaftenSubmittedtothe DepartmentofInformaticsandMathematicsofthe Universitat¨ PassauinPartialFulfilmentoftheRequirementsfor the Degreeof aDoctorintheDomainofScienceBetreuer/Advisor:Prof. Dr. MartinKreuzerUniversitat¨ PassauApril2011Tomy Parents,my wife Samina,my kids, Ahmed and Maheen ...AbstractIn this thesis, we shall consider a certain class of algebraic cryptosystems calledGrobner¨ Basis Cryptosystems. In 1994, Koblitz introduced the Polly Cracker cryp-tosystem that is based on the theory of Grobner¨ basis in commutative polynomialsrings. The security of this cryptosystem relies on the fact that the computation ofGrobner¨ basisis,ingeneral,EXPSPACE-hard. CryptanalysisofthesecommutativePolly Cracker type cryptosystems is possible by using attacks that do not requirethe computation of Grobner¨ basis for breaking the system, for example, the attacksbased on linear algebra. To secure these (commutative) Grobner¨ basis cryptosys-tems against various attacks, among others, Ackermann and Kreuzer introduced ageneral class of Grobner¨ Basis Cryptosystems that are based on the difficulty ofcomputing module Grobner¨ bases over general non-commutative rings.