Questions tagged [carter-wegman]

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

Filter by
Sorted by
Tagged with
6 votes
2 answers
478 views

Message Authentication Code Padding Overview

I am confused about padding when using a Message Authentication Code (MAC). This paper suggests using a different key if the message is padded, and otherwise not, which really confused me. An example ...
Titanlord's user avatar
  • 2,234
3 votes
1 answer
156 views

Carter-Wegman MAC different notations

While studying Carter-Wegman message authentication codes MAC, I got two different notations for the broader concept and have problems with understanding the difference, if any exist. Let $K, K_1, K_2$...
Titanlord's user avatar
  • 2,234
1 vote
1 answer
52 views

Unconditionally Secure Signature Key Generation

I'm reading through a paper called Unconditionally Secure Signatures (https://eprint.iacr.org/2016/739) and to generate keys, the authors select $\epsilon-ASU_2$ functions, such that: For any $m \in ...
Lev Knoblock's user avatar
3 votes
1 answer
158 views

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. ...
Paul Uszak's user avatar
  • 15.3k
4 votes
2 answers
447 views

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 ...
Hernichtocles's user avatar
2 votes
1 answer
112 views

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 ...
user93353's user avatar
  • 2,181
2 votes
0 answers
166 views

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'...
Adomas Baliuka's user avatar
1 vote
1 answer
380 views

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 ...
David 天宇 Wong's user avatar
8 votes
1 answer
592 views

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$ ...
fgrieu's user avatar
  • 140k
11 votes
3 answers
2k views

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 ...
lightspeeder's user avatar
11 votes
2 answers
3k views

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. ...
David Schumann's user avatar
1 vote
1 answer
184 views

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 ...
Majid Azimi's user avatar
1 vote
2 answers
156 views

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 ...
Demi's user avatar
  • 4,793
6 votes
1 answer
497 views

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 ...
Demi's user avatar
  • 4,793
5 votes
0 answers
190 views

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 ...
fgrieu's user avatar
  • 140k
11 votes
1 answer
3k views

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). ...
BlaX's user avatar
  • 736
2 votes
1 answer
168 views

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's user avatar
  • 736
6 votes
2 answers
1k views

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 ...
Matt Groff's user avatar