Using an Error-Correction Code for Fast, Beyond-Birthday-Bound Authentication

摘要

In this paper, we describe a new variation of PMAC called PMACX. It generalizes PMAC-with-Parity, a prior work of Yasuda. The most unique feature of PMACX is its parallel MDS (Maximum Distance Separating) matrix multiplication on the input message before the authentication. The scheme is parameterized by a generator matrix for an MDS linear code over GF(2~n). PMACX supports any reasonable choice of the matrix's dimension, and this choice of the parameters reflects the trade-off between efficiency and security. For example, if a 14×12 matrix is used, PMACX will be about 14% slower than PMAC, and when n = 128, q = 2~(32) and ρ = 2~(64), the best known bound for PMAC, O(q~2ρ/2~n), gives a meaningless result, while our bound, O(q~2/2~n + qσρ/2~(2n)) in this case, is still in the reasonable order of 2~(-64). (q~2/2~n + qσρ/2~(2n) ≤ q~2/2~n + q~2ρ~2/2~(2n) = 2~(-64) + 2~(-64) = 2~(-63)) We corroborate the above theoretical observation with implementation results. Our comparative experiment shows that a careful choice of the MDS matrix can make PMACX faster than PMAC-with-Parity, yet reducing the number of keys from 4 to 2 and achieving asymptotically the same security level.