Score:0

Crypto

Oblivious Decision Making

Zarquan

11/11/23, 9:18 PM

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?

1 + 0

multiparty-computation

mixnets

Score:0

Crypto

Geoffroy Couteau

11/12/23, 4:55 PM

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).

+ 8

Zarquan

11/14/23, 8:12 PM

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.

Geoffroy Couteau

11/16/23, 10:45 AM

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.

Zarquan

11/18/23, 12:43 AM

Ah, I see. I misunderstood a part where you were talking about shares of size Z_2.

Geoffroy Couteau

11/18/23, 11:39 AM

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!

Zarquan

11/18/23, 7:25 PM

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.

Zarquan

11/18/23, 9:32 PM

I will say I didn't fully follow your PET protocol, and I would love to understand it. But your approach of splitting it in to shares then processing it internally between the parties gave me a solution that will work in my context. Thanks!

Geoffroy Couteau

11/19/23, 12:48 PM

(Answering your second to last comment) see the EDIT to my answer: I explain how the parties can compute the XOR on their ciphertexts, using only standard mod n homomorphic operations (additions, multiplications by a constant) plus some interaction. The key trick is that x XOR y is the same as x + y - 2*x*y mod n for any large modulus n, when x and y are bits.

Zarquan

11/21/23, 6:51 PM

So it is. I'm kicking myself for not knowing that, I must have known it at some point.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Oblivious Decision Making

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.