0
$\begingroup$

Suppose there is a ciphertext $C_1$ that hides message $m_1$ using a distributed additively homomorphic public key. I would like the holders of the key to run a protocol where if $m_1 = 0$, then it will return a ciphertext of $0$, but if $m_1 \neq 0$, then it will return a ciphertext of $1$. However, I would like this done without the key holders knowing whether $m_1 = 0$. I am assuming that there are not enough key holders that refuse to improperly decrypt the $C_1$

My instinct is to use some kind mix network using a Plaintext Equality Test. However, the result of the PET (true or false) would allow the key holders and any external verifier to know whether $m_1 = 0$.

Is there a known mechanism to allow the key holders to return a ciphertext with the correct value without it being made known which path was taken?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

The most natural option would be the following:

  • Let the parties run threshold decryption to obtain additive shares of the plaintext $m_1$
  • Run an MPC protocol that takes as input shares of $m_1$ and outputs shares of the equality test $[m_1 = _? 0]$. For example, in the two-party setting, you can use my paper (which is more or less still the state of the art, depending on your exact context -- size of $m_1$, time for preprocessing, number of executions, etc). There are also solutions in the $n$-party setting, the introduction of my paper should indicate what was the state of the art in 2016, but I'm not sure what would be the best solution now.
  • Convert back the shares of the output into an encryption of the output, the usual way: everyone encrypts their shares, broadcasts the ciphertexts, and the encrypted shares are homomorphically summed to recover the encrypted result.

In the two-party setting, there are very efficient equality tests (the one from my paper, but also others which are better if preprocessing is cheap, like this one), so this should overall work very well. I expect it to be more costly in the $n$-party setting with $n>2$, but you should search a bit the literature to know for sure!

EDIT for clarification:

The paper just assume that two parties have $x$ and $y$, and want to test whether $x = y$. If you have a threshold encryption scheme where the plaintext space is $\mathbb{Z}_n$, after threshold decryption, the parties have respective shares $m_1, m_2 \in \mathbb{Z}_n$ (seen as integers between $0$ and $n-1$) of the plaintext $m$. Then, testing whether $m=0 \bmod n$ is equivalent to testing whether $m_1 + m_2 = n$, i.e. testing whether $m_1 = n-m_2$. Hence, $P_1$ sets $x=m_1$, $P_2$ sets $y = n-m*2$, and the two parties run an equality test, as in my paper.

In the end, the parties have shares mod 2 of the result: that is, $b_1, b_2$ such that $b_1 \oplus b_2 = [m =_? 0]$, where $\oplus$ is the XOR. Then, the parties can easily construct an encryption of $[m =_? 0]$ with their additively homomorphic encryption scheme, using the identity $b_1 \oplus b_2 = b_1 + b_2 - 2b_1b_2$: $P_1$ sends a random encryption of $b_1$, and $P_2$ homomorphically compute an encryption of $b_1(1-2b_2) + b_2 = b_1 \oplus b_2 = [m=_? 0]$ (and rerandomizes it).

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for responding. From what I understood, your paper requires a bit-wise encrypted cipher. Unfortunately, in my larger setting, the ciphertext has gone through a large number of homomorphic operations that make determining a bitwise form of it difficult without decrypting it, which would defeat the purpose. Running these operations with bitwise ciphertexts would be prohibitively expensive. $\endgroup$ Commented Nov 14, 2022 at 20:12
  • $\begingroup$ No, my paper does not require this at all, it operates on shares over an integer ring, precisely what you get by doing distributed description of a standard additively homomorphic scheme, e.g. Paillier or something similar. I never assume any bitwise sharing and I don't think I mention anything about this setting in the paper. $\endgroup$ Commented Nov 16, 2022 at 10:45
  • $\begingroup$ Ah, I see. I misunderstood a part where you were talking about shares of size Z_2. $\endgroup$ Commented Nov 18, 2022 at 0:43
  • $\begingroup$ I wanted to write a comment to clarify exactly how to solve your problem using an equality test in the two-party setting, but it ended up being a bit long for the comment section, so I edited my answer. Feel free to ask if you need further clarification! $\endgroup$ Commented Nov 18, 2022 at 11:39
  • $\begingroup$ So the idea is that the multiple parties check to see if m_1 = n - m_2, and they get bits that can be combined with XOR to get an answer. A couple questions: I thought homomorphic XOR only existed in subgroups of size 2 and that a bitwise XOR required a bitwise representation of the ciphertext. $\endgroup$ Commented Nov 18, 2022 at 19:25

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.