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?
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.