Function-Dependent Commitments from Homomorphic Authenticators

In cloud computing, delegated computing raises the security issue of guaranteeing data authenticity during a remote computation. In this context, the recently introduced function-dependent commitments (FDCs) are the only approach providing both fast correctness verification, information-theoretic input-output privacy, and strong unforgeability. Homomorphic authenticators—the established approach to this problem—do not provide information-theoretic privacy and always reveal the computation’s result upon verification, thus violating output privacy. Since many homomorphic authenticator schemes already exist, we investigate the relation between them and FDCs to clarify how existing schemes can be supplemented with information-theoretic output privacy. Specifically, we present a generic transformation turning any structure-preserving homomorphic authenticator scheme into an FDC scheme. This facilitates the design of multi-party computation schemes with full information-theoretic privacy. We also introduce a new structure-preserving, linearly homomorphic authenticator scheme suitable for our transformation. It is the first both context hiding and structure-preserving homomorphic authenticator scheme. Our scheme is also the first structure-preserving homomorphic authenticator scheme to achieve efficient verification.