# Efficient proof of knowledge using Carter-Wegman hash

A verifier wants to ensure, with only little exchange of data with other systems, that a large block of data $$M$$ that the verifier holds is also available to some other system(s). It is not an objective to keep $$M$$ secret, or ensure that the other systems hold $$M$$ in some specified form (it is fine that $$M$$ is stored compressed or distributed in the other systems).

This seems ideal grounds for a protocol as follows, based on my limited understanding of Carter-Wegman hashes:

• verifier chooses a random primitive polynomial $$P$$ of degree $$k$$ with binary coefficients, and publishes/broadcasts it as a message of $$k-1$$ bits (the coefficients of degree $$k$$ and $$0$$ are known to be $$1$$ and need not be sent, and we might compact this a little further by broadcasting the seed for some CSPRNG used to generate $$P$$);
• verifier computes remainder of the polynomial $$M$$ (with the bits of $$M$$ defining the binary coefficients of the polynomial) by polynomial $$P$$ (in other words, the verifier computes a CRC of message $$M$$ per polynomial $$P$$);
• verifier receives a message, and is content if it is of $$k$$ bits that match the remainder that it computed. Of course, that message was computed by the other system(s) proving they collectively hold $$M$$.

Questions:

• Does this protocol meets the stated objective? Can we prove it under some appropriate definition of security, with quantitative bound as a function of $$k$$, and the number $$n$$ of iterations made for the same $$M$$ (and perhaps of the size of the broadcast message if that can be made much lower than $$k$$, and of the size $$m$$ of $$M$$ if that matters)?
• What if we replace the condition that polynomial $$P$$ is primitive by some weaker condition?
• What speed (in bit/second) is possible on an actual CPU, like a modern x86-64 or ARM CPU, with comparison to other means (perhaps, HMAC-MD5 or CBC-MAC-AES with challenge as key)?

Late update: it appears the scheme is Rabin fingerprinting, or closely related to that (a difference is that in Rabin fingerprinting, the polynomial is chosen irreducible, not necessarily primitive; and that Rabin fingerprints uses proper padding, which I forgot: my technique fails to prove that the number of initial 0 bits is known by the provers).

• I suspect that working with polynomials will have similar properties to working with integers. $\hspace{.94 in}$ – user991 Nov 24 '14 at 8:10
• @Ricky Demer: I guess you are suggesting that the challenge is (the seed of) some random prime $N$, and the response $M\bmod N$. That seems to works with odds of forgery $2^{-\log_2(N)}$ if $N<log_2(m)\log_2(\log(m))$ where $m$ is the bit size of $M$, or something on that tune; but I doubt this can be made computationally competitive. Using a smooth $N$ can be more efficient (by using the CRT) but is less secure, because an adversary might pre-compute $M$ modulo small primes, then discard $M$. – fgrieu Nov 24 '14 at 9:39
• No; I just mean that a similar analysis may work. $\;$ – user991 Nov 24 '14 at 9:44