Dissertation
A knapsack-type cryptographic system using algebraic number rings
Washington State University
Doctor of Philosophy (PhD), Washington State University
05/2010
DOI:
https://doi.org/10.7273/000006208
Abstract
Since the advent of the public-key cryptosystem, the search for a secure and efficient scheme has been ongoing. One such system makes use of the classical knapsack problem to implement security. Though very efficient, this system was shown to be insecure. This paper aims to use the underlying knapsack protocol, without the vulnerabilities of previous systems. To achieve such a result, two methods of constructing privates weights and encoding knapsack messages are posited. The first utilizes a new scheme to uniquely represent integers with recurrence sequences. The second uses specific congruence conditions of the weights to represent messages. Both techniques introduce constraints that cannot be modeled by Basis reduction. Thus eliminating its effectiveness. In order to defend against any other specialty attacks, modular multiplication within an algebraic number ring is established and developed to disguise the private weights. This is ultimately a generalization of the disguising in the Merkle-Hellman system to integers in quadratic, bi-quadratic, and higher dimensional rings. Included in this development are issues of complete residue systems, calculating inverses, and number representations. The analysis of this modular multiplication reveals its immunity from attacks which seek to reverse or undo the disguising.
Metrics
4 File views/ downloads
17 Record Views
Details
- Title
- A knapsack-type cryptographic system using algebraic number rings
- Creators
- Nathan Thomas Moyer
- Contributors
- William Webb (Chair)Bala Krishnamoorthy (Committee Member) - Washington State University, Department of Mathematics and StatisticsJudith McDonald (Committee Member) - Washington State University, Graduate School
- Awarding Institution
- Washington State University
- Academic Unit
- Department of Mathematics and Statistics
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 91
- Identifiers
- 99901055122601842
- Language
- English
- Resource Type
- Dissertation