Private Key Extension of Polly Cracker Cryptosystems

Abstract

In 1993 Koblitz and Fellows proposed a public key cryptosystem, Polly Cracker, based on the problem of solving multivariate systems of polynomial equations, which was soon generalized to a Dröbner basis formulation. Since then a handful of improvements of this construction has been proposed. In this paper it is suggested that security, and possibly efficiency, of any Polly Cracker-type cryptosystem could be increased by altering the premises regarding private- and public information.