Blind coding: authentication frauds from the point of view of rate-distortion theory
Andrea Sgarro · Journal of Discrete Mathematical Sciences and Cryptography · 2001
Surprisingly, the rate-distortion function appears in a powerful lower bound to the probability of an authentication fraud; we show that the link between authentication theory and rate-distortion theory is not just formal, but also conceptual. To this end we introduce the notion of “blind coding”, that is trying to encode a source output which one cannot observe; we show that authentication frauds can be re-interpreted precisely as trying to blind-code the key source, rather than the clearmessage source. We provide a lower bound to the probability of blind coding, which holds true for any value of the admissible distortion level, at least asymptotically. Seeing authentication frauds as a rate-distortion theoretic problem suggests introducing positive distortion levels in a situation when the authentication of communication is certified only after a sufficiently high number of checks has been successful.