Enhancement of Nth degree truncated polynomial ring for improving decryption failure

Thesis (PhD. (Computer Science))

Bibliographic Details
Main Author: Gaithuru, Juliet Nyokabi
Format: Thesis
Language:English
Published: Universiti Teknologi Malaysia 2024
Subjects:
Online Access:http://openscience.utm.my/handle/123456789/965
_version_ 1796848939795742720
author Gaithuru, Juliet Nyokabi
author_facet Gaithuru, Juliet Nyokabi
author_sort Gaithuru, Juliet Nyokabi
collection OpenScience
description Thesis (PhD. (Computer Science))
first_indexed 2024-03-05T17:35:11Z
format Thesis
id oai:openscience.utm.my:123456789/965
institution Universiti Teknologi Malaysia - OpenScience
language English
last_indexed 2024-03-05T17:35:11Z
publishDate 2024
publisher Universiti Teknologi Malaysia
record_format dspace
spelling oai:openscience.utm.my:123456789/9652024-01-15T13:00:28Z Enhancement of Nth degree truncated polynomial ring for improving decryption failure Gaithuru, Juliet Nyokabi Public key cryptography Data encryption (Computer science)—Mathematics Computer security—Research Thesis (PhD. (Computer Science)) Nth Degree Truncated Polynomial (NTRU) is a public key cryptosystem constructed in a polynomial ring with integer coefficients that is based on three main key integer parameters N; p and q. However, decryption failure of validly created ciphertexts may occur, at which point the encrypted message is discarded and the sender re-encrypts the messages using different parameters. This may leak information about the private key of the recipient thereby making it vulnerable to attacks. Due to this, the study focused on reduction or elimination of decryption failure through several solutions. The study began with an experimental evaluation of NTRU parameters and existing selection criteria by uniform quartile random sampling without replacement in order to identify the most influential parameter(s) for decryption failure, and thus developed a predictive parameter selection model with the aid of machine learning. Subsequently, an improved NTRU modular inverse algorithm was developed following an exploratory evaluation of alternative modular inverse algorithms in terms of probability of invertibility, speed of inversion and computational complexity. Finally, several alternative algebraic ring structures were evaluated in terms of simplification of multiplication, modular inversion, one-way function properties and security analysis for NTRU variant formulation. The study showed that the private key f and large prime q were the most influential parameters in decryption failure. Firstly, an extended parameter selection criteria specifying that the private polynomial f should be selected such that f(1) = 1, number of 1 coefficients should be one more or one less than -1 coefficients, which doubles the range of invertible polynomials thereby doubling the presented key space. Furthermore, selecting q 2:5754 f(1)+83:9038 gave an appropriate size q with the least size required for successful message decryption, resulting in a 33.05% reduction of the public key size. Secondly, an improved modular inverse algorithm was developed using the least squares method of finding a generalized inverse applying homomorphism of ring R and an (N x N) circulant matrix with integer coefficients. This ensured inversion for selected polynomial f except for binary polynomial having all 1 coefficients. This resulted in an increase of 48% to 51% whereby the number of invertible polynomials enlarged the key space and consequently improved security. Finally, an NTRU variant based on the ring of integers, Integer TRUncated ring (ITRU) was developed to address the invertiblity problem of key generation which causes decryption failure. Based on this analysis, inversion is guaranteed, and less pre-computation is required. Besides, a lower key generation computational complexity of O(N2) compared to O(N2(log2p+log2q)) for NTRU as well as a public key size that is 38% to 53% smaller, and a message expansion factor that is 2 to15 times larger than that of NTRU enhanced message security were obtained. Faculty of Engineering - School of Computing 2024-01-15T04:51:46Z 2024-01-15T04:51:46Z 2019 Thesis Dataset http://openscience.utm.my/handle/123456789/965 en application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf Universiti Teknologi Malaysia
spellingShingle Public key cryptography
Data encryption (Computer science)—Mathematics
Computer security—Research
Gaithuru, Juliet Nyokabi
Enhancement of Nth degree truncated polynomial ring for improving decryption failure
title Enhancement of Nth degree truncated polynomial ring for improving decryption failure
title_full Enhancement of Nth degree truncated polynomial ring for improving decryption failure
title_fullStr Enhancement of Nth degree truncated polynomial ring for improving decryption failure
title_full_unstemmed Enhancement of Nth degree truncated polynomial ring for improving decryption failure
title_short Enhancement of Nth degree truncated polynomial ring for improving decryption failure
title_sort enhancement of nth degree truncated polynomial ring for improving decryption failure
topic Public key cryptography
Data encryption (Computer science)—Mathematics
Computer security—Research
url http://openscience.utm.my/handle/123456789/965
work_keys_str_mv AT gaithurujulietnyokabi enhancementofnthdegreetruncatedpolynomialringforimprovingdecryptionfailure