Given a public address and an xpub master public key from a deterministic wallet, is it possible to verify whether that address is (or isn't) a member of the wallet?
For example, if my address is 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2 and my xpub is xpub6CUGRUonZSQ4TWtTMmzXdrXDtypWKiK, how long would it take to verify that the address is not generated by the wallet? Can it be checked in constant time, or brute-forced in a reasonable amount of time?
Given a public address and an xpub master public key from a deterministic wallet, is it possible to verify whether that address is (or isn't) a member of the wallet?
Yes (and no)
how long would it take to verify that the address is not generated by the wallet?
I guess it would take the same time to verify if an address is generated by the wallet as the time taken for generating it (at least as order of magnitude), on the other hand you should not be able to verify if the addess is NOT generated by that deterministic wallet, because there are infinitely many addresses you can generate, so you would have to check an infinite amount of addresses.