What I can think of is that, there are two directions to optimise the verification overhead of stealth address: 1) optimising the verification overhead of each tx, 2) reducing the number of txs to verify by filtering.
For 1), the optimisation space is very small, as scalar multiplication on an elliptic curve seems to be the cheapest trapdoor function already. For 2), there seems to be a trade-off between privacy and verification overhead.
Let me informally prove this statement below. I cannot guarantee it’s fully correct, and I’m happy to be proven wrong.
We shatr from proving the necessity of the randomness r for constructing stealth address.
Lemma 1: To receive money without revealing the receiver’s address, 1) the sender should always use a secret r and send r to the receiver privately, and 2) the receiver should always scan all txs on the blockchain to find txs going to himself.
Proof: Without the first condition, each stealth address can be mapped to a real address deterministically, which leaks the real address.The second condition is always necessary regardless of the stealth address. Consider payments without stealth address, the receiver should still compare his address with addresses in txs on the blockchain.
Then, we identify the security foundation of the stealth address, namely the CDH.
Lemma 2: To break the privacy guarantee of stealth address, one should break Computational Diffie-Hellman.
Proof: Easy from the security proof of the stealth address, i.e., prG = pR = Pr.
CDH relies on a trapdoor function. So far the most practical trapdoor function seems to be the elliptic curve scalar multiplication already. I don’t know any trapdoor function that is more lightweight than this. If there exists one, replacing EC scalar multiplication with this trapdoor can speedup verification directly.
Then, we consider the second possibility: filtering txs so that the receiver only needs to perform trapdoor functions on a subset of txs rather than all txs.
Here is a simple solution. In a nutshell, each tx attaches a short prefix of the receiver’s PK, and the receiver only needs to run trapdoor functions over txs with his PK’s prefix.
Each tx attaches an extra byte b equal to the first byte of the receiver’s PK. Upon a tx, the receiver checks whether his PK’s first byte equals to this tx’s b. If no, then this tx is not for the receiver. If yes, the receiver further computes the trapdoor function to see whether this tx is really for himself.
This allows the receiver to run trapdoor functions on \frac{1}{16} of all txs only.
However, the privacy downgrades for 16 times in the meantime, as the search space narrows down for 16 times.
It’s easy to see that, given a fixed trapdoor function, there is a trade-off between privacy and verification overhead.
Less verification overhead -> fewer txs to verify using trapdoor function -> fewer txs to search for identifying the receiver.