from public hashes partition into 1024 subsets; create bloom filter for each, and add the subset to the bloom filter as hash(public hash concatenated with its index)
verify(signature,message) = find the expected signature for m; for each private hash in signature, get public hash by hash(private hash), and check in corresponding bloom filter for positive; if all respond positive, return true, else return false