A New Public-Key Cryptosystem Based on the Problem of Reconstructing p—Polynomials

摘要

In this paper we present a new public key cryptosystem whose security relies on the intractability of the problem of reconstructing p-polynomials. This is a cryptosystem inspired from the Augot-Finiasz cryptosystem published at Eurocrypt 2003. Though this system was broken by Coron, we show However, in our case, we show how these attacks can be avoided, thanks to properties of rank metric and p-polynomials. Therefore, public-keys of relatively small size can be proposed (less than 4000 bits).