For example, given $E(m_1)$ and $E(m_2)$ to the cloud. How does it calculate $E(m{_1}^{m_2})$?

Is it related to the claim that any computable function can be represented as a circuit containing or xor (additive) and and (multiplicative) gates?

If so, what's the approach?


1 Answer 1


Yes, it is related and they don't need only addition and multiplication. If you know from the electronics the Functional completeness;

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression

What operation is suitable for functional completeness is fine. However, addition and multiplication are common since many mathematical structures have it. Besides, there are others,for example; there is a partial FHE that only supports x-or.

It is a similar idea in FHE and you can build almost any circuits. The basic problem is the semantic security which prevents the direct comparison of ciphertexts. You compare in a different way.

Also, if you look at TFHE: Fast Fully Homomorphic Encryption over the Torus yo can see the supported boolean operations;

The library supports the homomorphic evaluation of the 10 binary gates (And, Or, Xor, Nand, Nor, etc…), as well as the negation and the Mux gate. Each binary gate takes about 13 milliseconds single-core time to evaluate, which improves [DM15] by a factor 53, and the mux gate takes about 26 CPU-ms.

To calculate $E(m_1^{m_2})$? is really depend on the scheme. But basically you cannot use $E(m_1^{m_2}) = E(m_1) E(m_1) \dots E(m_1)$ since it will reveal your $m_2$. You need at least the repatings squaring method to hide the actual value.

With square-and-multiply you can at least hide the actual value of the power, not the size. let convert the below code into bit based FHE;

Let b be the “base” of the power, let p be the exponent.
Let r = the multiplicative identity (e.g.: 1).
Let s = b.
While p > 0 do:
    if p is odd
        let r = r * s.  // The "multiply"
    Let s = s * s       // The "square"
    Let p = p / 2 //(throw out the remainder).
The result is r

FHE version ( I keep $b=m_1$ and $p=m_2$);

While C(p,0) do:
    r =(r*s∗ S)+(r∗S′)
    Let s = s * s
    Let p = p >> 1 
The result is r

in this code C(p,0) is the comparator as in Representing a function as FHE circuit. The multiply is performed by the if condition 'S' keep the value of p is odd. Since it is semantically secure we apply multiplication by the bit for if and it's inverse for the else case.

As you can see from this circuit this will only release the number of bits in $m_2$

In Short: We can build almost any circuit, however, some circuits may reveal some information that either sensitive or not depending on the problem


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.