Paper 2024/273

Perfect/Statistical 2-Party Computation with Improved Circuit Privacy

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). 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 1st 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, assuming the server is semi-honest in the setup protocol. Client privacy is statistical if the server is malicious during the setup protocol. 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, without circuit expansion, except for leaking the number of AND 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.