  We consider repeated communication sessions between a RFID Tag (e.g., Radio
Frequency Identification, RFID Tag) and a RFID Verifier. A proactive
information theoretic security scheme is proposed. The scheme is based on the
assumption that the information exchanged during at least one of every n
successive communication sessions is not exposed to an adversary. The Tag and
the Verifier maintain a vector of n entries that is repeatedly refreshed by
pairwise xoring entries, with a new vector of n entries that is randomly chosen
by the Tag and sent to the Verifier as a part of each communication session.
The general case in which the adversary does not listen in k > 0 sessions among
any n successive communication sessions is also considered. A lower bound of
n(k+1) for the number of random numbers used during any n successive
communication sessions is proven. In other words, we prove that an algorithm
must use at least n(k+1) new random numbers during any n successive
communication sessions. Then a randomized scheme that uses only O(n log n) new
random numbers is presented. A computational secure scheme which is based on
the information theoretic secure scheme is used to ensure that even in the case
that the adversary listens in all the information exchanges, the communication
between the Tag and the Verifier is secure.
