2
$\begingroup$

Given the following situation, what sort of cryptographic construction am I looking for?

  • Alice has a bitfield (vector, polynomial representation, etc.)
  • Bob has a different bitfield of the same length
  • Alice and Bob want to know the bitwise AND of their two bitfields without revealing the result to others and without revealing their personal bitfields to each other or anyone else

For example

  • Alice has 0101
  • Bob has 1100

What would one do for Alice and Bob to know the result 0101 & 1100 = 0100 without revealing anything as stated above?

I imagine this would require some combination of zero-knowledge and homomorphic techniques, but I will be the first to admit that this is probably a bit out of my depth.

$\endgroup$
1
  • 1
    $\begingroup$ Obviously, given the partially-reversible quality of the AND operation, some data will be revealed to the other participant, but I'm explicitly excluding that weakness in my thinking here. I'm not worried about Mallory sending 1111. $\endgroup$ Aug 25, 2018 at 2:42

2 Answers 2

4
$\begingroup$

The concept of "bitfield" is in fact irrelevant in this case since it doesn't really matter to which algebraic structure the data belongs to, at the end you're not using this structure at all, you're just treating them as bit strings.

What you're looking for is Secure Multiparty Computation (MPC). A bit more specifically, you need Two party computation (2PC). There are many techniques to achieve this but since you're working over a binary representation I recommend you to take a look at Garbled circuits or TinyOT (the latter should perform well since your circuit has low depth).

As a note, you cannot achieve this with something weaker than 2PC since computing AND gates is essentially complete for 2PC, meaning that any other solution you find could potentially imply a 2PC protocol.

$\endgroup$
2
  • $\begingroup$ That's exactly it! Thanks for showing me to the trailhead :) $\endgroup$ Aug 29, 2018 at 4:46
  • $\begingroup$ No problem, hope you find what you're looking for :) $\endgroup$
    – Daniel
    Aug 29, 2018 at 7:48
0
$\begingroup$

Since I don't get enough reputation to comment, I'll leave a new answer here.

know the result 0101 & 1100 = 0100 without revealing anything as stated above?

The answer to this question is NO. No matter how fancy the crypto tricks are, the truth still holds: ONCE one party knows the final result, the privacy of the other party's input will be compromised. Because together with his input(let's say Alice knows the result )

holds:0101 get: 0100

we all know that 0&0=0 0&1=0 1&1=1 1&0=0

So it's clear that Alice can definitely recover some bits of Bob's input where a bit 1 occurs in the result.

And the sad news here is that MPC does NOT work at all. Of course, it's well known that MPC guarantees the privacy of input of both parties. BUT MPC fails when the result itself leaks information about parties' data. In fact, the security definition of MPC indicates what I mentioned above is not complete, the latter half of the definition is:

except what be derived from the output.

Note information leaked from the result does not contradict the security definition of MPC. The reason is what can be learned from REAL world can be learned from IDEAL world(computation is done by a trusted third party) So when we utilize MPC as a privacy tool, it's crucial that the first step to asking whether utilizing MPC brings privacy or NOT. A bad concrete example to calculate the sum of two numbers by MPC: a+b=c. An easy invert algorithm simply calculates b=c-a can get the genuine input of Bob.

$\endgroup$
3
  • $\begingroup$ And is destructive. If the result is 0 and you have 0 then you cannot determine that the other party has 0 or 1. In Short, your first paragraph contradicts with the rest. $\endgroup$
    – kelalaka
    Aug 20, 2020 at 10:46
  • $\begingroup$ The privacy of MPC is defined to only give the result, and no additional information beyond that. It makes no statement about what the parties can find out from the result. It's fairly obvious, that you can't get any better than that, unless you break the functionality. If the intended functionality fits to the understanding of privacy is another question - it is just important that everyone understands that. $\endgroup$
    – tylo
    Aug 20, 2020 at 22:03
  • $\begingroup$ @kelalaka My apology to inaccuracy, But I believe I made my point $\endgroup$ Aug 21, 2020 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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