Fast and Secure Root-Finding for Code-based Cryptosystems

Abstract: In this work we analyze four previously published respec- tively trivial approaches to the task of finding the roots of the error locator polynomial during the decryption operation of code-based en- cryption schemes. We compare the performance of these algorithms and show that optimizations concerning finite field element representations play a key role for the speed of software implementations. Furthermore, we point out a number of timing attack vulnerabilities that can arise in root-finding algorithms, some aimed at recovering the message, others at the secret permutation. We give experimental results showing that manifestations of these vulnerabilities are present in straightforward im- plementations of most of the root-finding variants presented in this work. As a result, we find that one of the variants provides security with re- spect to all vulnerabilities as well as highly competitive results in terms of performance for code parameters that minimize the public key size.


Category :  implementation / side channel attack, timing attack, implementation, code-based cryptography

[non commercial cryptographers]Download this Papers



  1. I am somewhat planning to buy a smartphone on eBay or at retail pricing and then activating it on my basic plan. Is this possible now? Will it remain possible once Alltel becomes Verizon? How do I do this, just buy the phone, activate it online/over phone?

  2. Nice post, I am sure to come bach again in future …

  3. … [Trackback]…

    […] Informations on that Topic: […]…

Sorry, the comment form is closed at this time.

Comments RSS