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.

  • $\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$ – Scott Colby Aug 25 '18 at 2:42

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.

| improve this answer | |
  • $\begingroup$ That's exactly it! Thanks for showing me to the trailhead :) $\endgroup$ – Scott Colby Aug 29 '18 at 4:46
  • $\begingroup$ No problem, hope you find what you're looking for :) $\endgroup$ – Daniel Aug 29 '18 at 7:48

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.