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

4

1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times more expensive than 1.79 bits per key!

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

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