Multivariate Quadratic Cryptosystems

Abstract

Vi beskriver egenskapene til multivariate ligningssystemer, og både egenskapene til Grøbnerbaser, og hvordan man beregner dem. Videre beskriver vi to multivariate kvadratiske kryptosystemer, kryptosystemet Matsumoto-Imai og kryptosystemet HFE. Til slutt beskriver vi to angrep mot kryptosystemet Matsumoto-Imai, der det første angrepet er et direkte angrep basert på Grøbnerbaser, og det andre angrepet utnytter hvordan kryptosystemet er konstruert.

We describe the properties of multivariate system of polynomials, and both the properties of Gröbner bases, and how to calculate them. Furthermore, we describe two multivariate quadratic cryptosystems, the Matsumoto-Imai cryptosystem and the HFE cryptosystem. Finally, we describe two attacks against the Matsumoto-Imai cryptosystem, where the first attack is a direct attack based on Gröbner bases, and the second attack takes advantage of how the cryptosystem is constructed.