Paper 2026/685

Efficient e = 3 Threshold RSA via Integer Coordinates for Intel SGX

Abstract

Threshold RSA signatures face a fundamental obstacle: reconstructing the private exponent from Shamir shares requires Lagrange coefficients whose computation involves modular division by values tied to $\phi(N)$, which must remain hidden. This obstacle is particularly acute for critical deployments such as Intel SGX code signing, which mandates $e=3$. Existing $e=3$-compatible approaches incur substantial overhead, increased share sizes, or sacrifice security properties such as perfect secrecy. This work introduces the integer coordinate framework, achieving $e=3$ support with EUF-CMA security under the standard RSA assumption alone. By carefully selecting interpolation coordinates that yield integer-valued Lagrange coefficients, we eliminate all modular inversions modulo $\phi(N)$, requiring only standard integer arithmetic and modular exponentiation. The framework achieves $O(\kappa)$-bit share sizes, perfect secrecy, and computational efficiency previously unattained for $e=3$-compatible schemes. Although we currently lack an efficient general algorithm for constructing coordinate sets for arbitrary $(t,n)$—a challenging open problem for future work—the coordinate families found via heuristic search achieve coverage for $2 \leq t \leq n \leq 9$ and selected $n=10$ configurations, sufficient for small boardroom-size deployments. The resulting online protocol is extremely simple and immediately enables practical $e=3$ threshold RSA for Intel SGX and similar applications.