Public-private key encryption using two sparse matrices and an invertible dense matrix

摘要

A method for an efficient cryptosystem which is implemented with two sparse matrices, where the number of non-zero elements is relatively few, an invertible dense matrix, where the number of non-zero elements per row is of the same order as the matrix size, and a corruption vector. A dense matrix, constructed by the three matrices, and the statistical properties of the corruption vector constitute the public key. This specific construction and decrypting strategy allows for a secure communication and for a reliable and efficient decryption. The method of the present invention can be represented as a Hamiltonian of a physical Ising-type system; this allows one to gain useful insight from the physical description of the system.