Common use of Proof sketch Clause in Contracts

Proof sketch. The proof of this theorem relies on the theory of typical sequences7 and is similar to the proof of Theorem 8, which is a special case of this theorem, but the technical details are omitted from this extended abstract. In order to authenticate a k-bit message by an l = 2k-bit authenticator using m = 4k bits of Xn (or of Y n when Bob is the sender), the described approach based on error correcting codes can be used to select the positions of a subsequence [Xi ; : : : ; Xi ] of Xn. The receiver accepts the message if and only if the sequence of pairs [(Xi1 ; Yi1 ); : : : ; (Xil ; Yil )] is -typical for the distribution PXY for some suitable small . One can prove that for every distribution PXY Z that is neither X-simulatable nor Y -simulatable by ▇▇▇, there exists a positive such that for su ciently large k ▇▇▇'s cheating probability is arbitrarily small. The same argument as in the proof of Theorem 8 can be used to prove that the ratio of bits needed for authentication and of bits used for secret-key agreement vanishes asymptotically.