Skip to main content

Questions tagged [universal-hash]

In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property.

Filter by
Sorted by
Tagged with
1 vote
0 answers
39 views

Expected size of a set hashed to a specific value

In Theorem D.5 of Goldreich's Computational Complexity: A Conceptual Perspective, Goldreich states: Let $m \leq n$ be integers, $H_n^m$ be a family of pairwise independent hash functions, and $S \...
Germ's user avatar
  • 133
1 vote
0 answers
26 views

Proof of UOWHF construction from a strongly universal hash family

I am currently trying to rigorously prove Lemma 2.2 of [NY]. More specifically, a UOWHF family can be constructed from a composition of a strongly universal family $G_k = \{g : \{0, 1\}^k \rightarrow \...
Pontakorn Prasertsuk's user avatar
2 votes
2 answers
106 views

What does the leftover hash lemma guarantee for a specific hash function?

Suppose I sample a matrix $h$ from $\mathbb{Z}_2^{l \times n}$ where each entry in $h$ is $1$ with probability 1/2. Suppose I also have a set $S\subset \{0,1\}^n$, and I define a random variable $X$ ...
Germ's user avatar
  • 133
3 votes
1 answer
809 views

What is the advantage of using hash function families instead of a single hash function?

My guess would be that families are more secure. In which way though? I have seen claims that hash function families can be collision resistant while single hash functions can not be. Is this true? ...
Wouter's user avatar
  • 31
0 votes
1 answer
55 views

Is a PRF pairwise independently and uniformly distributed

The notation of a strongly universal function was introduced by Wegman and Carter here and it states, that such a function has to be pairwise independently and uniformly distributed. I would like to ...
Titanlord's user avatar
  • 2,307
0 votes
0 answers
141 views

Do "superfast" keyed hash functions exist?

A common family of requirements for (cryptographic) keyed hash functions is that the function $h(k,-)$ should have good collision resistance for all keys $k$, even if the key $k$ is known to the ...
SocraticMathTutor's user avatar
5 votes
1 answer
150 views

The rigorous proof in the commitment based on CRHF

I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous ...
constantine's user avatar
3 votes
1 answer
217 views

UOWHF vs CRHF / Relevance of UOWHF

What's the difference between UOWHF and CRHF and why are UOWHF useful? As far as I understand, Universal One-Way Hash Functions are an alternative to CRHF. While for CRHF it is hard, given randomly ...
sbluff's user avatar
  • 113
2 votes
1 answer
297 views

Create a control hash string from different sources, is there a difference, advantage or disadvantage in comparison when using this ways?

I wanna create from several inputs/sources should be formed into one hash value for controlling of different thinks later. Example: String + File String + String File + File String + File + String ...
Z0OM's user avatar
  • 155
2 votes
2 answers
195 views

Why do we need the leftover hash lemma for this hybrid proof (Learning with Errors)?

I've been reading about Learning with Errors here. On p. 7 there's a proof for the security of the PKE scheme, that goes through the leftover hash lemma, in order to prove that: $$ (pk, Enc(0))\equiv (...
Anon's user avatar
  • 403
1 vote
0 answers
88 views

Is the following statistically close to uniform? (and how does one prove such claims in general)

For every $a \in \{0,1\}^n$ define: $$h_a : \{0,1\}^n\to \{0,1\}$$ $$ h_a(b)=\langle a,b \rangle$$ So $\{h_a\}_{a \in \{0,1\}^n}$ is known to be a universal hash function family. This means that if we ...
Anon's user avatar
  • 403
4 votes
2 answers
532 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
0 votes
0 answers
35 views

How Davies–Meyer does work? [duplicate]

I am here so if I asked something wrong or in the wrong way please let me know. How to hash compression large data into the fixed size of the string. Edit: How Davies–Meyer does work? Take the example ...
Rohit Nishad's user avatar
3 votes
1 answer
513 views

Why do universal hash functions prevent adversarys, but uniform hash functions don't?

Before I state my actual question, let me first five some terminology so we are all on the same page: Let $U=\{k_1,...,k_u\}$ the universe of possible keys, $|U|=u$. We use a hash table $T$ with $m$ ...
Prof.Chaos's user avatar
2 votes
1 answer
75 views

On randomness related terminology clarification

It was suggested to provide a new question in the comments in How to combine $n$ 'less random' bits to generate one 'more random' bit?. Why there is no unbiased randomness (seeking ...
Turbo's user avatar
  • 930
1 vote
0 answers
101 views

Exercise applying Leftover hash Lemma

Say that X is a (k; n)-source if $X\in\{0,1\}^2$, and the min-entropy of X is at least k. Answer the following questions: (i) Suppose that $l=128$; what is the minimal amount of min-entropy needed in ...
Fede's user avatar
  • 11
1 vote
0 answers
60 views

What is the appropriate choice of hash family to make XOR homomorphism unlikely?

Let's say $N \subseteq [n]$ is not empty. Is there a type of hash family $H = \{h : [n] \rightarrow \{0 , 1\}^k\}$, where $k = \theta(\log(n))$, to ensure that the following holds when $|N| > 1$? $$...
Johnny's user avatar
  • 111
4 votes
2 answers
792 views

What are the differences between a UHF (as used in cryptography) and a cryptographic hash function?

After reading about UHFs from different sources (From Algorithm books to Crypto books), I am still thoroughly confused about them. How is a UHF different from other cryptographically secure hashing ...
user93353's user avatar
  • 2,245
0 votes
0 answers
310 views

Family of hash functions which are epsilon-almost universal

Let $R, S,$ and $T$ be finite, non-empty sets. Suppose that for each $r \in R,$ we have a function $h_r: S \rightarrow T.$ In other words $\{h_r\}_{r \in R}$ is a family of keyed hash functions from $...
Sayantan's user avatar
6 votes
1 answer
616 views

How does GHASH used in GCM behave as a universal hashing function?

As per my understanding, a Universal Hash Function isn't a cryptographic hash function & it's output isn't uniformly distributed. However, this is still secure because it's actually a family of ...
user93353's user avatar
  • 2,245
2 votes
1 answer
120 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,245
4 votes
1 answer
105 views

Why does the hashfamily of all functions with $\{h \in H_0 | h:U \rightarrow V\}$ satisfy universal hashing?

I read in our university lecture on hashing that it would be good (even though it is way to space intensive) if we could take the set of all function from $U \rightarrow V$ to satisfy the following ...
OuttaSpaceTime's user avatar
5 votes
1 answer
144 views

How does the probabilty for universal hashing work out?

Hey for universal hashing we say the following: Definition: A randomized algorithm $H$ for constructing hash functions $h\colon U \to \{1,\ldots,M\}$ is universal if for all $x \neq y$ in $U$, we have ...
OuttaSpaceTime's user avatar
2 votes
0 answers
190 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
0 answers
72 views

Low weight linear $\varepsilon$-universal hash function

According to the definition, an $\varepsilon$-universal linear hash function family, given a field $\mathbb{F}$, is a set of linear transformations $\mathcal{H} \subseteq \mathbb{F}^{m,n}$ such that ...
JayTuma's user avatar
  • 71
6 votes
2 answers
571 views

How does this POLYVAL modular reduction algorithm work?

I recently found the GitHub repository used to make the measurements in the AES-GCM-SIV paper where they implement polynomial hashing using POLYVAL. This means in this context to compute the usual $\...
SEJPM's user avatar
  • 46.1k
0 votes
1 answer
245 views

What are the random variables in Universal Hash Function?

Universal hash function is defined as follow: $f_{(k_0,k_1)}(x) = (k_0\cdot x + k_1) \mod p$, where $p$ is prime In Wikipedia, it is mentioned that the above function is pairwise independent. ...
Reza's user avatar
  • 75
3 votes
2 answers
2k views

Difference between strongly universal and $\delta$ univeral hash functions

Define a family of strongly universal hash functions as: $$\forall x_1, x_2 \in \{0,1\}^n, \forall y_1, y_2 \in \{0,1\}^m, ~ x_1\ne x_2: ~~ \Pr_{h\in H} [h(x_1) = y_1 ~\text{and}~ h(x_2) = y_2] \le \...
csstundent's user avatar
6 votes
2 answers
1k 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 \...
Martin Kromm's user avatar
2 votes
3 answers
8k 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 ...
JGoodwin10's user avatar
1 vote
0 answers
57 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\...
Sabarna Hazra's user avatar
1 vote
1 answer
395 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
4 votes
1 answer
106 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}:\...
Idra's user avatar
  • 91
1 vote
0 answers
160 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 ...
ayman ayman's user avatar
1 vote
1 answer
81 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$ ...
DEBASMITA DEY's user avatar
1 vote
1 answer
131 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 ...
Daniel's user avatar
  • 457
1 vote
1 answer
362 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 ...
Digimon Kaiser's user avatar
6 votes
2 answers
1k 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 ...
Daniel's user avatar
  • 457
0 votes
1 answer
1k 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 ...
LyingOnTheSky's user avatar
1 vote
1 answer
5k 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 ...
Aymn Alaney's user avatar
12 votes
1 answer
15k 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 ...
Melab's user avatar
  • 3,655
0 votes
2 answers
3k views

Toy Tetragraph hash

Im trying to understand how TTH works, but have a question. Let's take this example: ABCDEFGHIJKLMNOP We have ...
Goldy's user avatar
  • 9
2 votes
1 answer
881 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 ...
Jal's user avatar
  • 123
1 vote
1 answer
185 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/...
Jay's user avatar
  • 195
4 votes
2 answers
333 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 ...
SEJPM's user avatar
  • 46.1k
2 votes
1 answer
598 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} = (...
Demi's user avatar
  • 4,793
1 vote
0 answers
341 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 ...
Demi's user avatar
  • 4,793
3 votes
1 answer
328 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 ...
Demi's user avatar
  • 4,793
3 votes
1 answer
667 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 ...
A.Solei's user avatar
  • 405
2 votes
1 answer
263 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 ...
dylan7's user avatar
  • 551