So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman, Mike Hearn, Bytecoin and others about reusable addresses.
There is a summary of the situation here
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03792.html and I had posed th question of whether it was possible to do better at all with Peter Todd:
Now while it would be clearly a very nice win if reusable addresses could be made SPV-like in network characteristics and privacy, but we dont have a plausible mechanism yet IMO. Close as we got was Greg's enhancement of my/your "bloom bait"/"prefix" concept to make multiple candidate baits to provide some ambiguity (still allows elimination, just slightly less of it).
If we can find some efficient crypto to solve that last one, we could even adopt them generally if it was efficient enough without needing interactive one-use address release
and Peter proposed also the related problem of proving something about that existence or not of a solution to that problem.
I think I have a proof-of-concept solution that proves by example we can do better in space efficiency, linkability defense and non-interactivity than my bloom bait, Peter Todds related prefix; and Greg Maxwell's extended bloom bait described
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03705.html.
So the idea is to use an IBE scheme as a building block in analogous way to my 1996 problem statement for NIFS and 1998 observation that a novel use for an IBE scheme can provide a generic solution to NIFS, and the arrival in 2001 of the first efficient / sensible trapdoor steepness (*) IBE with the introduction of the Weil Pairing problem by Dan Boneh and Matt Franklin described here
http://en.wikipedia.org/wiki/Boneh%E2%80%93Franklin_scheme.
Greg summarized IBE as follows on IRC:
(for those who may) not be familar with IBE stuff: The idea is that the user has a master private key, which results in a master public key. Anyone can take a prior block hash and combine it with the master public key to get a session pubkey which could be used to encrypt a chaincode included in an OP_RETURN. Using the master private key the user can derrive the session private key, which can then be used to recognize transactions using the same session key.
In IBE (identity based encryption) this is all used a bit differently: the master keys are held by a CA, and the session ID is your email address, and now anyone can make a public key for you— but you need the CA's help to get your private key)
Basically as Greg said your public key is your address (an email address, a block hash, whatever is convenient and unique) and from that and the master public key of the IBE server, the server can compute a private key corresponding to that. The master public is usually considered to be a system-wide domain parameter. Naturally enough because a side effect of this is that the IBE server can decrypt everyones email people were never too excited about the prospect.
However my 1998 NIFS observation is by acting as your own IBE server (each user creates their own master public server key) they can create a sequence (NIFS) or set (bitcoin reusable address) of public keys with interesting and publicly derivable properties!
It is my conclusion from 1996 that to solve this with DL directly at least in the NIFS case appears to be not possible.
So basically the reusable address becomes an IBE public key, the existing public derivation via DH or EC Elgamal/ECIES or whatever variant (bytecoins, mine, Peter Todd/Amir Taaki's) arrives at a factor that can be recovered. So with my variant (random sender generated multiplication factor encrypted with ECIES) you could encrypt the factor with a pub=IBE-extract(master pub, id=previous block hash) using the previous block hash as the "identity" and the users own self-owned IBE "server".
For Bytecoin & Peter Todd/Amir Taaki EC DH version using input or auxilliary addresses to save space its not even necessary to send the factor, its already sent. So then you send a separate message to do with secure delegatable filtering, a more secure/more space efficient bloom filter/prefix replacement, and this is a more flexible structure.
So the secure delegatable filter is you separately add an encrypted bloom bait Greg suggested (eg 1byte prefix communicated with public address.) And you can even combine that with Greg's extended bloom bait above to add anonymity set within the block.
Consequently you can now securely and very network/space efficiently securely delegate searching a block by computing the private key for the IBE pub key that any sender would use for that block, and sending it as a query to a random (or node-capture defended random selected node). The node can decrypt the encrypted bloom baits with it, but remains powerless to correlate with bloom baits to other payments received by the same user in bother blocks.
(In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block).
About weil pairing, and new hardness crypto risk, this is also the hardness assumption under some ZK-SNARKs as I think used in zerocash, and while ZK-SNARK introduces its own complexity/crypto system risk on top; in my view weil pairing is slightly lower assurance/review not so widely used relative to EC DL problem. Anyway the interesting thing to say about that is in the event this scheme got broken in the future it falls back to the scheme that is being proposed using prefix. Ie its no worse than that from linkability and likely would retain some cost even if broken-- asymmetric crypto breaks are usually somewhat gradual.
This looks more expensive and non-indexable though I didnt look to see if there is any ciphertext only or batch precomputation that could be squeezed out of it.
Obviously its more CPU intensive and some eg fee mechanism to prevent node DoS could be nice, but it seems to demonstrate a proof by existence that it is possible to do better.
Finally I think it maybe within possibility to do further than this because it is not technically necessary to delegate decryption, only to delegate filtering, which can be a simpler requirement.
Adam
(*) There was an earlier scheme by Maurer et al if I recall, but to get a 1024-bit security margin you had to perform a discrete log attack on a 512-bit prime, so the key generation cost was immense, hence "sensible trapdoor steepness" thats very shallow in tems of work difference between setup cost and crypto system strength.
