Underlying Mathematics of Bitsliced Polynomial Multiplication

This thesis studies the secure polynomial multiplication methods related to the article Batch Binary Weierstrass. For the publication, we wrote a benchmarking software for fast creation of keys for elliptic curve cryptography, with arbitrary field sizes. These keys are created in batches of size equal to the register size of a computer's CPU. We use a programming technique called bitslicing to achieve high-speed polynomial multiplication that is resistant to side-channel attacks. This thesis provides a more comprehensive description of the finite field calculations used in the publication. The multiplication is performed with a divide-and-conquer method, using recursion to split the calculation into simpler subproblems. These subproblems may again be split recursively, leading to a recursion strategy. As some of these strategies are faster to compute than others, I analyze their efficiencies to see how the choice of multiplication strategy affects the overall performance. I also study the cut-off points of recursion in the fastest strategies to see whether our search parameters should be modified. The performance results show that the fastest strategies can lead to significant speed ups, about 15% on average. The analysis of recursion cut-off points showed that we could have reduced our search range by more than three quarters without losing any of the fastest strategies