Multivariate Signature using Algebraic Techniques

We propose an algebraic framework for designing trap-door one-way functions with applications in multivariate signature schemes. Multivariate schemes are attractive because of their efficiency. The proposed framework involves paraunitary matrices, a special subset of invertible polynomial-matrices. Using the algebraic framework, we propose the general template of paraunitary digital-signature scheme (PDSS). The general framework paves the way for a computational-security analysis of the PDSS. We also propose a practical instance of the PDSS that operates on the field GF (2⁸). The message block and the secret key both consist of 16 symbols from GF (2⁸). The signature is a block of length 26 symbols from GF (2⁸). The complexity analysis of this instance reveals that it is, at least, as efficient as the hidden-field equations (HFE) scheme. In addition, our cryptanalysis shows that the proposed instance is secure