Efficient implementation of TMVP-based prime field multiplication and its applications to ECC

Download
2019
Taşkın, Halil Kemal
The need for faster and practical cryptography is a research topic for decades. For elliptic curve cryptography, which is proposed independently by Koblitz and Miller in 1985 as a more efficient alternative to RSA, the applications of it in real life started after 2000s. Today, most of the popular applications and protocols like Whatsapp, Signal, iOS, Android, TLS, SSH, Bitcoin etc. make use of elliptic curve cryptography. In this thesis, we present a new representation of finite field multiplication which is one of the basic building blocks for the ECC using Toeplitz matrix-vector product (TMVP) and discuss its arithmetic cost and comparison. In addition, we evaluate the delay complexity of the proposed algorithm when computations are performed using multi-core systems. We also describe how to choose proper prime fields that make use of Toeplitz matrices to get faster field arithmetic. Then, we give parameter choice details to select prime fields that support TMVP operations and propose some prime fields to work on. We propose a new multiplication algorithm over F_{2^{255}-19} where the de-facto standard Curve25519 algorithm is based on. The proposed algorithm for the underlying finite field multiplication exploits the TMVP and achieves salient results. We also introduce the safe curve selection rationale and discuss about attacks on ECC. Next, we propose a new curve choice parameter and safe curve generation process. Finally, we introduce the Curve2663 and give details about its implementation and benchmark results and conclude the thesis.

Suggestions

TMVP-Friendly Primes for Efficient Elliptic Curve Cryptography
Taskin, Halil Kemal; Cenk, Murat (2020-12-03)
The need for faster and practical cryptography is a research topic for decades. In case of elliptic curve cryptography, which was proposed by Koblitz and Miller in 1985 as a more efficient alternative to RSA, the applications in real life started after 2000s. Today, most of the popular applications and protocols like Whatsapp, Signal, iOS, Android, TLS, SSH, Bitcoin etc. make use of Elliptic curve cryptography. One of the important factor for high performance elliptic curve cryptography is the finite field ...
NEW TMVP-BASED MULTIPLICATION ALGORITHMS FOR POLYNOMIAL QUOTIENT RINGS AND APPLICATION TO POST-QUANTUM CRYPTOGRAPHY
Keskinkurt Paksoy, İrem; Cenk, Murat; Department of Cryptography (2022-7-28)
One of the quantum-safe cryptography research areas is lattice-based cryptography. Most lattice-based schemes need efficient algorithms for multiplication in polynomial quotient rings. The fastest algorithm known for multiplication is the Number Theoretic Transform (NTT), which requires certain restrictions on the parameters of the ring, such as prime modulus. Direct NTT application is not an option for some schemes that do not comply with these restrictions, e.g., the two finalists of the PQC standardizati...
High speed VLSI implementation of the Rijndael Encryption Algorithm
Sever, Refik; Aşkar, Murat; Department of Electrical and Electronics Engineering (2003)
This thesis study presents a high speed VLSI implementation of the Rijndael Encryption Algorithm, which is selected to be the new Advanced Encryption Standard (AES) Algorithm. Both the encryption and the decryption algorithms of Rijndael are implemented as a single ASIC. Although data size is fixed to 128 bits in the AES, our implementation supports all the data sizes of the original Rijndael Algorithm. The core is optimised for both area and speed. Using 149K gates in a 0.35-æm standard CMOS process, 132 M...
Analyzes of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber
Aksoy, Berkin; Cenk, Murat; Department of Cryptography (2022-2-28)
Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptography (PQC) Standardization Process, efficient implementations of lattice-based algorithms have been studied extensively. Lattice-based NIST PQC finalists use polynomial or matrix-vector multiplications on the ring with type {Z}_{q}[x] / f(x). For convenient ring types, Number Theoretic Transform (NTT) can be used to perform multiplications as done in Crystals-KYBER among the finalists of the NIST PQC S...
Mutual correlation of NIST statistical randomness tests and comparison of their sensitivities on transformed sequences
Doğanaksoy, Ali; Uğuz, Muhiddin; Akcengiz, Ziya (2017-01-01)
Random sequences are widely used in many cryptographic applications and hence their generation is one of the main research areas in cryptography. Statistical randomness tests are introduced to detect the weaknesses or nonrandom characteristics that a sequence under consideration may have. In the literature, there exist various statistical randomness tests and test suites, defined as a collection of tests. An efficient test suite should consist of a number of uncorrelated statistical tests each of which meas...
Citation Formats
H. K. Taşkın, “Efficient implementation of TMVP-based prime field multiplication and its applications to ECC,” Ph.D. - Doctoral Program, Middle East Technical University, 2019.