Is it possible to use BGW scheme, to compute (private value) power of some other private input?

I believe that it's not possible, because this scheme allow only multiplication and addition. Where here we need to know the number of multiplication operations in front of the protocol.

Is there any other MPC (more efficient than Yao's GC/ or extension to BGW), that I can use to compute a "gate power"?



1 Answer 1


The exact solution will depend on the specific setting you have in mind, but yes, it should be basically feasible. Suppose for example that Alice has a private input $a$, and Bob has a private $t$-bit input $b = b_0b_1\cdots b_{t-1}$ (the length $t$ is public; we always have to assume some public bound on the values of the parties anyway, whatever the protocol we plan to run).

A simple solution would be the following: Alice computes $a_i \gets a^{2^i}$ for $i=0$ to $t-1$. Then, both parties run any MPC protocol to securely compute $$\prod_{i=0}^{t-1} \left((a_i-1)\cdot b_i + 1\right) = \prod_{i=0}^{t-1} a_i^{b_i} = a^{\sum_i 2^i b_i} = a^b.$$

This requires $t$ secure multiplications and $t$ secure additions.

In this simple, setting where both parties hold one of the inputs (instead of, say, shares of the inputs), you can also use the following natural ElGamal-based solution:

  • Alice encrypts her input with an ElGamal encryption scheme over a group of prime order $p$, and sends the ciphertext to Bob;
  • Bob can homomorphically compute an encryption of $a^b \bmod p$ from this ciphertext and sends it back to Alice;
  • Alice decrypts the result and get $a^b \bmod p$.

The protocol can be repeated multiple time with different primes $p_i$ until $\prod_i p_i > a^b$, and $a^b$ can then be reconstructed over the integers via CRT. There are a few details to take care of in this solution (e.g. if Alice's input is $0$, she would have to encrypt some arbitrary non-zero value instead, set her output to $0$, and ignore the content of the ciphertexts sent by Bob), but that should work.

There are alternative, more complex solutions that would be more suited in other scenarios (e.g. if $b$ is very large, and if the inputs are not known to each party but secretly shared between them, etc), see for example my paper on encryption switching, or this paper.


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.