Cryptography

The security of the current public-key cryptographic schemes, based on integer factorization and discrete logarithm problems, is expected to be totally broken with the development of quantum computers utilizing Shor’s algorithm. As a result, The National Institute of Standards and Technology (NIST) initiated the Post-Quantum Cryptography (PQC) standardization process in 2016, inviting researchers to submit candidate algorithms that are both resistant to quantum attacks and efficient for real world applications. Researchers have since studied various aspects of the candidate algorithms, such as their security against quantum attacks and efficient implementation on different platforms.
In this thesis, we investigate the practical aspects of Post-Quantum Cryptography and contribute to several topics. First, we focus on the knapsack problem and its security under classical and quantum attacks. Second, we improve the secure biometric template generation algorithm NTT-Sec, proposing an enhanced version, NTT-Sec-R, and providing an in-depth design and security analysis. Third, we work on optimizing implementations of the post-quantum secure signature scheme LESS and polynomial inversion algorithms for code-based schemes. Finally, we analyze a proposed countermeasure for the exposure model of SIKE, the isogeny-based scheme that is a candidate in NIST’s Round 4.

An efficient scalar multiplication algorithm is vital for elliptic curve cryptosystems. The first part of this dissertation focuses on a scalar multiplication algorithm based on scalar recodings resistant to timing attacks. The algorithm utilizes two recoding methods: Recode, which generalizes the non-zero signed all-bit set recoding, and Align, which generalizes the sign aligned columns recoding. For an ℓ-bit scalar split into d subscalars, our algorithm has a computational cost of ⌈⌈ℓ logk(2)⌉/d⌉ point additions and k-scalar multiplications and a storage cost of kd−1(k − 1) – 1 points on E. The “split and comb” method further optimizes computational and storage complexity. We find the best setting to be with a fixed base point on a Twisted Edwards curve using a mix of projective and extended coordinates, with k = 2 generally offering the best performance. However, k = 3 may be better in certain applications. The second part of this dissertation is dedicated to constant-time polynomial inversion algorithms in Post-Quantum Cryptography (PQC). The computation of the inverse of a polynomial over a quotient ring or finite field is crucial for key generation in post-quantum cryptosystems like NTRU, BIKE, and LEDACrypt. Efficient algorithms must run in constant time to prevent side-channel attacks. We examine constant-time algorithms based on Fermat’s Little Theorem and the Extended GCD Algorithm, providing detailed time complexity analysis. We find that the constant-time Extended GCD inversion algorithm is more efficient, performing fewer field multiplications. Additionally, we explore other exponentiation algorithms similar to the Itoh-Tsuji inversion method, which optimizes polynomial multiplications in the BIKE/LEDACrypt setup. Recent results on hardware implementations are also discussed.

Cryptographic algorithms are being developed and incorporated into network security protocols to provide secure communication over vulnerable mediums like the Internet. These protocols utilize secret and public key mechanisms to carry out data integrity, confidentiality, authentication, and non-repudiation.
The urge to deploy cryptosystems on low-end devices, based on the constantly growing Internet of Things (IoT) world, requires optimal design and implementation of cryptographic algorithms and protocols to achieve small communicational and computational cost, while preserving the privacy of the transmitted data. Scenarios of low bandwidth, constrained memory, and limited processing power are common when targeting embedded devices; however, security requirements are still present due to the sensitive information that may be communicated. In this thesis, we address the need for optimal cryptographic primitives implementation design in terms of computing capabilities, energy and power consumption, and memory usage to accommodate the deployment of cryptographical systems on resource-constrained devices.

