Constant-Factor Improvements Sample Clauses

Constant-Factor Improvements. In this section we propose improvements that reduce the round complexity by a factor of 4 and the entropy loss by a factor of up to 18, making this protocol considerably more practical. Reducing the length of the extracted MAC key k2 Note that choosing the length of k2 as above increases the entropy loss of the protocol by almost a factor of 3. By reworking the analysis of Phase 1 using the notion of average min-entropy (similar to the analysis in Appendix C ), we can show that requiring k2 to be longer than twice the communication in Phase 1, as discussed above, is unnecessary. Using the same notation that we used in the protocol description, we let σ2 denote the tag of the MAC. To succeed in forging it, the adversary Xxx needs to successfully change σ2 to σ2j . In addition, in Phase 1 she is also allowed to query Xxxxx and Xxx, say, T times. Protocol Auth implicitly imposes the constraint that Xxx needs to also respond to T such queries. Let us denote her queries by (q1,... , qT ) and responses by (q1j ,... , qTj ). We analyze the security of phases I and II jointly by looking at the average min-entropy of (σ2j , (q1j ,... , qTj )) given (σ2, (q1,... , qT )). It turns out to be roughly λk2 − T − λσ2 , which makes the likelihood that Eve to completes phase I and comes up with σ2j is no more than 2−L if λk > 2L + T . Working Base 4. Recall that in ith round of Xxxx, Xxx sends Xxxxx an extractor seed sufficient to extract L + 1 bits, and Xxxxx responds with either nothing or the extracted string, depending on the value of the ith bit of the message being transmitted. We improve this by encoding the message transmitted by Auth (namely, the MAC key k1) in base 4 rather than in base 2. Bob will send Xxxxx an extractor seed sufficient to extract 3L + 1 bits, and Xxxxx will respond with nothing, the first L + 1 bits, the first 2L +1 bits, or all 3L + 1 bits depending on the ith digit of the message. This protocol works for strings that are “balanced” in base 4: i.e., messages M of length κM whose base-4 digits whose digits add up to 1.5κM . It takes κM rounds and loses 2.5LκM bits of entropy, while maintaining the same security. This improves the number of rounds by a factor 2 and the entropy loss by a factor of 3/2.5 = 1.2, because κM is half of the length that M would have if written in binary (the techniques used to balance a message in base 2 are also applicable in base 4, and increase the length by essentially the same ratio).