# Tagged Questions

For questions about hash functions: functions from a big set to a smaller one such that the same output $f(x_1)=f(x_2)$ for different input $x_1\ne x_2$ is unlikely, especially if $x_2$ differs from $x_1$ by a random error or is crafted by an adversary.

41 views

### Probability that an arbitrary element of a field has a specific structure.

This question is related to : http://crypto.stackexchange.com/questions/37351/encoding-an-element-in-r-rhr-way that I asked couple of weeks ago. The difference is that I did not take the collision ...
8 views

### How to prove pairwise independence of a family of hash functions?

I want to prove pairwise independence of a family of hash functions, but I don't know where to start. Given the family of hash functions: H with h(x) = a * x + b (mod M). ( Say h: U -> V, then: M ...
29 views

### Probability of collision of some family of hash functions

Given $x$ and $y$ in $\mathbb{R}$, and let $\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$ be a family of hash functions where $h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$ for some ...
9 views

### Need help in Hashing to create a fingerprint

Given a pattern P of length m and a text T of length n (n >= m), in which all characters ...
34 views

33 views

195 views

### Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
30 views

### How to calculate the expectation $E[\sigma(1)\sigma(2)\sigma(3)]$, given a 2-wise hash function $\sigma: [d] \rightarrow \{-1,+1\}$

Given a 2-wise hash function $\sigma: [d] \rightarrow \{-1,+1\}$, i.e., $\sigma(a)$ will map any positive integer $a\leq d$ into real number $-1$ or $+1$ with equal probability. Then how to calculate ...
69 views

### Cyclic Group permutations

I am working on the following exercise question: Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)). Gen : On input 1n , ...
32 views

20 views

### Find all groups that meets the condition

I have $n$ elements, each of them have two unsigned int attributes $x$ and $y$. Now I'd like to find out all the groups that fit the following condition: $A.x \geq B.y$ and $B.x \geq A.y$. The ...
54 views

### Exponentiation for hash function & associativity

Some cryptographic papers use $H^n(x)$ to mean $H(H^{n-1}(x))$ where $H^0(x) = x$ and $H$ is a cryptographic hash. So $H^3(x)$ would be $H(H(H(x)))$. Is this definition formally correct? It seems to ...
Suppose that $(m, r, s)$ is a message signed with an Elgamal signature scheme. Choose $h$ with $(h, p − 1) = 1$, and let $r_1 ≡ r^h\pmod p$, $s_1 ≡ sr_1h^{−1}r^{−1}\pmod {p − 1}$, and \$m_1 ≡ mr_1r^{−1}...