Cryptography Stack Exchange
Cryptography Stack Exchange

Questions tagged [carter-wegman]

Carter-Wegman MACs build a provably secure MAC from a universal hash

Carter-Wegman MACs build a provably secure MAC from a . With a one-time key they are the authentication equivalent of a one-time pad. They are often used with a PRF or PRP instead to allow key-reuse. In this case their security can be reduced to that of the underlying primitive and a small term.

Wegman, Mark N., and J. Lawrence Carter. "New hash functions and their use in authentication and set equality." Journal of computer and system sciences 22.3 (1981): 265-279.

Examples of Carter-Wegman style MACs:

15 questions
11
votes
3 answers

Is Poly1305 an information-theoretically secure MAC?

I have heard some people say that the Poly1305 authenticator is a "nuclear" MAC i.e. it is information-theoretically secure. After reading the paper I see it is based on the Wegman-Carter MAC which is supposedly the natural authentication pairing…
lightspeeder
  • 368
  • 1
  • 9
11
votes
2 answers

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…
David Schumann
  • 243
  • 3
  • 9
10
votes
1 answer

Regular MACs vs Carter-Wegman MAC

Carter-Wegman MAC variants (VMAC, UMAC etc) are known to be very fast and efficient when compared to MAC algorithms that are based on block ciphers and compression functions (like HMAC, CMAC etc). However, Carter-Wegman MAC variants are not very…
BlaX
  • 726
  • 6
  • 17
8
votes
1 answer

Security of Carter-Wegman polynomial authenticators, and their concatenation?

Carter-Wegman polynomial authenticators For a given finite field $(\mathbb F,+,\times)$ of $f$ elements, define a Carter-Wegman polynomial authenticator for a message $M=m_1\|m_2\|\dots\|m_l$ of $l$ symbols in $\mathbb F$ as…
fgrieu
  • 131,696
  • 12
  • 284
  • 553
6
votes
2 answers

Is there another resource for Carter-Wegman-style message authentication?

I'm wondering if there are other resources that cover Carter-Wegman style message authentication, besides the sources themselves. Is there an online text or a book that covers their ideas? I'd prefer something that's very thorough, and less…
Matt Groff
  • 163
  • 4
6
votes
1 answer

Do Carter–Wegman MACs allow key reuse if the MAC tag is kept secret?

Poly1305 (and GHASH) are secure authenticators, but only for one use. Thus, nonce reuse in Poly1305-AES, ChaCha20-Poly1305, and AES-GCM all reveal the authentication key. However, my understanding is that this is because (in Poly1305-AES,…
Demi
  • 4,753
  • 1
  • 18
  • 38
5
votes
0 answers

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…
fgrieu
  • 131,696
  • 12
  • 284
  • 553
3
votes
1 answer

Does authenticating fake Carter Wegman protected OTP messages consume key material at the receiving node?

Assume a message protocol whereby one time pad messages are authenticated with a Carter Wegman type hash on the ciphertext, or some similar construct utilizing a unique authentication key per message. Since this is a OTP system, there is a store of…
Paul Uszak
  • 14,496
  • 2
  • 23
  • 69
3
votes
1 answer

Proof that the Family of Toeplitz Matrices is XOR-Universal

Definition of XOR-Universal hash functions by Abidin[1]: A class $H$ of hash functions from $M$ to $T$ is XOR-Universal$_2$ ($XU_2$) if there exist at most $|H|/|T|$ hash functions $h$ $\in$ $H$ such that $(h(m_1) = h(m_2$) $\oplus t)$ for any two…
Hernichtocles
  • 33
  • 4
2
votes
1 answer

Corelating between the concept of Universal Hashing wrt Algorithms (hash-table use) & the use of Universal Hashing in a one-time MAC

Trying to understand the concept of a Universal Hashing function. From Introduction of Algorithms by Cormen, Rivest et al We now define the hash function $h_ab$ for any $a \in Z^*_p$ and any $b \in Z_p$ using a linear transformation followed by…
user93353
  • 2,197
  • 2
  • 21
  • 37
2
votes
0 answers

How to look for implementations of universal hashing?

Being a physicist, I know very little about cryptography. In fact, the main two practical aspects I've learned so far are: Unless you're an expert, 1. Don't try to invent new cryptosystems and 2. Don't implement cryptographic algorithms yourself if…
Adomas Baliuka
  • 121
  • 2
2
votes
1 answer

Parallel variant of Carter-Wegman MAC with incremental property

Is there any variant of the Carter-Wegman MAC algorithm that is fast, parallel and has the property of incremental crypto?
BlaX
  • 726
  • 6
  • 17
1
vote
1 answer

Why does Carter-Wegman (and AES-GCM) use different keys for PRF and keyed-hash

So. As I understand, Carter-Wegman transforms a one-time MAC (which must be a difference unpredictable function (DUF)) by encrypting it with a PRF. The DUF and the PRF use two different keys, which can be understandable if: you're just being…
David 天宇 Wong
  • 1,505
  • 11
  • 24
1
vote
1 answer

Why does Carter-Wegman MAC have 2n-bit output?

The Coursera course on Cryptography 1 has a section about Carter-Wegman MAC. Here is the image of slide: Now my question is both $F$ and $S$ output $n$-bit strings. We XOR two $n$-bit strings and we should get an $n$-bit string as a result. But the…
Majid Azimi
  • 133
  • 4
1
vote
2 answers

Is this a better GCM?

Using the keystream from the block cipher for both parts of the GMAC key (initialization and encrypting the auth tag) seems to produce a better mode of operation than GCM, as successful forgeries and nonce reuse only compromise the particular (key,…
Demi
  • 4,753
  • 1
  • 18
  • 38