### Fast and Secure Root Finding for Code-based Cryptosystems

Falko Strenzke

##### Abstract

In this work we analyze five previously published respectively trivial approaches and two new hybrid variants for the task of finding the roots of the error locator polynomial during the decryption operation of code-based encryption 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 support. We give experimental results of software implementations showing that manifestations of these vulnerabilities are present in straightforward implementations of most of the root-finding variants presented in this work. As a result, we find that one of the variants provides security with respect to all vulnerabilities as well as competitive computation time for code parameters that minimize the public key size.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
side channel attacktiming attackimplementationcode-based cryptography
Contact author(s)
fstrenzke @ crypto-source de
fstrenzke @ gmx de
History
2012-08-07: last of 3 revisions
See all versions
Short URL
https://ia.cr/2011/672

CC BY

BibTeX

@misc{cryptoeprint:2011/672,
author = {Falko Strenzke},
title = {Fast and Secure Root Finding for Code-based Cryptosystems},
howpublished = {Cryptology ePrint Archive, Paper 2011/672},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/672}},
url = {https://eprint.iacr.org/2011/672}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.