14
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – SEJPM
    Commented Oct 28, 2015 at 21:35
  • $\begingroup$ ... 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. $\endgroup$
    – SEJPM
    Commented Oct 28, 2015 at 21:47
  • $\begingroup$ @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'$ $\endgroup$
    – poncho
    Commented Oct 28, 2015 at 22:33
  • $\begingroup$ @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, $\endgroup$
    – poncho
    Commented Oct 28, 2015 at 22:37
  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Commented Oct 29, 2015 at 12:32

4 Answers 4

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – poncho
    Commented Nov 2, 2015 at 14:23
  • 1
    $\begingroup$ I guess a sublinear solution is not possible unless you reveal something about $A$, e.g. some characters of it. $\endgroup$
    – MH Samadani
    Commented Nov 3, 2015 at 14:03
1
$\begingroup$

Recently, this problem has received significant attention in the blockchain/cryptocurrency community as it appears in various applications:

  1. Recipient anonymous (instant) messaging.
  2. Detecting incoming payments efficiently and privately in stealth address schemes such as Umbra.
  3. Light clients for anonymous cryptocurrencies such as Zcash or Monero.

There are 3 main works and approaches to attack this problem.

  • Fuzzy Message Detection(ACM CCS 2021) by Gabrielle Back et al. This novel cryptographic scheme employs an untrusted server that coarsely filters the incoming messages for recipients. Each recipient can define a false positive rate $p$ and sends detection keys to the server. The detection keys will match every true positive message for a recipient, and each message not sent to the recipient will also yield a match to the detection keys of the recipient with probability $p$. Note that by construction, given the detection keys, the server can tell the false positive rate of each recipient. The false positive rate $p$ offers a privacy vs. efficiency (bandwidth) tradeoff.

    • If $p=0$, then the recipient only downloads their incoming (true positive messages). This is optimal from an efficiency/bandwidth point of view but does not offer privacy.
    • If $0\leq p \leq 1$, then the user downloads several false positive messages, i.e., in expectation $p(M-TP)$, where $M$ is the number of all messages and $TP$ is the number of true positive messages. This is less efficient than the previous option but provides some levels of anonymity.
    • If $p=1$, then the user downloads all the messages providing maximal recipient anonymity, but this approach is highly inefficient if the server stores numerous messages/transactions.

    For a more thorough anonymity and privacy analysis of this scheme, see this work: The Effect of False Positives: Why Fuzzy Message Detection Leads to Fuzzy Privacy Guarantees? by István A. Seres et al.

  • Private Signaling(USENIX 2021) by Varun Madathil et al. This paper observes that any meaningful scheme for this problem should offer full privacy. They propose two approaches:

    • Trusted execution environment (TEE)-based solution. This scheme relies on an untrusted server and a TEE, e.g., Intel SGX. It is an efficient (constant work for both sender and recipient) and private solution but relies on the strong assumption of TEE.
    • Garbled circuit-based solution. This scheme assumes two non-colluding servers that execute a garbled circuit. The garbled circuit encodes the detection of the messages. It is a fully private solution and efficient for senders and recipients (constant work again), but it requires quite some heavy work from the two servers.

  • Oblivious Message Retrieval(CRYPTO 2022) by Zeyu Liu and Eran Tromer. This scheme applies FHE to solve this problem. It provides full privacy and is somewhat efficient, but users need to have large detection keys, approximately $1$GB large. For constrained devices, large detection keys might make this scheme impractical. This scheme is currently under development for the Zcash cryptocurrency. See it here.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.