  Hard lattice problems are predominant in constructing post-quantum
cryptosystems. However, we need to continue developing post-quantum
cryptosystems based on other quantum hard problems to prevent a complete
collapse of post-quantum cryptography due to a sudden breakthrough in solving
hard lattice problems. Solving large multivariate quadratic systems is one such
quantum hard problem.
  Unbalanced Oil-Vinegar is a signature scheme based on the hardness of solving
multivariate equations. In this work, we present a post-quantum digital
signature algorithm VDOO (Vinegar-Diagonal-Oil-Oil) based on solving
multivariate equations. We introduce a new layer called the diagonal layer over
the oil-vinegar-based signature scheme Rainbow. This layer helps to improve the
security of our scheme without increasing the parameters considerably. Due to
this modification, the complexity of the main computational bottleneck of
multivariate quadratic systems i.e. the Gaussian elimination reduces
significantly. Thus making our scheme one of the fastest multivariate quadratic
signature schemes. Further, we show that our carefully chosen parameters can
resist all existing state-of-the-art attacks. The signature sizes of our scheme
for the National Institute of Standards and Technology's security level of I,
III, and V are 96, 226, and 316 bytes, respectively. This is the smallest
signature size among all known post-quantum signature schemes of similar
security.
