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???