Paper 2024/273

Perfect 2-Party Computation from Additive Somewhat Homomorphic Encryption

Abstract

Two-party computation has been an active area of research since Yao's breakthrough results on garbled circuits. We present secret key somewhat homomorphic additive schemes where the client has perfect privacy (server can be computationally unbounded). Our basic scheme is somewhat homomorphic additive and we extend it to support multiplication. The server handles circuit multiplication gates by returning the multiplicands to the client which updates the decryption key so that the original ciphertext vector includes the encrypted multiplication gate outputs. We give a 2-party computation (2PC) protocol that also incorporates server inputs where the client has perfect privacy. Server privacy holds against a computationally bounded adversary since it depends on the hardness of the subset sum problem. The 2PC protocol maintains circuit privacy except for leaking the number of multiplication gates to the client. Scaling the 2PC protocol via separate encryption parameters for smaller subcircuits allows the ciphertext size to remain constant as circuit size grows.