Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice
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.
- scientific article; zbMATH DE number 2086625
- Public Key Cryptography - PKC 2006
- scientific article; zbMATH DE number 2085200
- Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
- Cryptanalyzing the Polynomial-Reconstruction Based Public-Key System Under Optimal Parameter Choice
- How to avoid the Sidel'nikov-Shestakov attack
- A note on the Sidelnikov-Shestakov attack of Niederreiter scheme
- scientific article; zbMATH DE number 1088909
- On the edge-independence number and edge-covering number for regular graphs
- scientific article; zbMATH DE number 4008275
- Cryptanalyzing the Polynomial-Reconstruction Based Public-Key System Under Optimal Parameter Choice
- Decoding of Reed Solomon codes beyond the error-correction bound
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- scientific article; zbMATH DE number 2009958 (Why is no real title available?)
- scientific article; zbMATH DE number 2086625 (Why is no real title available?)
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Public Key Cryptography – PKC 2004
- The tail of the hypergeometric distribution
- The non-gap sequence of a subcode of a generalized Reed-Solomon code
- RSA, Dickson, LUC and Williams: a study on four polynomial-type public-key cryptosystems
- scientific article; zbMATH DE number 2009958 (Why is no real title available?)
- scientific article; zbMATH DE number 2085200 (Why is no real title available?)
- scientific article; zbMATH DE number 2086625 (Why is no real title available?)
- Implicit Polynomial Recovery and Cryptanalysis of a Combinatorial Key Cryptosystem
- Cryptanalyzing the Polynomial-Reconstruction Based Public-Key System Under Optimal Parameter Choice
- Coding and Cryptography
- Public Key Cryptography – PKC 2004
- Cryptanalysis of Ivanov-Krouk-Zyablov cryptosystem
This page was built for publication: Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2384012)
