Paper 2024/273

Perfect 2-Party Computation from Somewhat Additive Homomorphic Encryption

Abstract

We present protocols where one entity, the server, evaluates a circuit with encrypted inputs from the second party, the client. We give secret key somewhat additive homomorphic schemes where the client has perfect privacy (server is computationally unbounded). Our scheme is somewhat additive homomorphic and we extend it to support multiplication. The server handles circuit multiplication gates by sending the multiplicands to the client which does the multiplication and updates the decryption key so that the original ciphertext vector includes the encrypted multiplication gate outputs. The key idea for client privacy is the permutation table which consists of rows of vectors modulo a prime integer m. The initial row is (1, d2, . . . , dc) where di−1|di, di > N (a + 1)di−1, for an integer N which is a power of 2 and integer a, 2 ≤ i ≤ c. Subsequent rows are integer multiples of the first row, modulo m. The permutation table has a subset of rows (vectors) whose components are relatively short (facilitating addition without overflowing m) and which map to every possible vector modulo N (giving perfect privacy since every plaintext vector is possible given a ciphertext vector from the table.) We give a 2-party computation (2PC) protocol that also incorporates server inputs where the client has perfect privacy. Server privacy only holds against a computationally bounded adversary since it depends on the hardness of a variant of the HSSP (Hidden Subset Sum Problem) and the DDH (Decisional Diffie Hellman Assumption). We leverage the Castagnos Laguillaumie linear homomorphic public key encryption for setup. 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.