  We refine and extend Ziv's model and results regarding perfectly secure
encryption of individual sequences. According to this model, the encrypter and
the legitimate decrypter share in common a secret key, not shared with the
unauthorized eavesdropper, who is aware of the encryption scheme and has some
prior knowledge concerning the individual plaintext source sequence. This prior
knowledge, combined with the cryptogram, is harnessed by eavesdropper which
implements a finite-state machine as a mechanism for accepting or rejecting
attempted guesses of the source plaintext. The encryption is considered
perfectly secure if the cryptogram does not provide any new information to the
eavesdropper that may enhance its knowledge concerning the plaintext beyond his
prior knowledge. Ziv has shown that the key rate needed for perfect secrecy is
essentially lower bounded by the finite-state compressibility of the plaintext
sequence, a bound which is clearly asymptotically attained by Lempel-Ziv
compression followed by one-time pad encryption. In this work, we consider some
more general classes of finite-state eavesdroppers and derive the respective
lower bounds on the key rates needed for perfect secrecy. These bounds are
tighter and more refined than Ziv's bound and they are attained by encryption
schemes that are based on different universal lossless compression schemes. We
also extend our findings to the case where side information is available to the
eavesdropper and the legitimate decrypter, but may or may not be available to
the encrypter as well.
