Paper 2010/421 Original: eprint.iacr.org/2010/421 ↗

Binomial Sieve Series -- a Prospective Cryptographic Tool

Abstract

A Binomial Sieve Series (BSS) is an infinite monotonic set of natural numbers, b1, b2, .....bn ( bi < b(i+1) ) generated, ('naturally') from any two natural numbers (x, y <= x) . If one repeatedly counts bi elements over the set X= 1,2,…,x (recycled counting) and eliminates each time the element of X that stops each round of counting, then the surviving element of X is y. Every natural number, per any x, is associated with a certain survivor. We prove that per any x all BSS are infinite and approach an equal size, regardless of the identity of the survivor element y. These infinite series (in count and length) have no simple pattern, their disorder is reminiscent of primes. We suggest some intriguing cryptographic applications based on the poor predictability of the next element in each series, combined with good predictability of the computational load to develop the series (by users and by the cryptanalyst). Using x as a shared secret, and a random, per-session, y, Alice and Bob may mark successive messages between them with the next element of the respective BSS, thereby mutually authenticating themselves throughout their conversation. Other cryptographic possibilities are outlined.