Questions tagged [universal-hash]

Question 1

It seems to me that all that exists for universal hash functions used in Carter–Wegman MACs is finite field multiplication. Are there any others?

Question 2

For any positive integer $k$, let $\boxplus_k$ be addition on $k$-bit unsigned integers and $\boxminus_k$ be subtraction on $k$-bit unsigned integers. Let $\operatorname{NH}_w((X,Y),(a,b)) = (a \...

Question 3

Consider a function $h:\mathcal{K} \times X^n \to X^n$. The function $h$ is called $(\epsilon_1, \epsilon_2)$-block-wise almost uniform (BAU), if for all $(\mathbf{x},i)\ne(\mathbf{x}',i')$ the ...

Question 4

Background In theory, hash functions produce a binary number having bounded (often fixed) length from binary data of arbitrary length. In practice, specifications and implementations constrain the ...

Question 5

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 \...

Question 6

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 \...

Question 7

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$ ...

Question 8

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? ...

Question 9

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 ...

Question 10

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 ...

Question 11

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 ...

Question 12

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 ...

Question 13

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 ...

Question 14

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 (...

Question 15

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 ...

Stack Exchange Network

Questions tagged [universal-hash]

Universal hash functions besides finite field multiplication

Is the NH hash family (from UMAC) AXU?

Block-wise universal functions and their properties

Which hash algorithms support binary input of arbitrary bit length?

Expected size of a set hashed to a specific value

Proof of UOWHF construction from a strongly universal hash family

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

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

Is a PRF pairwise independently and uniformly distributed

Do "superfast" keyed hash functions exist?

The rigorous proof in the commitment based on CRHF

UOWHF vs CRHF / Relevance of UOWHF

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

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

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

Hot Network Questions