You are looking at a specific version 20100730:035448 of this paper. See the latest version.

Paper 2010/421

Binomial Sieve Series -- a Prospective Cryptographic Tool

Gideon Samid

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. sieve, authentication, computational load, pattern-recognition, compression
Contact author(s)
gideon samid @ case edu
History
2010-07-30: received
Short URL
https://ia.cr/2010/421
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.