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

• I guess we can't simply assume Bob to have pre-distributed some trusted public key? / Are we restricted to only one message from Alice -> Bob or may Bob also respond later? – SEJPM Oct 28 '15 at 21:35
• ... If you have high entropy strings, wouldn't it be possible to deterministically hash a substring of those and include this? An attacker wouln't still be able to identify the same string (as the non-included part would still have enough entropy?) if you follow your $r||H(A_1||A_2||r)||H(A_1)$ and it would give you some speed-up although no superlinear as you could pre-hash the strings and identify those with the same start. – SEJPM Oct 28 '15 at 21:47
• @SEJPM:including $H(A_1)$ would allow an attacker to deduce under some circumstances that two different exchanges used different values of $A$, if $H(A_1) \ne H(A'_1)$, he could conclude that $A \ne A'$ – poncho Oct 28 '15 at 22:33
• @SEJPM: actually, within the existing protocol, Bob does respond. However, I don't immediately see how that helps, as Bob will need to know which $B_i$ is the correct value, and Bob can't learn anything additional from his own response, – poncho Oct 28 '15 at 22:37
• I think what you're trying to do is impossible with one-way functions. You need a (somewhat) deterministic construction to satisfy (1) and a (completely) randomized construction to satsfy (2) so this isn't the way to go. Obviously you need a reversible function then, symmetric encryption is obviously out, you could however do a) hard-code a public key, b) run a three-pass protocol ("ping", certificate, Enc(A)) or c) apply some really fancy crypto (identity based public keys?). All of these approaches have draw-backs but are the only ones I can think of. – SEJPM Oct 29 '15 at 12:32

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.

• I disagree that it has a contradiction; I don't care if a third party who has a guess of $A$ can learn whether his guess is correct. What I want is that a third party who doesn't have a plausible guess for $A$ is unable to correlate two different exchanges. The distinction between Bob and the third party is that Bob has the correct value of $A$ in his pile of $B_i$ values; the third party does not. The 'linear scan for a matching $B_i$" actually works; it's just less efficient than I'd like. – poncho Nov 2 '15 at 14:23
• I guess a sublinear solution is not possible unless you reveal something about $A$, e.g. some characters of it. – MH Samadani Nov 3 '15 at 14:03

Not a real solution yet, still:

"linear time", I guess, means linear in number of strings. This is a reasonable efficiency expectation in case of relatively large number of short strings.

There could be a solution, I guess, by deciding on incremental prefix or suffix of all candidate strings until the single match. This might grow into new research in private matching.

This is a very boring answer and it doesn't actually make it more efficient but it might still improve performance... ;)

If you take non-random nonces (like a counter or some number from other parts of the protocol) for your $r$ in $Hash(A||r)$ Bob could possibly save some time by precomputing all the $Hash(B_i||r)$ and putting them in a Hash table.