Efficient Two-Party Exponentiation from Quotient Transfer
Yi Lu, Keisuke Hara, Kazuma Ohara +2 more
Secure multi-party computation (MPC) allows participating parties to jointly compute a function over their inputs while keeping them private. In particular, MPC based on additive secret sharing has been widely studied as a tool to obtain efficient protocols secure against a dishonest majority, including the important two-party case. In this paper, we propose a two-party protocol for an exponentiation functionality based on an additive secret sharing scheme. Our proposed protocol aims to securely compute a public base exponentiation ax mod p for an odd prime p, where the exponent x ∈ ℤp is a (shared) secret and the base a ∈ ℤp is public. Our protocol is based on a new simple but efficient approach involving quotient transfer that allows the parties to perform the most expensive part of the computation locally, but requires the base a ∈ ℤp to be a quadratic residue. To address scenarios where the base does not fulfill this, we combine our exponentiation protocol with a new efficient modulus conversion protocol which might be of independent interest. Even taking into account a potential modulus conversion, our exponentiation protocol only requires 3 rounds and 4 invocations of multiplication.
IEICE Transactions on Information and Systems•Aug 20, 2025•0 citations