Security Analysis of the Unbalanced Oil and Vinegar Signature Scheme

Abstract

Due to advancements in quantum computer algorithms, the cryptographic community is exploring alternatives to traditional hardness assumptions, such as the discrete logarithm problem. One such assumption is the Multivariate Quadratic (MQ) problem, which is used by a number of cryptographic primitives, including the Unbalanced Oil and Vinegar (UOV) signature scheme. Apart from MQ, UOV uses another, less understood, hardness assumption which we call the polynomial equivalence problem. The reliance on an open problem and simplicity of the scheme make UOV an excellent subject for cryptographic research. This work studies the UOV construction and methods of solving multivariate systems of nonlinear equations that underlie the security of the scheme. The thesis is split into three parts: key space of UOV, polynomial system solving, and the polynomial equivalence problem. The contributions include a complete classification of sustaining transformations, a study of Gröbner bases complexity estimation, and implementations of algorithms. Security assessment of UOV is presented in the final chapter.