Most space-efficient lossy dictionary?
Let's see what we can do. Values are random and hence are incompressible, but keys can be sorted and then diffed. So, just sort the data, employ difference compression schema for keys and use binary search to find.

It will put your N keys+values into minimum amount of bits required to keep this amount of information.

May be, you can further improve compression ratio by dropping less compressible items.

EDIT: As mentioned here, you can compress keys to smaller values. So, f.e. you can use Bloom filter to check that probed key is included in the result set, and then use compressed 32-bit hash of the key to find it in table with 64K entries with pretty high fidelity. NOTE: at more thorough analysis I realized that Bloom filter will occupy at least the same space you will economy on reducing key values stored in the sorted table.

PS: You can use any rehashing scheme, including Cuckoo hashing, to cut off rehash chains at some point, but anyway sorted sequence should be better compressible than any hashtable containing unused cells.

Perfect hashing just helps you to make hashtable without holes. I don't know what signature you mean here.

Bloom filter by itself only checks value presence, then you still need to store entire key+value pair.