Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking

Shlomi Dolev

Consider graphs of n nodes, and use a Bloom filter of length 2 log3 n bits. An edge between nodes i and j, with i < j, turns on a certain bit of the Bloom filter according to a has…