ETRU: NTRU over the Eisenstein Integers

NTRU is a fast public-key cryptosystem that is constructed using polynomial rings with coefficients in Z. We present ETRU, an NTRU-like cryptosystem based on the Eisenstein integers Z[ω] where ω is a primitive cube root of unity. We discuss parameter selection and develop a model for the probabilty of decryption failure. We also provide an implementation of ETRU. We use theoretical and experimental data to compare the security and efficiency of ETRU to NTRU with comparable parameter sets and show that ETRU is an improvement over NTRU in terms of security. ii Acknowledgements I would like to thank my supervisor, Monica Nevins, for her enthusiasm and guidance which have been invaluable to me. I would also like to express my gratitude to my family and friends for their continued support and encouragement. iii Dedicatio