A Survey on Polly cracker systems

Multivariate algebra plays a central role in today's cryptography. The most popular public key cryptosystems based on multivariate polynomials are more or less related to the Matsumoto-Imai scheme dating back to late eighties, the Polly Cracker-like family, arising in the early nineties, proposed an alternative use of multivariate algebra. In this paper, we survey the constructions and results having appeared so far. Our goal is to reevaluate the provocative assertion ``cannot even hope to use Groebner Bases in Public-key Cryptography" made years ago by B. Barkee et al. in their seminal paper noticing that, because of recent uses of Groebner bases in cryptanalysis, it should rather be replaced by ``cannot hope to use Polly Cracker-like systems in cryptography''. We try to explain why one cannot use such schemes for the design of secure and efficient cryptosystems