# Tag Info

4

For the first question, about the last line, it surely depends on the hash function. For example, suppose each line is a single bit (0 or 1). If the hash function is the xor of the bits, then the answer is yes -- take 240 lines with total parity 0. But the answer is no if the hash function is defined by $$f(x_1, x_2, \ldots, c_n) = \neg (x_n \oplus f(x_1, \... 3 Cryptographic hashes I don't think anything is known unconditionally. We can analyze this question using a random oracle assumption. MD5, SHA1, SHA256, etc., have a Merkle-Damgaard structure: they split the input x up into blocks x_1,\dots,x_n, then compute$$h_i = F(x_i,h_{i-1}) where $h_0$ is a constant and $h_n$ is used as the output of the hash ...

2

As much as you're being downvoted and attacked, you've nearly reinvented bcrypt. Let's say we have encryption algorithm (doesn't matter which one): blowfish Then generate random sequence of chars consisting predefined array (for instance just random sequence of digits) A sequence of 24 characters; an even multiple of the 8-byte blocksize of blowfish: ...

2

Yes. The simplest way to understand this is to understand the zero-knowledge proof that you know a 3-coloring of a graph. 3-coloring is NP-complete, so an arbitrary hash function $h$ and target value $w$ can be represented as a graph where knowing a 3-coloring for that graph is equivalent to knowing a $v$ such that $h(v) = w$. That isn't the most efficient ...

1

It depends what you mean by "arbitrary cryptographic hash function". If you care about practical cryptography, I think the most natural interpretation is to model $H$ as a random oracle (i.e., the random oracle model for hash functions). In this setting, the problem is hard. As a lower bound, it requires exponential running time. To prove this, let \$u=(1,...

1

Today you should probably use Tabulation hashing for Linear Probing. In The Power of Simple Tabulation Hashing by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well. Tabulation hashing is also a lot faster than even ...

Only top voted, non community-wiki answers of a minimum length are eligible