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.