Euclidean lattices have attracted considerable research interest as they can be used to construct efficient cryptographic schemes that are believed to be quantum-resistant. The NTRU problem, introduced by J. Hoffstein, J. Pipher, and J. H. Silverman in 1996 [16], serves as an important average-case computational problem in lattice-based cryptography. Following their pioneer work, the NTRU assumption and its variants have been used widely in modern cryptographic constructions such as encryption, signature, etc.
Let Rq = Zq[x]/ (xn + 1) be a quotient polynomial ring. The standard NTRU problem asks to recover short polynomials f, g E Rq such that h - g/ f (mod q), given a public key h and the promise that such elements exist. In practice, the degree n is often a power of two. As a generalization of NTRU, the Module-NTRU problems were introduced by Cheon, Kim, Kim, and Son (IACR ePrint 2019/1468), and Chuengsatiansup, Prest, Stehle, Wallet, and Xagawa (ASIACCS '20).
In this thesis, we presented two post-quantum Digital Signature Schemes based on the Module-NTRU problem and its variants.

In 1994 when Peter Shor released his namesake algorithm for factoring and solving the discrete logarithm problem he changed cryptography forever. Many of the state-of-the-art cryptosystems for internet and other computerized communications will become obsolete with the advent of quantum computers. Two distinct approaches have grown to avoid the downfall of secure communication: quantum cryptography which is based in physics and information theory, and post-quantum cryptography which uses mathematical foundations believed not to be weak against even quantum assisted adversaries. This thesis is the culmination of several studies involving cryptanalysis of schemes in both the quantum and post-quantum paradigms as well as mathematically founded constructions in the post-quantum regime.
The first two chapters of this thesis on background information are intended for the reader to more fully grasp the later chapters. The third chapter shows an attack and ultimate futility of a variety of related quantum authentication schemes. The fourth chapter shows a parametric improvement over other state-of-the-art schemes in lattice based cryptography by utilizing a different cryptographic primitive. The fifth chapter proposes an attack on specific parameters of a specific lattice-based cryptographic primitive. Finally, chapter six presents a construction for a fully homomorphic encryption scheme adapted to allow for privacy enhanced machine learning.

To address the increased interest in crypto hardware accelerators due to performance and efficiency concerns, implementing hardware architectures of different public-key cryptosystems has drawn growing attention. Pure hardware methodology enhances architecture’s performance over a hardware/software co-design scheme at the cost of a more extended design cycle, reducing the flexibility, and demands customized data paths for different protocol-level operations. However, using pure hardware architecture makes the design smaller, faster, and more efficient. This dissertation mainly focuses on designing crypto accelerators that can be used in embedded systems and Internet-of-Things (IoT) devices where performance and efficiency are critical as a hardware accelerator to offload computations from the microcontroller units (MCU). In particular, our objective is to create a system-on-chip (SoC) crypto-accelerator with an MCU that achieves high area-time efficiency. Our implementation can also be integrated as an off-chip solution; however, other criteria, such as performance, are often as important or more important than efficiency in the external crypto-chip design, which is beyond of this work. Not only does our architecture inherently provide protection against timing and simple power analysis (SPA) attacks, but also some advanced security mechanisms to avoid differential power analysis (DPA) attacks are included, which is missing in the literature. In a nutshell, the contributions are summarized as follows:

Cryptography relies on hard mathematical problems that current conventional computers cannot solve in a feasible amount of time. On the other hand, quantum computers, with their quantum mechanic construction, are presumed to be able to solve some of these problems in a reasonable amount of time. More specifically, the current hard problems that public key cryptography relies upon are expected to be easily broken during the quantum era, a time when large-scale quantum computers are available. To address this problem ahead of time, researchers and institutions have proposed post-quantum cryptography (PQC), which is an area of research that focuses on quantum-resistant public key cryptography algorithms. One of the candidates in the NIST PQC standardization process is SIKE, an isogeny-based candidate. The main advantage of SIKE is that it provides the smallest key size out of all the NIST PQC candidates at the cost of performance. Therefore, the development of hardware accelerators for SIKE is very important to achieve high performance in time-constrained applications. In this thesis, we implement several accelerators for SIKE and its primitives using different design approaches, all of which are suitable for different applications. We deliver significant enhancements to SIKE’s most expensive component, the modular multiplier. We design SIKE using a hardware-based approach and a software-hardware codesign approach, the latter of which utilizes a RISC-V processor. We also design SIKE with multi-level security level support for applications that require support of multiple security levels with minimal area usage. We enclose our performance and area results, which provide a reference to evaluate our work with other implementations.

It is well known that in the near future, a large-scale quantum computer will be unveiled, one that could be used to break the cryptography that underlies our digital infrastructure. Quantum computers operate on quantum mechanics, enabling exponential speedups to certain computational problems, including hard problems at the cornerstone of our deployed cryptographic algorithms. With a vulnerability in this security foundation, our online identities, banking information, and precious data is now vulnerable. To address this, we must prepare for a transition to post-quantum cryptography, or cryptosystems that are protected from attacks by both classical and quantum computers. This is a dissertation proposal targeting cryptographic engineering that is necessary to deploy isogeny-based cryptosystems, one known family of problems that are thought to be difficult to break, even for quantum computers. Isogeny-based cryptography utilizes mappings between elliptic curves to achieve public-key encryption, digital signatures, and other cryptographic objectives necessary to support our digital infrastructure's security. This proposal focuses on three aspects of isogeny-based cryptography: 1) cryptographic engineering of isogeny-based cryptosystems; 2) developing and optimizing security-enabling isogeny applications; and 3) improving the security from known and emerging implementation attacks. By improving each of these aspects, we are providing confidence in the deployability of isogeny-based cryptography and helping to prepare for a post-quantum transition.

As the cryptographic community turns its focus toward post-quantum cryptography, the demand for classical cryptographic schemes such as Elliptic Curve Cryptography (ECC) remains high. ECC is mature, well studied, and used in a wide range of applications such as securing visits to web pages through a web browser, Bitcoin, and the Internet of Things (IoT). In this work we present an optimized implementation of the Edwards Curve Digital Signature Algorithm (EdDSA) operations Key Generation and Sign using the Ed25519 parameter on the ARM Cortex-M4, and we discuss the optimization of field and group arithmetic to produce high throughput cryptographic primitives. In addition, we discuss several techniques for optimizing scalar multiplication, and present timing and memory consumption for each, as well as comparisons to other works. Our fastest implementation performs an Ed25519 Key Generation operation in 250,785 cycles and signing in 435,426 cycles utilizing 6.1 kB of additional Read Only Memory (ROM) space.

An adversary armed with a quantum computer has algorithms[66, 33, 34] at their disposal, which are capable of breaking our current methods of encryption. Even with the birth of post-quantum cryptography[52, 62, 61], some of best cryptanalytic algorithms are still quantum [45, 8]. This thesis contains several experiments on the efficacy of lattice reduction algorithms, BKZ and LLL. In particular, the difficulty of solving Learning With Errors is assessed by reducing the problem to an instance of the Unique Shortest Vector Problem. The results are used to predict the behavior these algorithms may have on actual cryptographic schemes with security based on hard lattice problems. Lattice reduction algorithms require several floating-point operations including multiplication. In this thesis, I consider the resource requirements of a quantum circuit designed to simulate floating-point multiplication with high precision.