Enhancement of Nth degree truncated polynomial ring for improving decryption failure

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...

Full description

Saved in:

Bibliographic Details
Main Author:	Gaithuru, Juliet Nyokabi
Format:	Thesis
Language:	English
Published:	2019
Subjects:	QA75 Electronic computers Computer science
Online Access:	http://eprints.utm.my/id/eprint/96161/1/JulietNyokabiGaithuruPSC2019.pdf.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.96161
record_format	uketd_dc
spelling	my-utm-ep.961612022-07-04T07:38:23Z Enhancement of Nth degree truncated polynomial ring for improving decryption failure 2019 Gaithuru, Juliet Nyokabi QA75 Electronic computers. 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. 2019 Thesis http://eprints.utm.my/id/eprint/96161/ http://eprints.utm.my/id/eprint/96161/1/JulietNyokabiGaithuruPSC2019.pdf.pdf application/pdf en public http://dms.library.utm.my:8080/vital/access/manager/Repository/vital:142135 phd doctoral Universiti Teknologi Malaysia Faculty of Engineering - School of Computing
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA75 Electronic computers Computer science
spellingShingle	QA75 Electronic computers Computer science Gaithuru, Juliet Nyokabi Enhancement of Nth degree truncated polynomial ring for improving decryption failure
description	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.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Gaithuru, Juliet Nyokabi
author_facet	Gaithuru, Juliet Nyokabi
author_sort	Gaithuru, Juliet Nyokabi
title	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_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_sort	enhancement of nth degree truncated polynomial ring for improving decryption failure
granting_institution	Universiti Teknologi Malaysia
granting_department	Faculty of Engineering - School of Computing
publishDate	2019
url	http://eprints.utm.my/id/eprint/96161/1/JulietNyokabiGaithuruPSC2019.pdf.pdf
_version_	1747818643122552832

Enhancement of Nth degree truncated polynomial ring for improving decryption failure

Similar Items