Questions tagged [universal-hash]

The tag has no usage guidance.

4
votes
2answers
309 views

Universal hash functions with homomorphic XOR property

Let $H = \{h_r : U \rightarrow [m]\}$. What are the currently known most efficient algorithms such that $H$ is a universal family and fulfils the homomorphic XOR operation property $\forall h \in H \...
0
votes
0answers
68 views

19 out of 24 words of BIP39 passphrase (brute-force last 5?)

I have managed to lose 5 words of my 24 word Ledger Nano S recovery phrase. I have words 1-19 but I am missing words 20-24. I have significant holdings on the wallet so would very much like to recover ...
1
vote
0answers
31 views

How to prove security of scheme constructed by Hash then PRP

Suppose there is a scheme where a message is first hashed and then sent to a PRP. If the hash is done using an $\epsilon$-bounded universal hash function and the PRP $K\times \{0,1\}^n\rightarrow\{0,1\...
1
vote
1answer
99 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 ...
4
votes
1answer
83 views

Difficulty of forging MACs based on linear functions over $GF\left(2^n\right)$

This is a homework question, therefore I'm not expecting full solutions, just general guidance. I want to build a one-time MAC using universal hashing. I defined my hash functions as: $h_{a,b}:\...
1
vote
0answers
90 views

How does Skype hash the phone number to a fixed length? [closed]

I have a Skype account with a phone number and I noticed that my contacts and I who created the accounts with a phone number have the Skype ID in some form of a hash. But all the Skype IDs have the ...
1
vote
1answer
58 views

Meaning of $\operatorname{UOWH}(k; u_1, u_2)$

I do not understand the format used in Shoup's "Using Hash Functions as a Hedge against Chosen Ciphertext Attack (page 8 of the PDF) for universal one way hash functions (UOWH). What are $k$, $u_1$ ...
1
vote
1answer
32 views

if a hash is difference-unpredictable, will it keep unpredictable given an offset?

Let $H(k,m)$ an universal hash function that is difference-unpredictable. Let $\mathcal{A}$ be an attacker who sends tuples $(m_0, m_1, \delta)$, and $\mathcal{A}$ wins the game if one of the tuples ...
0
votes
1answer
124 views

Combining two almost universal hash functions

We say that a set of functions $S$ is $\epsilon$-almost-universal if for any function $f \in S$, it holds that $\Pr[f(m) = f(m')] < \epsilon$ for $m \not = m'$. Assume that we have the following ...
6
votes
2answers
322 views

Proof that MAC and hash composition is insecure

Let $F$ be a secure PRF and $H$ a universal hash function. How can I exhibit a pair $(F,H)$ whose composition $$S'((k_1, k_2), m) = F(k_2, H(k_1,m))$$ is an insecure MAC (or an insecure PRF, since a ...
0
votes
1answer
148 views

What is a fast good-uniformity hash function that if it's seed and it's hash values are unknown, can be strong as cryptographic hash functions?

The hash function is for an application that the input to the hash function is from a user's, hence the user can control the collisions, but the question is that if the collisions, the hash function's ...
0
votes
1answer
825 views

Which algorithm has better performance (HMAC, UMAC, and Poly1305)?

I want to implement a protocol which requires Integrity and Authentication for its messages. I found a lot of algorithms such as HMAC, UMAC, and Poly1305 which provide Integrity and Authentication. So ...
3
votes
1answer
3k views

What is a universal hash function?

Short and to the point. I'm assuming that it is not a kind of hash function that can be used universally. After having read about universal hash functions used with the one-time pad to form an ...
1
vote
1answer
703 views

Toy Tetragraph hash

Im trying to understand how TTH works, but have a question. Let's take this example: ABCDEFGHIJKLMNOP We have ...
2
votes
1answer
385 views

Why is double hashing universal hash function still a universal hash function?

Here is the definition of universal hash function for $h \in H$ (family of universal hash function) $$\forall x, y \in U x \neq y : Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{m}$$ Double hashing is the ...
0
votes
1answer
85 views

Generating two secret keys from a physical analog signal: Crypto HASH analogous to time varying signal

Can we generate two secret keys from same source? The idea is we have time varying signal. We capture a window of say few milliseconds,$t$. I can chop values of signals at a rate $N_S$ and get $tN_S/...
3
votes
2answers
197 views

Can universal hashing functions be (ab)used as stream ciphers?

These days, universal hashing functions like GHASH and Poly1305 are very trendy because of their simplicity and speed. Now during a discussion related to export restrictions, it came up that mainly ...
2
votes
1answer
293 views

Is this hash function almost XOR universal?

Consider this hash function: The key $K$ is $2^n$ bits. The message $M$ is divided into $2^n$ bit blocks. Arithmetic is performed modulo $2^{n+1}$. The hash is defined by: $ H_0 = 1 $. $H_{i+1} = (...
0
votes
0answers
89 views

Hash function with good performance on extremely short messages

Are there randomized almost universal hashes that are fast for extremely short messages (usually <10 bytes)? Edit: This is for hash tables, so it only needs to be hard enough to break to make the ...
2
votes
1answer
125 views

Can an attacker recover the key if a Poly1305 collision is known?

Suppose that messages $m_1$ and $m_2 \neq m_1$, both known to the attacker, are both MAC'd through Poly1305 with the same key. By chance, these two messages hash to the same value. The attacker ...
2
votes
1answer
273 views

PRF and pairwise independent hash function

I'm confused with the concepts of pairwise independent hash function and pseudorandom function. They seem identical to me. A family of hash functions $H=\{ h:U \to [m] \}$ is $k$-independent if for ...
2
votes
1answer
179 views

Unconditional authentication

I have a few questions regarding universal-hash functions: Is there a way universal hash functions can be used to provide unconditional authentication in the way the OTP provides unconditional ...
1
vote
1answer
106 views

Why does UMAC encrypt the output of universal hash function?

UMAC uses a key to choose a random hash function from a family of universal hash functions. The value of the hash function is always encrypted using yet another key, and the resulting ciphertext ...
9
votes
1answer
377 views

Secure content-defined chunking

Intro For deduplication purposes, I need to split a stream of plaintext bytes into variable-sized chunks. The way this is traditionally done is using a rolling hash function defined over some window $...
2
votes
1answer
258 views

Hash functions to the power of two and three notation

I have found in a Wireless Sensor Networks security paper, operations where cryptographic hash functions are elevated to the power of 2 and to the power of 3 (i.e. $h^2(x)$ and $h^3(x)$). This might ...
1
vote
1answer
188 views

On the privacy of perfect hash functions

I'm digging into the several algorithms for building (Minimal) Perfect Hash Functions. It seems that the recent works provide quite a few very efficient algorithms. However, I'm wondering how a (M)...
3
votes
1answer
1k views

Universal hashing techniques based on matrix multiplication

The article here says below, about a universal hashing technique based on matrix multiplications. "However, there is a little known method based on using a random matrix. It has lots of advantages - ...
1
vote
0answers
156 views

Is this a correct understanding of Universal Hash Functions?

I'm studying universal hash functions and have been reading several papers but now i'm focusing on Wegman and Carters original paper from 1979 (Universal classes of hash functions) and the H1 class. ...
1
vote
1answer
149 views

Asymptotic Hash Function and Concrete Hash Function

I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical, and they say that its formalization is non-asymptotic. Why is the formalization non-asymptotic? What is an example of hash ...
3
votes
0answers
215 views

Precise meaning of various terms related to universal hash functions [closed]

I've been reading about universal hashing, but I'm confused by all these different terms and notations. Could someone help me understand the precise meaning or relation between the following terms: ...