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

Download
index.pdf
2019
Taşkın, Halil Kemal
Show full item record
329
views
106
downloads
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.
Cryptography., Curves, Elliptic., Toeplitz matrices., Data encryption (Computer science).
http://etd.lib.metu.edu.tr/upload/12623089/index.pdf
https://hdl.handle.net/11511/28017
Graduate School of Applied Mathematics, 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...
Analysis of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber
Aksoy, Berkin; Cenk, Murat (2022-01-01)
Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptog-raphy (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 Zq [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 Standa...
Homomorphic encryption based on the ring learning with errors (RLWE) problem
Keskinkurt, İrem; Cenk, Murat; Department of Cryptography (2017)
The encryption techniques used to ensure data secrecy have been evolving in compliance with the developments in technology and reforming according to need. Nowadays, the increase in the amount of data that should be stored in encrypted form, has led to the need for encryption schemes that provide both the safety and the efficient usability of data. Homomorphic encryption, which enables the ability to make computations on encrypted data, is seen as one of the solutions that can meet this need. In this thesis...
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...
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.
METU IIS - Integrated Information Service open@metu.edu.tr