Actually, come to think of it, this gives a brute-force attack a big optimization. They only have to test against the bloom filter now. There's no need to do the strong hash. So this has to be hashed using the strong hash.
OK, we have two options here:
1. Use strongH(password) to calculate bloom filter. Slow, but secure. Unfortunately, this can not be delegated. So perhaps a no-go.
2. Use sha(password) to calculate bloom filter. Fast, but reduces the password search space by up to eleven-ish bits (I think). I thought you were saying you were OK with this. However, I guess eleven-ish bits is a little high for me.
Alternate proposed solution:
filter = 0 # 32 bit integer
valid_passwords = [user_password, fake_password] # Can be any number of passwords. To preserve plausible deniability of all users, the spec should mandate a randomly generated fake password if the user doesn't want one
for password in valid_passwords:
hash = PBKDF2_HMAC_SHA512(password, "", 65536, 11)
for i in range(0,11):
filter |= 1 << (hash[i] & 0x1F) # Sets a random bit in the filter to 1
This still allows the attacker to reduce the search space by something like 2^11, but at the expense of doing 2^16 extra rounds of PBKDF2-HMAC-SHA512 per checked password.
Even the lowest-end device can handle this without delegation.