Underlying Mathematics of Bitsliced Polynomial Multiplication
Vuojärvi, Kide (2021)
2021
Teknis-luonnontieteellinen DI-ohjelma - Master's Programme in Science and Engineering
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2021-11-22
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202111048189
https://urn.fi/URN:NBN:fi:tuni-202111048189
Tiivistelmä
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.
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.