This paper, presented at ASIACRYPT 2011, tackles a fundamental efficiency bottleneck in Secure Multi-party Computation (MPC): the reliance on "bit-decomposition." By finding clever ways to bypass this primitive, the authors achieve constant-round protocols for private exponentiation and modulo reduction with linear communication complexity and perfect security.
TL;DR
The authors present the first constant-round, perfectly secure MPC protocol for private exponentiation with linear communication complexity by eliminating the need for expensive bit-decomposition. They also introduce a "hybrid-base" digit decomposition technique that significantly optimizes public modulo reduction, reducing communication costs by nearly a factor of four for small moduli.
What Problem Does This Paper Address?
In MPC, multiple parties want to compute a function over their private inputs without revealing the inputs themselves. Most efficient MPC systems use Linear Secret Sharing Schemes (LSSS), which make additions "free" (no communication) but multiplications "expensive."
A major hurdle in LSSS-based MPC is bit-decomposition (BD)—the process of converting a shared secret $x$ into sharings of its individual bits. BD is a "bridge" that allows arithmetic circuits (good for addition/multiplication) to interact with Boolean circuits (good for comparisons and bitwise logic). However, BD is computationally heavy; for perfect security, its communication complexity is non-linear (typically $O(l \log l)$ where $l$ is the bit-length).
While previous researchers found ways to perform equality tests and comparisons without BD, private exponentiation (computing $[x^a]$ where both $x$ and $a$ are secret) was widely believed to require BD of the exponent. This paper challenges that assumption.
Methods
The authors propose two primary algorithmic improvements:
-
Private Exponentiation without BD: Instead of decomposing the secret exponent $a$ into bits, they use a "masking" technique. They generate a random shared value $r$, compute $[c] = [a] + [r] \pmod p$, and reveal $c$. They then compute $x^c$ (using a public exponentiation sub-protocol) and $x^{-r}$ (using a bit-exponentiation sub-protocol on the bits of $r$). By combining these, they get $x^a$. To handle the modular "wrap-around" (where $a+r > p$), they use a linear comparison protocol.
-
The $\sqrt{l}$ Optimization: To further optimize the bit-exponentiation of $r$, they divide the $l$ bits into $s$ blocks of $t$ bits. By setting $s = t = \sqrt{l}$, they reduce the number of expensive public exponentiation calls from $l$ to $2\sqrt{l}$.
- Hybrid-base Digit-Decomposition: For public modulo reduction ($x \pmod m$), the authors generalize BD into a "hybrid-base" system. Instead of using a consistent base (like base-2 or base-$m$), they represent the number using a mix of bases: $[2, 2, ..., 2, m]$. This allows them to extract the remainder by focusing only on the "least significant digit" in this hybrid system, which is much more efficient than full base-$m$ decomposition.
Datasets
As a theoretical cryptography paper, no empirical datasets were used. The protocols are evaluated based on theoretical complexity: Round Complexity (number of communication steps) and Multiplicative Complexity (total number of secure multiplications required).
Key Insights and Ideas
- Bypassing the "Essential" Primitive: The most significant insight is that bit-decomposition is not a prerequisite for private exponentiation. By masking the exponent and revealing a blinded version, the problem shifts from "private exponentiation" to "public exponentiation," which is much cheaper.
- The Power of Hybrid Bases: The shift from uniform base-m decomposition to a hybrid $[2, ..., m]$ base is an "aha moment" for modulo reduction. It allows the protocol to leverage the efficiency of binary operations for the bulk of the number while using the specific modulus $m$ only where it matters (the remainder).
- Linearity is King: In MPC, moving from $O(l \log l)$ to $O(l)$ communication is the difference between a protocol that is theoretically interesting and one that is practically scalable for large bit-lengths.
Key Results
- Private Exponentiation: The new
Pri-Expo+protocol achieves a communication complexity of roughly $162l$ multiplications (plus a $2\sqrt{l}$ term). This is a massive improvement over the previous state-of-the-art, which required $O(l \log l)$ multiplications and had significantly higher constants. - Public Modulo Reduction: The
Pub-MR+protocol reduces the communication complexity from approximately $326l$ to $78l$ multiplications (for small $m$). In a concrete example ($l=256, m=100$), the authors calculate a 3.8x reduction in communication cost. - Perfect Security: All proposed protocols maintain perfect security (security against an unbounded adversary) in the honest-majority setting.
Limitations and Future Work
- Round Complexity Constants: While the round complexity is "constant" (it doesn't grow with $l$), the constants are still relatively high (e.g., 19 to 22 rounds). In high-latency networks, this could still be a bottleneck.
- Public Exponentiation Sub-protocol: The authors note that their
Pub-Exposub-protocol's complexity depends on the number of parties ($n$) and a security parameter ($k$) for "cut-and-choose" methods in the malicious case. They leave the construction of aPub-Expoprotocol independent of $n$ and $k$ as an open problem. - Preprocessing: The paper notes that round complexity could be further reduced by moving random value generation to a preprocessing phase, though they did not detail this optimization to maintain clarity in the main analysis.
Summary updated