Why would Carter-Wegman-style message authentication not be broken by P = NP?

Researching about the implications of P = NP to cryptography I found someone say that the only cryptography left standing would be the one time pad and Carter-Wegman-Style message authentication. While the one time pad seems obvious, I am not sure about Carter-Wegman-Style message auth. Can anyone explain this?

• Note that a nonce based Carter-Wegman MAC is no one-way function. – CodesInChaos Jul 14 '16 at 18:51

While the one time pad seems obvious, I am not sure about Carter-Wegman-Style message auth.

What they are talking about is a Carter-Wegman authentication method that uses a stream of random bits as a part of the process (just like a one time pad uses a stream of random bits to encrypt).

Normally, when we implement CW, we use some almost universal (au) hash function, and pair it up with some cryptographical object. The au hash function processes the message being MACed; and then use the cryptographical object to disguise the au hash output.

How this works: using the au hash implies that someone who doesn't know the au hash key cannot generate two messages that have a nontrivial probability of hashing to the same value (and there are a number of constructions where this is provable). However, someone who sees the au hash output can deduce rather a lot; hence we disguise the intermediate au hash to generate the full hash with the cryptographical object.

In a one-time-pad setting, one of the things we could do is replace the cryptographical object with "xor the au-hash with the next set of pad bits"; this also effectively disguises the hash output, and so satisfies the criteria (and an oracle that can do NP cannot recover the au-hash, because (just like the one-time pad), there's not enough information to do so). Note: actually, in this construction, you'd need a delta almost universal hash function; if you care about those details, ask in a separate question.

On the other hand, those two wouldn't be quite the only things that would be left in the cryptography toolbox. In addition, we have:

• Secret Sharing (where if someone has fewer than the requisite number of shares, they literally don't have enough information to reconstruct the secret)

• Some key distribution schemes (where someone issues key shares to parties, two parties can generate the same key, and no one else with fewer than k key shares (where k is a security parameter) have enough information to reconstruct their secret.

• "you'd need a delta almost universal hash function;" it seems to me that this sentence needs a delta of "delta". Or should I ask in a separate question :P ? – Maarten Bodewes Jul 14 '16 at 16:42
• @MaartenBodewes: I would say that going down to that level is veering rather far from the OP's original question, and another (deeper) question would be advisable. In fact, I did say that :-) – poncho Jul 14 '16 at 17:06
• Quantum cryptography would also be left standing. – Demi May 4 '17 at 17:45

A simplified* Carter-Wegman MAC could be defined as:

$$t=\sum_{i=1}^n {k_1^i m_i} + k_2 \pmod p$$

$p$ is a sufficently large prime (e.g. 256 bits). You must choose a new truly random $k_2$ uniformly from $0\leq k_2 <p$. It acts as a one-time-pad that prevents an attacker who sees the tag $t$ from learning anything about $k_1$.

The polynomial $\sum {k_1^i m_i}$ has the property that for any fixed message $m$, the result will differ for most $k_1$, so an attacker who doesn't know $k_1$ will have only a very small chance of being able to predict the result, no matter how powerful their computer is.

Combined these properties mean that even a computationally unbounded attacker will have a negligible chance of producing a valid $(m,t)$ pair they haven't seen yet.

* This only serves to get an intuition for how polynomial MACs work. If you actually want to use this in practice, you need to take care of several details I did not cover here. Consider using well defined algorithms based on this concept like GHash/GCM or Poly1305.

• Notes (in case someone's actually going to implement this): $p$ needs to be prime; for $k_1$, it's important that the lowest coefficient is $i=1$ (that is, the message starts with $m_1$, not $m_0$); it's also important that $k_2$ take on each value in the range $[0, p)$ with equal probability; and even if all this is true, the forgery probability (for an $n$-word message) is bounded by $n/p$ (so it's not great for very long messages, unless you use a huge $p$). – poncho Jul 13 '16 at 18:15
• Also, there's no requirement that $k_2$ be different for each message; each $k_2$ value should be selected randomly and independently of any previous $k_2$ value. In fact, if you do insist on uniqueness, that would allow an attacker to eliminate some potential $k_1$ values (that is, those values that would imply a reuse of a $k_2$ value). – poncho Jul 13 '16 at 18:55
• @poncho I meant that as rolling a new $k_2$ for each message. For properly sized $p$ that will never result in a collision. – CodesInChaos Jul 13 '16 at 19:45
• Also, with the MAC as defined, you can create a forgery by simplying adding a 0 at the end; that is, increasing the message length to $n+1$, and making $m_{n+1} = 0$ (as that won't change the MAC value). You'd need to make sure that the msword is nonzero, or make $m_1$ be the message length (which is what GMAC does) – poncho Jul 13 '16 at 20:12