2013/01/09 by S. P. Christmas, Christmas, S. P., Russell Leidich +2
Computer Science · #Algorithms and Data Compression #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Logic, programming, and type systems #Parallel Computing and Optimization Techniques #cs.CR
paper · pdf · doi:10.48550/arxiv.1301.1739
arxiv created 2013/01/09 · openalex publication_date 2013/01/09 · arxiv updated 2013/01/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.