Bi and B2 Belong to Different Users

Recall that each Bloom filter is initialized with a random seed chosen uniformly at random from {0, l}64. Therefore, if Bi and B2 pertain to different users, then it is highly likely that they are initialized with different random seeds. This means that the false positives generated by each filter are highly likely to correspond to different addresses. Moreover, since different users will have different Bitcoin addresses, Bi and B2 will contain different elements. Therefore, Bi П B2 is likely to comprise only few addresses, if any. Notably, when Bi and B2 pertain to different users, then

B nB2 can be computed as follows:

where N1 corresponds to the number of elements inserted in B1. E [Bi n B2] is the expected number of elements that match B2 and B1. The number of elements in B that match B2 is given by Pf (m2)B. Then, E[B1 n B2] can be computed by assuming a binomial distribution with success probability Pf (m2) and with Pf (m2)B number of trials.

Note that the adversary can compute m1 (using (6.4)); if m1 > B1 n B2, then this offers a clear distinguisher for the adversary that the two acquired Bloom filters B1 and B2 pertain to different user wallets.

< Prev   CONTENTS   Source   Next >