Two-Server Delegation of Computation on Label-Encrypted Data
This work addresses the need for efficient and verifiable secure delegation of computations on encrypted data, offering improvements over prior methods but is incremental in nature.
The paper tackles the problem of delegating high-degree computations on encrypted data by proposing a new scheme that replaces linearly-homomorphic encryption with label-based encryption and pseudorandom functions, reducing server computations and enabling verifiable computations, while extending to d-server schemes for degree-d computations.
Catalano and Fiore propose a scheme to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating quadratic computations on ciphertexts. Their scheme is based on the linearly-homomorphic encryption (such as Goldwasser-Micali, Paillier and ElGamal) and need to perform large integer operation on servers. Then, their scheme have numerous computations on the servers. At the same time, their scheme cannot verify the computations and cannot evaluate more than degree-4 computations. To solve these problems, we no longer use linearly-homomorphic encryption which based on number theory assumptions. We use label and pseudorandom function to encrypt message, which significantly reduce the computations on the servers and enable us to use homomorphic MACs technology to realize verifiable computations naturally. We also extend the method to construct $d$-server schemes, which allow the client to delegate degree-$d$ computations on outsourced data.