semantic security must be achieved against such ¬gurations of the network itself.

an adversary. Such security is called “semantically Sender anonymity can be achieved against

secure against chosen plaintext attack” and writ- computationally restricted eavesdroppers by MIX

ten IND-CPA. The threat of adversary who has networks [1] and against computationally unre-

access to decryption oracle is called chosen cipher- stricted eavesdroppers by DC networks [2, 3].

text attack (CCA). If a public-key scheme is seman- Note that sender anonymity is weaker than

tically secure against an adversary who has access sender unobservability, where the attacker can-

to a decryption oracle before determining the pair not even determine whether or not a participant

of plaintexts m0 and m1 , it is called IND“CCA1. If sends a message. Sender unobservability can be

a public-key scheme is semantically secure against achieved with MIX networks and DC networks by

an adversary who has access to a decryption ora- adding dummy traf¬c.

cle not only before receiving a target ciphertext

Gerrit Bleumer

but also during the guessing stage, then it is de-

¬ned as IND“CCA2. It is regarded that this type

References

of adversary is the most powerful. Therefore the

scheme achieving IND“CCA2 is considered most

[1] Chaum, David (1981). “Untraceable electronic mail,

secure. (There is a restriction on this type of ad-

return addresses, and digital pseudonyms.” Com-

versary, namely that he cannot receive an answer

munications of the ACM, 24 (2), 84“88.

of the target ciphertext from decryption oracle.)

[2] Chaum, David (1985). “Security without identi¬ca-

Besides semantic security, there are related

tion: Transaction systems to make big brother ob-

notions such as non-malleability and plaintext solete.” Communications of the ACM, 28 (10), 1030“

awareness. 1044.

[3] Chaum, David (1988). “The dining cryptographers

Kazue Sako problem: Unconditional sender and recipient un-

traceability.” Journal of Cryptology, 1 (1), 65“75.

Reference

[1] Bellare, M., A. Desai, D. Pointcheval, and P.

SEQUENCES

Rogaway (1998). “Relations among notions of secu-

rity for public-key encryption schemes.” Advances

in Cryptography”CRYPTO™98, Lecture Notes in Sequences have many applications in mod-

Computer Science, vol. 1462, ed. H. Krwawczyk. ern communication systems, including signal

Springer-Verlag, Berlin, 26“45. synchronization, navigation, radar ranging,

Code-Division Multiple-Access (CDMA) systems,

random number generation, spread-spectrum

communications, cryptography, in particular in

SENDER ANONYMITY stream cipher systems.

In stream cipher systems it is essential to

Sender anonymity is achieved in a messaging sys- construct sequences with good random proper-

tem if an eavesdropper who picks up messages ties, long periods, and large linear complexity. To

from the communication line of a recipient cannot achieve many of these goals one often generates

Sequences 561

sequences using linear recurrence relations. The sequence. Then, we can compute the product

period of a sequence {st } is the smallest integer µ

G(x) f — (x) = (s0 + s1 x + s2 x 2 + · · · )

such that st+µ = st for all t. We will explain how

— (1 + fn’1 x + · · · + f1 x n’1 + x n )

the period of a generated sequence is completely

∞

determined by the characteristic polynomial of the

= ct x t .

sequence. For linear sequences the period of the se-

t=0

quences generated can easily be controlled, which

The coef¬cient ct+n of x t+n for any t ≥ 0 becomes

makes them good building blocks in stream cipher

systems. n

ct+n = fi st+i = 0

A linear recursion of degree n with binary coef-

¬cients is given by i=0

as a consequence of the recurrence relation.

n

fi st+i = 0, Hence,

i=0

G(x) f — (x) = φ — (x)

where fi ∈ GF(2) = {0, 1} for 0 < i < n and f0 =

for some polynomial φ — (x) of degree at most n ’ 1.

f = 1. The characteristic polynomial of the recur-

n

Its reciprocal polynomial φ(x) is given by

sion is de¬ned by

φ(x) = s0 x n’1 + (s1 + fn’1 s0 )x n’2 + · · ·

n

f (x) = fi xi . + (sn’1 + fn’1 sn’2 + · · · + f1 s0 )

i=0 n’1 n’1’i

= fi+ j+1 s j xi .

The initial state (s0 , s1 , . . . , sn’1 ) and the given

i=0 j=0

recursion uniquely determines the generated se-

quence. A linear shift register with a characteristic There is a one-to-one correspondence between any

sequence {st } in ( f ) and any polynomial φ — (x) of

polynomial f (x) of degree n generates 2n different

sequences corresponding to the 2n different initial degree ¤ n ’ 1. All sequences generated by f (x)

states and these form a vector space over GF(2) can therefore be described by

which is denoted ( f ).

φ — (x)

deg(φ — (x)) < deg( f ) = n .

( f) =

The maximum period of a sequence generated

f — (x)

by a linear shift register is at most 2n ’ 1. This

(x 3 +

follows since a sequence is completely determined For example, the m-sequence 0010111 in

by n-successive bits in the sequence and period 2n x + 1) can be written

is impossible since n successive zeros implies the

x2

all zero sequence. Sequences with the maximal pe-

1 + x2 + x3

riod 2n ’ 1 are called m-sequences. For example,

= x 2 + x 4 + x 5 + x 6 + x 9 + x 11 + x 12 + · · ·

with initial state (s0 , s1 , s2 ) = (001), then f (x) =

x 3 + x + 1 generates the m-sequence 0010111. = (x 2 + x 4 + x 5 + x 6 )(1 + x 7 + x 14 + · · ·

In particular, a simple consequence of the above

EXAMPLE 1. Let the recursion be

description of ( f ) is that ( f ) ‚ (g) if and only

st+4 + st+3 + st+2 + st+1 + st = 0 (mod 2) if f (x) divides g(x).

The generating function G(x) for a periodic se-

with characteristic polynomial f (x) = x 4 + x 3 + quence of period µ can be written as

x 2 + x + 1. The sequences in ( f ) consists of

G(x) = s0 + s1 x + · · · + sµ’1 x µ’1

the 24 = 16 sequences corresponding to the se-

quences {(0), (00011), (00101), (01111)} and their — (1 + x µ + x 2µ + · · · )

cyclic shifts. s0 + s1 x + · · · + sµ’1 x µ

= .

1 ’ xµ

To analyze properties of linear sequences, we as-

Combining the two expressions for G(x), we obtain

sociate a generating function G(x) to the sequence

the identity

{st }, and let

(x µ ’ 1)φ(x) = σ (x) f (x),

∞

G(x) = st x t .

where σ (x) = s0 x µ’1 + s1 x µ’2 + · · · + sµ’1 , contains

t=0

all the information of a period of the sequence.

Let f — (x) = i=0 fn’i xi be the reciprocal polyno-

n

The period of the polynomial f (x) is the smallest

positive integer e such that f (x) divides x e ’ 1. The

mial of the characteristic polynomial of f (x) of the

562 Sequences

importance of the period e of f (x), is that in order To ¬nd the cycle structure of (gh), suppose (g)

contains d1 cycles of length »1 and (h) contain d2

to ¬nd the period of all the sequences in ( f ), it is

cycles of length »2 . Add in all possible ways the