Asymmetric cryptosystem employing paraunitary matrices

Abstract

Disclosed are multivariate paraunitary asymmetric cryptographic systems and methods based on paraunitary matrices. The cryptographic systems and methods are based on formulating a system of multivariate polynomial equations by paraunitary matrices. These matrices are a family of invertible polynomial matrices that can be completely parameterized and efficiently generated by primitive building blocks. Using a general formulation involving paraunitary matrices, a one-way function is designed that operates over the fields of characteristic two. Approximations made to a paraunitary matrix result in a trapdoor one-way function that is efficient to evaluate, but hard to invert without secret information about the trapdoor. An exemplary implementation operates on the finite field GF(256). In this example, the message block includes 16 to 32 symbols from GF(256), i.e., the block size is an integer between 16 and 32. The ciphertext block takes its elements from the same field and has at least 10 extra symbols.