Is there a way to optimize a linear scan while preserving anonymity? I've been wrestling with a problem, and I was hoping if someone else had a bright idea.

Here's the problem: I have two sides, Alice and Bob.  Alice has a single high entropy string $A$, and Bob has a number of high entropy strings $B_i$, one of which may be $A$.  What we would like to do is have Alice send a single randomized message $F(A, r)$ to Bob so that:


Bob can determine in sublinear time which $B_i$ is equal to $A$ (or if none is)
Someone listening into two such exchanges (and who doesn't know either string) cannot determine if the two exchanges had the same string or not.


It's easy with only one of those constraints; it's easy to do if we let Bob take linear time (by having Alice send $r, Hash(A || r)$ to Bob, and have Bob compute each $Hash(B_i || r)$ value and look for a match.  And, it's easy to do if we don't care if someone listening in can check if two exchanges have the same string (just have Alice send $A$ in the clear).

I've tried to think of ways for Alice to include a hint that would allow Bob to skip over sections of his list; however every way I thought of would allow an attacker some advantage in determining whether two different exchanges had the same string.

And, in case you're wondering:


We can't assume that Alice and Bob had any preexisting shared secrets (other than the joint value of $A$ and some $B_i$).
We can't have Bob send a message to Alice first (which, again, would make it easy; Bob would send his public encryption key).  This limitation is because this exchange piggybacks on an existing protocol, and we can't add messages to that.


So, any bright ideas???
Your problem has a contradiction: since there is no agreement between two parties anything that Bob should learn about $A$ is also possible to learn for a third party. So, there should be a kind of trapdoor for Bob to be able to learn something about $A$ which is not possible to learn without knowing that trapdoor.

Your problem can be defined as a kind of secure set intersection protocol. One of the most significant works on the set intersection and the usage of it for pattern matching is done by Carmit Hazay and Yehuda Lindell.

However, in their work Alice is the one going to learn the result, not Bob. However you can use the idea of using a key as a trapdoor and by using an OT protocol have alice to learn $PRF(A,k)$ and send it to Bob whom is able to locally generate $PRF(B_i,k)$ and find the result.