Driving an NP-Complete problem with Combinatorial Decomposition to generate a unique and irreversible bitstring from a single integer seed value
This addresses the need for secure and efficient bitstring generation in cryptography, though it appears incremental as it builds on existing concepts like NP-complete problems and combinatorial methods.
The paper tackles the problem of generating a unique, irreversible bitstring from a single integer seed for applications in cryptography and random number generation, achieving this by using combinatorial decomposition and operations like XOR and ADC to produce bitstrings of arbitrary length with claimed security based on NP-complete complexity.
Generation of an (arbitrarily) long string of bits unique to a given finite-length numerical seed is of great value in the field of random number generation, computer simulations, and other areas of computer science. Extending this idea such that the bitstring cannot be reverse-engineered to recover the original seed value extends the value of such a system to the field of cryptography, as the string can be used directly as an encryption mask, or as the input to some other cryptographic function. The longer the string that can be generated, the closer the system would come to the ideal cryptographic case of the One Time Pad. In this paper we propose a scheme for taking an initial seed (nominally a 128-bit integer, but not restricted to such), and expanding this into a unique bitstring of a length determined by a limit cycle that makes it useful in practical applications. We utilize novel mathematical concepts such as combinatorial decomposition to turn the seed value into unique rotations of a pre-defined table, which are operated on via destructive functions such as exclusive-OR (XOR) and add-with-carry (ADC) to eventually produce the unique bitstring. We assert that the process of iterating the XOR or ADC operation conforms to the known NP-complete problem known as Subset-Sum, meaning that the reversal of the process that produced the bitstring is tantamount to solving the NP-Complete Subset-Sum problem, which in turn is less efficient than the brute-force method of testing every seed value until the corresponding bitstring is found, making the system highly relevant in a cryptographic context.