New Classes of Public Key Cryptosystems Constructed on the Basis of Low-Density Multivariate Polynomials - Along with K(I)·Knapsack Scheme

摘要

Extensive studies have been made of the public key cryptosystems based on multivariate polynomials over F{sub}2 and also F{sub}(2{sup}m). However most of the proposed public key cryptosystems based on multivariate polynomials, are proved not secure. In this paper, we construct random multivariate polynomials with relatively small number of terms which will be referred to as low-density multivariate polynomials. We show that the proposed scheme referred to as K(V)·RSE(g)PKC can be secure against the possible attacks, particularly Grobner basis attack. In Appendix, we present a new cryptographic scheme, referred to as K(I)·Knapsack Scheme that can be applied to a wide class of knapsack PKCs.