Compression for exact match identification

In this paper, we consider the problem of determining whether sequences X and Y, generated i.i.d. according to P_X × P_Y, are equal given access only to the pair (Y, T(X)), where T(X) is a rate-R compressed version of X. In general, the rate R may not be sufficiently large to reliably determine whether X=Y. We precisely characterize this reliability - i.e., the exponential rate at which an error is made - as a function of R. Interestingly, the exponent turns out to be related to the Bhattacharyya distance between the distributions P_X and P_Y. In addition, the scheme achieving this exponent is universal, i.e. does not depend on P_X, P_Y.