Information Technology Reference
In-Depth Information
Expected
π
-Adic Security Measures of
Sequences
(Extended Abstract)
Andrew Klapper
Department of Computer Science, University of Kentucky,
Lexington, KY 40506-0046, USA
Abstract.
Associated with a class of AFSRs based on a ring
R
and
π ∈ R
, there is a security measure, the
π
-adic complexity of a sequence.
To understand the normal behavior of
π
-adic complexity we can find
the average
π
-adic complexity, averaged over all sequences of a given
period. This has been done previously for linear and
p
-adic complexity.
In this paper we show that when
π
2
= 2, the average
π
-adic complexity
of period
n
sequences is
n − O
(log(
n
)).
Keywords:
feedback with carry shift register, algebraic feedback shift
register, pseudo-randomness, sequence, security measure.
1
Introduction
A variety of measures, such as linear span and 2-adic span, have been proposed
for deciding the cryptographic security of stream ciphers. Recently there has
been interest in understanding the average behavior of such measures. Several
variations have been studied, both for linear and 2-adic span [10,11,12,13]. In this
paper we extend this work to more general
π
-adic span, where
π
is an element
of certain algebraic rings.
Many of these measures arise as follows: We are given a class
of sequence
generators. There is a notion of
size
of a generator with a particular initial state.
This integer should be approximately the number of elements of the output
alphabet needed to represent all states in the execution of the generator starting
at that initial state using some standard encoding of states.
The
F
-span
of a (finite or infinite) sequence is the smallest size of a generator
in the given class that outputs the sequence. Thus the
F
F
-span is an integer.
