1
$\begingroup$

What are the families of codes frequently used in McEliece cryptosystem or its variants? I know that binary Goppa codes were used in the original system but many codes with efficient decoding algorithm can be used. Are there any other requirements on the code or generator matrix for that matter? I don't care about parameters used, just the names of families like Goppa, Hamming , Reed Solomon etc. is enough.

$\endgroup$
  • $\begingroup$ From what I know the binary goppa codes stood the test of time best... $\endgroup$ – SEJPM Jul 19 '17 at 20:12
2
$\begingroup$

The modern approach is still to use binary Goppa codes. See, e.g., McBits from 2013:

Daniel J. Bernstein, Tung Chou, Peter Schwabe. "McBits: fast constant-time code-based cryptography." Pages 250–272 in Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings, edited by Guido Bertoni, Jean-Sébastien Coron. Lecture Notes in Computer Science 8086, Springer, 2013. ISBN 978-3-642-40348-4.

https://binary.cr.yp.to/mcbits-20130616.pdf

Other proposals, such as Niederreiter's using generalized Reed–Solomon codes, have been broken:

V.M. Sidelnikov, S.O. Shestakov. "On insecurity of cryptosystems based on generalized Reed–Solomon codes." Discrete Mathematics and Applications, 2(4), pp. 439–444, 1992.

https://doi.org/10.1515/dma.1992.2.4.439 (paywalled, sorry!)

$\endgroup$
  • $\begingroup$ are there any other proposals for use of other codes? I get that Goppa codes are the ones that are mostly used but the proof for security of system doesn't involve much restrictions on structure of code. Also when one referral to 'variants' of McEliece in what sense these variants. I thought these variations are in terms of underlying code. $\endgroup$ – Root Jul 20 '17 at 7:35
  • $\begingroup$ I'm not aware of proposals to use other codes. They would have to demonstrate better performance for the same security to be useful. I don't follow what you're asking about variants—you used the term ‘variant’ in your original message, and I didn't echo it. You could vary the code, as in McEliece over GRS codes instead of McEliece over Goppa codes, or you could vary the construction, as in the Niederreiter cryptosystem, which is like McEliece backwards. $\endgroup$ – Squeamish Ossifrage Jul 21 '17 at 2:47
  • $\begingroup$ @Root: A preprint proposing McEliece over QC-MDPC (quasi-cyclic moderate-density parity-check) codes, for ephemeral key exchange only, allegedly thwarting all existing attacks on such codes, recently appeared on the IACR archive: Paulo S.L.M. Barreto, Shay Gueron, Tim Gueneysu, Rafel Misoczki, Edoardo Persichetti, Nicolas Sendrier, and Jean-Pierre Tillich, ‘CAKE: Code-based Algorithm for Key Encapsulation’, IACR Cryptology ePrint Archive: Report 2017/757. Earlier proposals based on QC-MDPC have been broken, as is this one for non-ephemeral public key use. $\endgroup$ – Squeamish Ossifrage Aug 8 '17 at 5:03
  • $\begingroup$ just a follow-up question : the paper doesn't mention any particular decoder. Is there a standard decoder for such codes? Also is the new system quantum secure? The original McEliece is shown as secure under quantum attacks. $\endgroup$ – Root Sep 5 '17 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.