Protocol Interactive Message Authentication Auth Clause Samples

Protocol Interactive Message Authentication Auth. The [RW03] authentication protocol allows two parties who share the same string R to authenticate a message M , even if R has very little entropy. ≥ We generalize this protocol slightly (to use general extractors instead of the specific polynomial authentication function) and present it in Figure 1. We as- sume that Ext is an average-case extractor that takes seeds of length q, and outputs L + 1-bit strings that are 2−L−1-close to uniform as long as the input has sufficient entropy h (in particular, h 3L+1 suffices if one is using universal hashing as the extractor). For our purposes, it suffices to assume that the length | | of M and the number of ones in it (i.e., its Hamming weight wt(M )) are known to Bob. If M is known but wt(M ) is not, M can be first encoded as a balanced string (i.e., a string with the same number of zeros and ones), by encoding, for example, a 0 as 01 and a 1 as a 10. This doubles the length of M .3 | | We note that [RW03] present a technique that can be used even if M is unknown (namely, encoding M as a string that becomes balanced only at the end), but we will not need it here. ˜ Each round of the protocol reveals L + 1 bits of information correlated to R if Mi = 0, and 2L + 1 bits of information of information correlated to R if Mi = 1. Hence, by ▇▇▇▇▇ 2, the adversary’s uncertainty about R will be sufficient for the extractor to work until the last round as long as H∞(R|E) ≥ 3L + 1 + (L + 1)(λM + wt(M )), and by Lemma 1 the ai and bi values will have entropy L from the adversary’s point of view. The intuition for the security of this protocol is that ▇▇▇ cannot answer a random query xi or yi with probability greater than 2−L because of the entropy of the answers, and hence can neither remove zero bits (because challenges to Bob keep him synchronized) nor insert one bits (because ▇▇▇▇▇ is required to answer a challenge for each one). She can insert zero bits and change zeros to ones, but that is taken care of by the assumption that Bob knows λM and wt(M ). ƒ We do not formally define or prove security of this protocol, as the proof is essentially the same as in [RW03]. The probability that ▇▇▇ succeeds in trans- mitting M j = M to Bob and Bob does not reject (or ▇▇▇▇▇ rejects and Bob accepts) is at most 2−L. ƒ We note the following security property observed in [RW04]. Consider a setting where, because of ▇▇▇’s malicious interference, Bob does not have the same R as ▇▇▇▇▇ does, but instead some (possibly correlated) Rj. The pro...