我们完善并扩展了Ziv的模型和有关单个序列的完全安全加密的结果。根据这个模型,加密器和合法解密器共享不与未经授权的窃听者共享的公共密钥。窃听者知道加密方案,并且具有关于各个明文源序列的一些先验知识。这些先前的知识,结合密码,被窃听者利用,实现有限状态机作为接受或拒绝对明文源的猜测的机制。如果密码不向窃听者提供任何新信息,则加密被认为是完全安全的,该新信息可以增强他们的关于明文的知识,超出他们的现有知识。Ziv表明,完美保密所需的密钥速率基本上受明文序列的有限状态可压缩性的限制较低,通过Lempel-Ziv压缩,然后进行一次性pad加密,可以明显渐近地获得绑定。在这项工作中,我们考虑了一些更一般的有限状态窃听者类别,并得出了完美保密所需的关键速率的相应下限。这些界限比Ziv的界限更严格,更精致,并且它们是使用基于不同的通用无损压缩方案的加密方案获得的。我们还将我们的发现扩展到窃听者和合法解密器可获得辅助信息但加密器可能可用或不可用的情况。
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 a common secret key that is not shared with the unauthorized eavesdropper. The eavesdropper 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 the eavesdropper, who implements a finite-state machine as a mechanism for accepting or rejecting attempted guesses of the plaintext source. The
encryption is considered perfectly secure if the cryptogram does not provide any new information to the eavesdropper that may enhance their knowledge concerning the plaintext beyond their 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 that is clearly asymptotically attained through 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 using
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.