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?

  • $\begingroup$ Note that a nonce based Carter-Wegman MAC is no one-way function. $\endgroup$ Commented Jul 14, 2016 at 18:51

2 Answers 2


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.

  • $\begingroup$ "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 ? $\endgroup$
    – Maarten Bodewes
    Commented Jul 14, 2016 at 16:42
  • $\begingroup$ @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 :-) $\endgroup$
    – poncho
    Commented Jul 14, 2016 at 17:06
  • $\begingroup$ Quantum cryptography would also be left standing. $\endgroup$
    – Demi
    Commented May 4, 2017 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.

  • 5
    $\begingroup$ 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$). $\endgroup$
    – poncho
    Commented Jul 13, 2016 at 18:15
  • 1
    $\begingroup$ 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). $\endgroup$
    – poncho
    Commented Jul 13, 2016 at 18:55
  • $\begingroup$ @poncho I meant that as rolling a new $k_2$ for each message. For properly sized $p$ that will never result in a collision. $\endgroup$ Commented Jul 13, 2016 at 19:45
  • $\begingroup$ 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) $\endgroup$
    – poncho
    Commented Jul 13, 2016 at 20:12
  • $\begingroup$ @Doesitmatter: well, if we included a block of the message as the constant polynomial term, then someone could generate a forgery by (say) incrementing that block and decrementing the tag (incrementing and decrementing done within the field, for $GF(2^{128})$, that'd actually be flipping one of the bits). $\endgroup$
    – poncho
    Commented Oct 7, 2020 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.