Variable relinearization in homomorphic encryption

A method for variable relinearization in homomorphic encryption, the method comprising:

• storing homomorphic encrypted data as a dataset in a memory device;
• and
• at a processor system:
• receiving a request containing a query of the homomorphic encrypted data of the dataset from another computing device via a communications network;
• and
• evaluating the homomorphic encrypted data of the dataset based on the query to determine requested data at least in part by:
• performing a multiplication operation on a ciphertext in the homomorphic encrypted data of the dataset responsive to the query, the multiplication operation contributing to increase a noise component in the ciphertext;
• determining one or more projected subsequent multiplication operations on the ciphertext;
• determining a relinearization amount that sets a noise increase in the ciphertext to a size that satisfies a noise increase performance target based at least in part on the one or more projected subsequent multiplication operations on the ciphertext, wherein the relinearization amount is determined based at least in part on a number of the one or more projected subsequent multiplication operations;
• relinearizing the ciphertext utilizing the determined relinearization amount;
• and
• returning the requested data to the other computing device via the communications network.

A method for variable relinearization in homomorphic encryption, the method comprising:

• storing homomorphic encrypted data as a dataset in a memory device;
• and
• at a processor system:
• receiving a request containing a query of the homomorphic encrypted data of the dataset from another computing device via a communications network;
• and
• evaluating the homomorphic encrypted data of the dataset based on the query to determine requested data at least in part by:
• performing multiplication operations on a ciphertext in the homomorphic encrypted data of the dataset responsive to the query, the multiplication operations each contributing to increase a noise component in the ciphertext;
• estimating a noise level in the ciphertext after each of the multiplication operations, the noise level being estimated based on an initial noise component in the ciphertext and the noise increase to the noise component;
• determining a variable relinearization amount that sets a noise increase in the ciphertext to a size that satisfies a noise increase performance target based at least in part on one or more subsequent multiplication operations performed on the ciphertext, wherein the relinearization amount is determined based at least in part on a number of the one or more projected subsequent multiplication operations;
• relinearizing the ciphertext utilizing the determined variable relinearization amount;
• and
• returning the requested data to the other computing device via the communications network.