2
$\begingroup$

According to Protocol A that was presented in Section 3.1 paper entitled "Some Efficient Solutions to Yao’s Millionaire Problem" (2013). [1]

In that protocol they used an assumption that there is an encryption function that has the homomorphism property with respect to both additions (over some finite field) and bitwise XOR operations.

Can someone please send a reference to scheme that uphold the requirements?

My current candidate is to combine the answer in [2] and micali-goldwaser encryption [3].

But I don't know how (and if it possible) the scheme could work and overcome: (1) $N$ in GM cannot be a $Z_{2^q}$ as it's a multiplication of two primes. and (2) Is it possible to work with 2-complement binary representation ( To perform the subtraction operation).

[1]- https://arxiv.org/pdf/1310.8063v1.pdf

[2]- Homomorphic encryption based on XOR

[3]- https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not sure I would trust that reference. That protocol A is very strange. Step 4 says "Bob decrypts $V$ to obtain $(a−b)\oplus R$ and sends the most significant bit (MSB) of the decrypted value to Alice – it contains the information about the sign of the operation $(a − b)$." I'm not sure how Bob even know what the MSB is because of R. the MSB of $(a-b)\oplus R$ is likely just a random bit. Anyways, my point is, if you are looking for a solution to Yao's, there are better protocols. Not to mention that they do not even cite whether or not such a homomorphic scheme exists. $\endgroup$
    – mikeazo
    Jan 11, 2017 at 14:50
  • $\begingroup$ I already contact the author and waiting to a reference. Alice is the one that will get the MSB of $(a-b)\oplus R$ by comparing it to the MSB of $R$ at step 5. I'm trying to modify that scheme (using the proposed encryption scheme) to a little different case. $\endgroup$
    – user1387682
    Jan 11, 2017 at 15:31

1 Answer 1

Reset to default
6
$\begingroup$

Assuming the finite field is of odd characteristic (that is, $GF(p^k)$ for some prime $p > 2$, then such an encryption operation would be FHE; and would be much bigger news than just only solving the Millionaire problem.

With such an encryption method, given $E(a)$, $E(b)$ and a constant $c$, we can compute $E(c)$,$E(a \oplus b)$, $E(a + b)$ and $E(c \times a) = E(\underbrace{a + a + ... + a}_{\text{c times}})$ (where the addition and multiplication are within $GF(p^k)$, If we can't compute $E(c)$ directly, we can just place $E(c)$ within the public key (assuming that the range of possible $c$'s is limited).

So, assuming $a, b$ are restricted to $\{0, 1\}$, we can compute the NAND operation $E(\overline{a \wedge b}) = E( 1 \oplus (k \times ((a + b) \oplus a \oplus b)))\ $ for the constant $k = 2^{-1} \pmod p$. It is straightfoward to see that this function gives $E(1)$ if either of $a, b$ is 0, and $E(0)$ otherwise.

With this encrypted NAND function, we can construct any circuit.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Okay thanks for the clarification. but what about the case of $GF(2^q)$? $\endgroup$
    – user1387682
    Jan 11, 2017 at 15:36
  • 1
    $\begingroup$ In the $GF(2^k)$ case, addition is the same as xor, and so there do exist cryptosystems that can perform it homomorphically. However, while I haven't gone through their protocol, I suspect it wouldn't be sufficient (because the ability to do bitwise xor doesn't allow you to compute much; for example, you can't compute any function that isn't linear. $\endgroup$
    – poncho
    Jan 11, 2017 at 16:50
  • $\begingroup$ But does it necessary to the protocol? I mean , In the article they only use to perform subtraction and xor operations... no need for linear function there. In your does the below operations are permitted? $Enc(a)*(E(2^{k-1})*E(b)*E(1)=Enc(a-b)$ Where E(2^{k-1})*E(b)*E(1) is the calculation of 1-complement of 1. $\endgroup$
    – user1387682
    Jan 11, 2017 at 17:21
  • $\begingroup$ @user1387682: my NAND implementation requires the multiplicative inverse of $1+1$. In $GF(2^k)$, $1+1 = 0$, and so that inverse doesn't exist. As for the protocol, the function $a \ge b$ is a nonlinear function of $a, b$, and so it can't be computed if you're limited to xor's. $\endgroup$
    – poncho
    Jan 11, 2017 at 17:30
  • 1
    $\begingroup$ @user1387682: the protocol doesn't work in $GF(2^k)$ (or, for that matter, any $GF(p^k)$ for small $p$); they assume that the msbit of $a - b$ is set if $a < b$; however if we're in a small characteristic field, that's not true. In $GF(2^k)$, the msbit of $a - b$ will be set iff the msbit of $a$ and $b$ differ. $\endgroup$
    – poncho
    Jan 11, 2017 at 19:07

Your Answer

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

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