The Multiconstraint Knapsack Problem And Its Applications to the Cryptosystem Design
1995
Hochschulschrift
Zugriff:
83
The multiconstraint knapsack problem (MKP) is an NP-complete integer programming problem with many important applications. To study various solution methods of MKP comprehensively, it is essential to efficiently prepare test data with known solution. Therefore, the first motivation and objective of this research is to develop efficient algorithms for generating solved instances of a class of MKP. Furthermore, this problem is closely related to one-way function, which is the core of modern cryptology. Consequently, the second research motivation and objective is to develop cryptosystems based on MKP. It is shown the generation of solved instance of MKP can be transformed to the generation of it linear relaxatin problem with known 0-1 optimal solution. Consequently, the procedure for solving complementary slackness condition is applied to develop three algorithms to generate solved instances of MKP, integr MKP and multiple choice MKP. These three algorithms have same complexity O(mn) where m and n is the number of constraint and variable respectively. Surprisingly, the complementary slackness condition of linear relaxation problem of MKP itself is a private key cipher. Starting from this discovery, four ciphers based on the difficulty of multidimensional subset sum problem (MSSP) are developed and generalized as a framework to build private key cipher based on any generable NP-complete problem. These results are further generalized to frameworks for constructing private key block and stream ciphers based on any one-way function. Finally, the assocaitive property of matrix multiplication of MSSP''s matrix form is applied to develop a general framework to construct public key distribution protocol and public key cipher based on any assocaitive one-way function.
Titel: |
The Multiconstraint Knapsack Problem And Its Applications to the Cryptosystem Design
|
---|---|
Autor/in / Beteiligte Person: | Lin, Yi-Cheng ; 林義誠 |
Link: | |
Veröffentlichung: | 1995 |
Medientyp: | Hochschulschrift |
Sonstiges: |
|