I have a hash function $HashSet(A) = H(a_1) *\cdots * H(a_n)$, where $A = \{a_1,\ldots,a_n\}$ and $H$ is a hash function which generates values of $b$ bits (and $H$ has no collision attack that requires less than $2^{b/2}$ of work for 50% chance of finding a collision).

Given $n$ how large should $b$ (the size of the output from $H$) be to resist attacks that create a collision by generating another $A$, assuming the attacker knows the initial $A$. I am assuming it is worse than $2^{b/2}$ for 50% of finding a collision and that for high $n$ there are slightly better attacks, but hopefully not enough to make it non-viable.

From what I have read the expected largest prime factor in any given $H(a_x)$ will be effectively $H(a_x)$, but I am worried that the algorithm will break down in some way due to the chance of really bad numbers (numbers with very low large prime factors), or due to something involving many non-prime numbers being multiplied.

EDIT: I made my assumption on the largest prime factor of $H(a_x)$ being effectively $H(a_x)$ based on this assumption:

The prime number theorem means the chance a number is prime is close to $\frac{1}{log(n)}$, so the expected size of the largest prime factor is at least $\frac{n}{log(n)}$. So for any given $b$ the expected bits in the prime number is $log_2(\frac{2^b}{log_2(b)}) = b - log_2(b)$. Which can be effectively considered to be $b$, as the difference between 1024 bits and 1014 ($1014 = 1024 - log_2(1024)$) is not significant to the security of the algorithm.

  • $\begingroup$ could you post where did you read? $\endgroup$ – kelalaka Nov 26 '18 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.