HFE based multi-variate quadratic cryptosystems and Dembowski Ostrom polynomials

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Edebiyat Fakültesi, Matematik Bölümü, Türkiye

Tezin Onay Tarihi: 2013

Öğrenci: BİLAL ALAM

Eş Danışman: OĞUZ YAYLA

Danışman: FERRUH ÖZBUDAK

Özet:

Harayama and Friesen proposed linearised binomial attack for multivariate quadratic cryptosystems and introduced weak Dembowski Ostrom(DO) polynomials in this framework over the finite fi eld F2. They conjecture about the existence of infi nite class of weak DO polynomials and presented the open problem of enumerating their classes. We extend linearised binomial attack to multivariate quadratic cryptosystems over Fp for any prime p and redefi ne the weak DO polynomials for general case. We identify an in finite class of weak Dembowski Ostrom polynomials for these systems by considering highly degenerate quadratic forms over algebraic function fields and Artin-Schreir type curves to achieve our results. This thesis also presents a comprehensive survey of HFE based multivariate quadratic publickey cryptosystems and discusses some recent cryptanalytic attacks involving Grobner bases and matrix/vector operations by reducing the involved problem to related MinRank and IP problem. We also mention a possible connection among Ore's p-polynomials and HFE cryptosystems identifi ed in the work of Coulter.