Paper 2023/268

Verifiable Multi-Client Functional Encryption for Inner Product

Abstract

Joint computation on encrypted data is becoming increasingly crucial with the rise of cloud computing. In theory, multi-party computation (MPC) allows for secure computation, but it is often impractical due to intensive interactions between users. In recent years, the development of multi-client functional encryption (MCFE) has made it possible to perform joint computation on private inputs, without any interaction. Well-settled solutions for linear functions have become efficient and secure, but there is still a shortcoming: if one user inputs incorrect data, the output of the function might become meaningless for all other users (while still useful for the malicious user). To address this issue, the concept of verifiable functional encryption was introduced by Badrinarayanan et al. at Asiacrypt '16 (BGJS). However, their solution was impractical because of strong statistical requirements. More recently, Bell et al. introduced a related concept for secure aggregation, with their ACORN solution, but it requires multiple rounds of interactions between users. In this paper, - we first propose a computational definition of verifiability for MCFE. Our notion covers the computational version of BGJS and extends it to handle any valid inputs defined by predicates. The BGJS notion corresponds to the particular case of a fixed predicate, in our setting. - we then design a concrete construction of verifiable MCFE for inner-product computations where the inputs are within a range. Verifiability cannot be easily obtained from classical proof systems only because the encryption key is usually secret in MCFE and the encryptor can maliciously perform the encryption without being detected. So we need to effectively combine different techniques such as commitments and range proofs to achieve the verifiability. Our approach can also be applied to input validation for secure aggregation as a special case.