Paper 2025/395

On the (In)security of Approximate Computation Protocols from CKKS

Abstract

Secure Multi-Party Computation (MPC) enables collaborative and privacy-preserving computation over private inputs. Recent advances in Homomorphic Encryption (HE), particularly the CKKS scheme, have significantly improved the practicality of secure computation, making it suitable for real-world applications involving approximate arithmetic. However, the inherent errors introduced by CKKS pose substantial challenges in the design and analysis of CKKS-based secure computation protocols. In this work, we investigate the correctness and security of existing CKKS-based MPC protocols. Most prior constructions rely on the noise smudging technique, in which each party independently adds exponentially large noise to the output to guarantee the security of the protocol. However, we show that this approach does not achieve standard simulation-based security for MPC. To address this limitation, we apply an alternative method, called collaborative sampling, in which all participating parties jointly generate additive shares of the smudging noise. We consider both asymmetric two-party protocols between a client and a server, and symmetric multiparty protocols among mutually distrusting parties. For each setting, we present concrete protocol constructions based on collaborative sampling, explicitly define the corresponding ideal functionalities, and provide formal security proofs. We further provide concrete constructions and implementations of collaborative sampling protocols. As an alternative perspective, we show that existing protocols, despite failing to achieve standard simulation-based security, still satisfy a weaker security notion called liberal security for approximate MPC protocols.