Paper 2010/421

Binomial Sieve Series -- a Prospective Cryptographic Tool

Gideon Samid


A Binomial Sieve Series (BSS) is an infinite monotonic set of natural numbers, b1, b2, ( 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.

Available format(s)
Publication info
Published elsewhere. sieve, authentication, computational load, pattern-recognition, compression
Contact author(s)
gideon samid @ case edu
2010-07-30: received
Short URL
Creative Commons Attribution


      author = {Gideon Samid},
      title = {Binomial Sieve Series -- a Prospective Cryptographic Tool},
      howpublished = {Cryptology ePrint Archive, Paper 2010/421},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.