HFE based multi-variate quadratic cryptosystems and Dembowski Ostrom polynomials

Abstract

Harayama ve Friesen, ikinci dereceden çok değişkenli kriptosistemlerine doğrusal binom atağını sunmuşlardır ve sonlu cisim F2 üzerindeki bu sistemler için zayıf Dembowski Ostrom(DO) polinomlarını tanımlamışlardır. Sonsuz elemanlı zayıf DO polinom sınıflarının olduğu varsayımını öne sürmüşlerdir ve bu sınıfların sıralanmasını açık problem olarak sunmuşlardır. Çalışmamızda, doğrusal binom atağını, herhangi bir asal p karakteristiğine sahip sonlu cisim Fp üzerindeki ikinci dereceden çok-değiskenli kriptosistemlere genelleştiriyoruz ve genel durum için zayıf DO polinomlarını yeniden tanımlıyoruz. Bu genel sistemler için sonsuz elemanl zayf DO polinom sınıfın, cebirsel fonksiyon cisimleri üzerindeki oldukça bozuk ikinci dereceden formları ve Artin-Schreir eğrilerini kullanaraksunuyoruz. Bu tezde ayrıca HFE tabanlı ikinci dereceden çok-değiskenli kriptosistemlerhakkında detaylı bir inceleme sunulmaktadır ve bu problemin ilgili Min-Rank ve IP problemlerine dönüştürülmesi ile Gröbner bazları ve matris/vektör islemleri içeren yakın zamanda sunulan bazı ataklar tartışılmaktadır. HFE kirptosistemleri ile Ore polinomlarının bağlantlarına da değinilmistir.Anahtar Kelimeler: doğrusal binom atak, zayıf Dembowski Ostrom Polinomlar,Saklı Cisim Denklemleri, İkinci Dereceden çok Değişkenli Kriptosistemler

Harayama and Friesen proposed linearised binomial attack for multivariate quadraticcryptosystems and introduced weak Dembowski Ostrom(DO) polynomials inthis framework over the finite field F2. They conjecture about the existence ofinfinite class of weak DO polynomials and presented the open problem of enumeratingtheir classes. We extend linearised binomial attack to multivariate quadraticcryptosystems over Fp for any prime p and redefine the weak DO polynomials forgeneral case. We identify an infinite class of weak Dembowski Ostrom polynomialsfor these systems by considering highly degenerate quadratic forms over algebraicfunction fields and Artin-Schreir type curves to achieve our results. This thesisalso presents a comprehensive survey of HFE based multivariate quadratic publickey cryptosystems and discusses some recent cryptanalytic attacks involvingGrobner bases and matrix/vector operations by reducing the involved problem torelated MinRank and IP problem. We also mention a possible connection amongOre's p-polynomials and HFE cryptosystems identied in the work of Coulter.Key Words: linearised binomial attack, weak Dembowski Ostrom polynomials,Hidden Field Equations Cryptosystems, Multivariate Quadratic Cryptosystems