Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice (Q2384012)

A polynomial reconstruction (PR) problem with parameters \(\{k,n,w\}\) over a finite field \(\mathbb F\) is: given \(n\) points \((x_i,y_i)\in\mathbb F\times\mathbb F\), find a polynomial \(p(x)\in\mathbb F[x]\) of degree \(< k\) such that \(p(x_i) \neq y_i\) for at most \(w\) values of \(i\). As is well-known, decoding of many error-correcting codes, and in particular Reed-Solomon codes, can be viewed as a PR problem. \textit{D. Augot} and \textit{M. Finiasz} [ EUROCRYPT 2003. Lect. Notes Comput. Sci. 2656, 229--240 (2003; Zbl 1038.94519)] proposed a public key cryptosystem based on Reed-Solomon codes, implemented as instances of PR. Grosso mode, in their approach the public key is a noisy Reed-Solomon encoded message-too noisy for any decoding to be possible-and the private key is knowledge of the positions of the errors in the public key. This approach allows a smaller key size than in most other cryptosystems based on error-correcting codes. However, \textit{J.-S. Coron} [PKC 2004. Lect. Notes Comput. Sci. 2947, 14--27 (2004; Zbl 1198.94088)] showed how to break the system with a cyphertext- only attack. The paper under review views the Augot-Finiasz scheme from a more general perspective, and considers possible improvements. It is shown that none of these is secure-each upgrade yields to a corresponding upgrade of the Coron attack. To quote the authors: ``We develop our presentation as a ping-pong game between a cryptosystems designer and a cryptanalyst. To avoid any misunderstanding our goal is not to design a new cryptosystem, but rather using the design and cryptanalysis steps as a methodology for exploring the general approach.''