0
$\begingroup$

Consider the following scenario:

We have two agents, A and B.

B needs to prove that they know a secret to A, without sharing the actual secret.

e.g.: A needs a way to de-duplicate the secrets they receive from B, but they don't need to know the actual secrets. (and B does not want them to know)

Think of it like sharing a hash of that secret, except: it's a very small, low entropy source (there's about 1 billion possible values). This means that a simple hash would be vulnerable to a dictionary attack.

Now, B could add a hidden "salt" to each secret they share and then hash it, and that would make it harder for A to do a dictionary attack. As far as I can tell, this would "solve" the problem for the 1-1 case.

However, let's now introduce a third agent, C. C is sending the same type of secrets to A. B and C cannot share their secrets between each other.

C can end up sending "duplicates" of secrets that B has, even though they don't know what B has on their end.

A, of course, now needs to de-duplicate not only the secrets from B, but also from C.

The hidden salt won't work anymore because now C would need to know the salt to be able to generate the same hashes. Otherwise A would not be able to de-duplicate between keys from B and C. Having a shared salt however means that C could do a dictionary attack on B or vice-versa.

Can A, B and C reach an agreement where B and C can share their "proofs" with A, in a way that A can de-duplicate them, but no one can reveal each other's secrets?

If so, can this be generalized to any number of consumers/producers?

Being far from an expert in cryptography (I only really know the very basics), I'm not sure if I'm using the proper terms here. Let me know if I can clarify any of it. Also, this is not homework or anything like it - while it was motivated by a concrete problem that I read recently, this is mostly just curiosity. A rough explanation on why it isn't possible (in the case that it is not) would most definitely be sufficient for me. Same for a brief description of a known algorithm, even if just the name - with proper direction I can do some research myself.

(Just to be clear if it already isn't: A, B and C do not trust each other)

(Contrived) example

Alice and Bob want to sell stamps to a stamp collector. Think of a stamp as being a 7-character string with only lowercase characters, and the stamp collector can't just fabricate them itself.

The stamp collector will buy any stamp that they currently do not have. However, it won't buy the stamp right away: it will wait to see how many sellers have it, so it can buy the stamp at the lowest price.

So before sending the actual stamp, Alice (or Bob) have to send a "bid" to the collector, so it can check if they already have the stamp, or if someone else offered it. They can't send the actual stamp with that bid, or the collector would just have it for free, which is no fun for anyone. The collector needs to know "which" stamp the bid is for, even if they don't know the actual 7-character string - or it won't be able to compare bids.

$\endgroup$
14
  • $\begingroup$ B and C would need to put some trust in A, because A would be able to reveal to B or C if B and C share any duplicates with one another. If B shared one value at a time with A, B could be informed by A as soon as A notices that particular value is shared by C. Perhaps if you explained the concrete problem it might be easier to fully understand the trust constraints. $\endgroup$
    – knaccc
    Commented Apr 23, 2022 at 0:08
  • $\begingroup$ B or C cannot trust A at all, or each other. I'm not sure the (once) concrete problem would add anything TBH. Like I said, it motivated the question, but it's not really the problem I'm trying to solve or think about. $\endgroup$ Commented Apr 23, 2022 at 0:26
  • $\begingroup$ Are you saying that a requirement is that A will not be able to collude with B to inform B which of the B's blinded values B has in common with C? So therefore it should be impossible for B to send blinded values to A one by one, so that A can inform B as soon as a duplicate is observed? Are you also saying that further "agents" should not be able to participate without the permission of all existing agents, to prevent a variant of such collusion? $\endgroup$
    – knaccc
    Commented Apr 23, 2022 at 1:00
  • $\begingroup$ Are you looking for the convergent encryption? $\endgroup$
    – kelalaka
    Commented Apr 23, 2022 at 1:25
  • $\begingroup$ @knaccc no, that is not a requirement. In theory B and C are not even aware of each other (they only comunicate with A and no one else) $\endgroup$ Commented Apr 23, 2022 at 2:11

0

Your Answer

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

Browse other questions tagged or ask your own question.