Facebook Instagram Twitter RSS Feed PodBean Back to top on side

A sharp proof of unicity distance for Markoff sources

In: Tatra Mountains Mathematical Publications, vol. 25, no. 3
Otokar Grošek - Sergio A. Herrera-Garcia - Karol Nemoga - Ladislav Satko
Detaily:
Rok, strany: 2002, 81 - 89
O článku:
The unicity distance of a symmetric cryptosystem, denoted by $n0$, is defined to be the value, at which the expected number of spurious keys becomes zero. In words of entropy, if we have at least $n0$ ciphertexts $Y1,Y2,... ,Yn0$ then there is no uncertainty about the used key, i.e., $H(K/Y1,Y2,...,Yn)approx 0$ for all $n≥ n0$. Standard approach to estimate such an $n0$ can be found in [D. Konheim: Cryptograpy. A primer, J. Wiley & Sons, New York, 1981], [D. Stinson: Cryptography. Theory and Practice, CRC Press, Boca Raton, Florida, 1995]. Unfortunately, in this kind of proof there is no specification of the used source, and this bound is not valid in general. It is shown that for a cryptosystem with the key-space $K$, and plaintext alphabet $P$, the following is valid:

$ n0≥ ((łog2|K|) / (Rłog2|P|)) -r(((1) / (R))-1) $

for a stationary Markoff source of the $r$th order with the redundancy $R$. For a general case

$ n0≥ max{n(ε), frac{łog2|K|}{Rłog2{Cal|P|}+ε} } $ ,

where $n(ε)$ is determined by the well known relation (see, e.g., [R. G. Galager: Information Theory and Reliable Communication, J. Wiley, New York, 1968])

$ |((1) / (n))H(A1,A2,...,An) - H| <ε $ .

Ako citovať:
ISO 690:
Grošek, O., Herrera-Garcia, S., Nemoga, K., Satko, L. 2002. A sharp proof of unicity distance for Markoff sources. In Tatra Mountains Mathematical Publications, vol. 25, no.3, pp. 81-89. 1210-3195.

APA:
Grošek, O., Herrera-Garcia, S., Nemoga, K., Satko, L. (2002). A sharp proof of unicity distance for Markoff sources. Tatra Mountains Mathematical Publications, 25(3), 81-89. 1210-3195.