Additively homomorphic encryption is a remarkably useful tool with one frustrating limitation. With Paillier, you can add ciphertexts, and multiply a ciphertext with a plain number (scalar multiplication). You can compute sums, averages and weighted scores on data nobody can see. But you can’t multiply two ciphertexts together. That one missing operation rules out a surprising number of everyday computations: the variance of encrypted salaries, the correlation between two encrypted columns, the dot product of two encrypted vectors, or the distance between two encrypted points.
Fully homomorphic encryption solves this, at the cost of heavy machinery. But in Using Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data (ACM CCS 2015), Dario Catalano and Dario Fiore showed something delightful: you can bolt exactly one multiplication onto almost any additive scheme, without changing the scheme at all, using nothing more than high school algebra and a one-time pad. In this post, we’ll take that trick apart piece by piece, and then use it with LightPHE in Python, Go, Java and TypeScript.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Thinking in Degrees
The cleanest way to describe what a homomorphic scheme can compute is the degree of the polynomial it can evaluate on encrypted inputs. Additions and multiplications with plain constants never raise the degree, so an additive scheme evaluates degree-1, or linear, functions. Multiplying two encrypted inputs gives degree 2, and that’s exactly what everyday statistics often need:
| Computation on encrypted x, y | Formula | Degree |
| Sum, mean | x_1 + x_2 + … + x_n | 1 |
| Weighted score with plain weights | w_1 x_1 + … + w_n x_n | 1 |
| Variance | needs x_1^2 + … + x_n^2 | 2 |
| Covariance, correlation | needs x_1 y_1 + … + x_n y_n | 2 |
| Dot product of two encrypted vectors | x_1 y_1 + … + x_n y_n | 2 |
| Squared euclidean distance | (x_1 – y_1)^2 + … + (x_n – y_n)^2 | 2 |
| Product of three encrypted values | x y z | 3 |
Homomorphic schemes form a ladder. Partially homomorphic schemes like Paillier stop at degree 1. Degree-2 schemes, such as Boneh-Goh-Nissim with its bilinear pairings, allow one multiplication. Somewhat homomorphic schemes allow a bounded number of multiplications, and fully homomorphic schemes allow any number, at a steep price. Catalano-Fiore lifts an ordinary additive scheme exactly one rung up, to degree 2.
The Trick, Step by Step
Step 1: Hide the Message Behind a One-Time Pad
Take any additively homomorphic scheme Enc with a public plaintext space of integers modulo M. To encrypt a message m, pick a uniformly random b in that space, and output a pair: the message masked with b in the clear, and an ordinary encryption of b.
pick a random b in [0, M) ciphertext of m: ( a, Enc(b) ) where a = m - b mod M
It feels wrong to leave a in the clear, but it reveals nothing: b is uniformly random and secret, so a = m - b is uniformly random too, whatever m is. It’s a one-time pad. The pad itself, b, is protected by the underlying scheme. Anyone with the private key decrypts b and adds it back: m = a + b.
Step 2: Additions Still Work
Adding two such ciphertexts is easy: add the clear parts as numbers, and the encrypted parts homomorphically. Multiplying with a plain constant scales both. Nothing has been gained yet, but nothing has been lost either.
(a1, Enc(b1)) + (a2, Enc(b2)) = (a1 + a2, Enc(b1) + Enc(b2)) encrypts (a1 + b1) + (a2 + b2) = m1 + m2 k * (a, Enc(b)) = (k a, k Enc(b)) encrypts k m
Step 3: Multiply With High School Algebra
Here is where the magic happens. Expand the product of two messages, written as m = a + b:
m1 m2 = (a1 + b1)(a2 + b2) = a1 a2 + a1 b2 + a2 b1 + b1 b2
----- ----- ----- -----
plain plain * enc plain * enc enc * enc
Look at the four terms. a1 a2 is a product of two public numbers, so anyone can compute it and encrypt it. a1 b2 and a2 b1 are a public number times an encrypted value, which an additive scheme handles with scalar multiplication. Only the last term, b1 b2, is a product of two encrypted values, which the scheme can’t compute. So the evaluator computes the first three terms under encryption:
alpha = Enc(a1 a2) + a1 * Enc(b2) + a2 * Enc(b1) encrypts m1 m2 - b1 b2 multiplied ciphertext: ( alpha, [ (Enc(b1), Enc(b2)) ] )
And the missing b1 b2? The evaluator can’t compute it, but it doesn’t have to. It simply carries the two encrypted pads along. Whoever holds the private key can decrypt them separately and multiply them in the clear.
Step 4: Decrypt
m1 m2 = Dec(alpha) + Dec(Enc(b1)) * Dec(Enc(b2))
That’s the whole construction: the multiplication of two ciphertexts is split into the part an additive scheme can compute, and a leftover that is postponed to decryption time, where it becomes easy.
A Worked Example
Let’s multiply 3 and 4 in a toy plaintext space of integers modulo 100, where the random pads happen to be 17 and 58:
encrypt 3: b1 = 17, a1 = 3 - 17 mod 100 = 86 ciphertext (86, Enc(17))
encrypt 4: b2 = 58, a2 = 4 - 58 mod 100 = 46 ciphertext (46, Enc(58))
multiply: a1 a2 + a1 b2 + a2 b1 = 86 * 46 + 86 * 58 + 46 * 17 = 9726 = 26 mod 100
alpha = Enc(26), and the pair (Enc(17), Enc(58)) travels along
decrypt: 26 + 17 * 58 = 26 + 986 = 1012 = 12 mod 100, and indeed 3 * 4 = 12
Notice that the evaluator only ever saw 86 and 46, two numbers that look completely random, and never 3, 4 or 12.
Why Only One Multiplication
After a multiplication, the clear part is gone: a multiplied ciphertext is alpha and a list of pairs, all encrypted. The trick depended on having one factor of each term in the clear, so it can’t be repeated. Multiplying two multiplied ciphertexts would need terms like Dec(alpha) * Dec(alpha'), products of encrypted values with no clear factor to lean on. So LightPHE refuses a second multiplication of ciphertexts.
Everything else still works after the multiplication. Two multiplied ciphertexts are added by adding their alpha parts and joining their lists of pairs. A plain constant scales alpha and the first ciphertext of each pair. A non-multiplied ciphertext can be added too, as (a, Enc(b)) is easily rewritten as Enc(a) + Enc(b) with no pairs. So you can compute any sum of products, plus linear terms, plus constants: every degree-2 polynomial.
Why It’s Secure
The transform uses the underlying scheme strictly as a black box: encryption, decryption, addition and scalar multiplication, nothing else. The clear part of a ciphertext is a one-time-padded value, and everything else is an ordinary ciphertext of the underlying scheme. So the transform is exactly as secure as the scheme it wraps. Ciphertexts carry the public key only, so an untrusted cloud can do all the computing.
There is one thing a multiplied ciphertext does reveal: its structure. Each pair shows which two ciphertexts were multiplied together, though not their values. For most outsourced computations, that’s the computation the cloud was asked to do anyway.
The Price: Ciphertexts That Grow
Nothing is free. Every product leaves a pair of ciphertexts behind, and a sum of products keeps all of them. So a dot product of two encrypted vectors of length d carries d pairs, and decrypting it takes 2d + 1 decryptions of the underlying scheme. Here is what that looked like with 1024-bit Paillier keys on my laptop:
| Ciphertext | Serialized size |
| Plain Paillier ciphertext | 0.7 KB |
| Boosted ciphertext, before multiplication | 1.1 KB |
| Product of two ciphertexts | 2.2 KB |
| Dot product of two vectors of length 100 | 138 KB, computed in 4.2 seconds and decrypted in 2.4 seconds |
For statistics over thousands of records, that growth adds up. If you only need a few aggregates, such as a sum and a sum of squares, it’s perfectly fine.
Required Features of the Underlying Scheme
The construction asks surprisingly little of the scheme it wraps, but each requirement rules some schemes out:
1. Additive homomorphism and scalar multiplication, for adding the encrypted pads and multiplying them with the clear parts.
2. A public plaintext modulus, because the encryptor computes m - b mod M itself.
3. Decryption of any value, because the pads are uniformly random over the whole plaintext space, not small numbers.
4. Tolerance for large plain multipliers, because the clear parts that multiply the encrypted pads are uniformly random too.
Which Algorithms Can Be Used, and Why
LightPHE can boost ten of its cryptosystems. For the others, it refuses with a reason, and the reasons map exactly to the requirements above:
| Algorithms | Catalano-Fiore | Why |
| Paillier, Damgard-Jurik, Bresson-Catalano-Pointcheval, Camenisch-Shoup, Elliptic Curve Paillier, Joye-Libert, Castagnos-Laguillaumie, Naccache-Stern, Benaloh, Damgard-Geisler-Kroigaard | ✅ | Additive with a public plaintext modulus and direct decryption. Damgard-Geisler-Kroigaard’s plaintext space is only about 32 bits, though, so results wrap around quickly |
| Exponential ElGamal, Elliptic Curve ElGamal | ❌ | Their decryption solves a discrete logarithm, which is infeasible for the uniformly random pads |
| Okamoto-Uchiyama | ❌ | Its plaintext modulus is secret, so the encryptor can’t compute m - b mod M |
| Regev, Lyubashevsky-Peikert-Regev | ❌ | Multiplying with uniformly random constants exceeds their noise budget |
| Goldwasser-Micali, ML-KEM | ❌ | XOR only, without addition or multiplication with a constant |
| Boneh-Goh-Nissim, Freeman-Boneh-Goh-Nissim, Brakerski-Vaikuntanathan, Gentry-Halevi-Vaikuntanathan, Gentry-Sahai-Waters | ❌ | They already support multiplication natively, so there’s nothing to add |
| RSA, ElGamal | ❌ | Not additively homomorphic |
Catalano-Fiore vs Boneh-Goh-Nissim
Both give you one multiplication, but in very different ways:
| Catalano-Fiore | Boneh-Goh-Nissim | |
| Where it comes from | A transform on top of an existing additive scheme | A dedicated scheme built on bilinear pairings |
| Plaintext space | Large, e.g. 1024 bits with Paillier | Small, as decryption solves a discrete logarithm |
| Ciphertext size after multiplications | Grows with every product | Stays constant |
| Best for | Large values and a few aggregates | Small values and many products |
Example 1: The Rules of the Game
In LightPHE, Catalano-Fiore is a boost: you build an ordinary cryptosystem with boost = "Catalano-Fiore", and its ciphertexts gain one multiplication. Let’s see the rules in action: one multiplication, then as many additions and multiplications with plain constants as you like, but not a second multiplication.
from lightphe import LightPHE
# paillier boosted with catalano-fiore - the underlying paillier is used as is
cs = LightPHE(algorithm_name = "Paillier", boost = "Catalano-Fiore")
c3, c4, c5 = cs.encrypt(3), cs.encrypt(4), cs.encrypt(5)
# one multiplication of two ciphertexts
assert cs.decrypt(c3 * c4) == 12
# followed by any number of additions and multiplications with plain constants
assert cs.decrypt(c3 * c4 + c5) == 17
assert cs.decrypt(2 * (c3 * c4) + c3 * c5) == 39
# but not by a second multiplication of ciphertexts
try:
c3 * c4 * c5
raise AssertionError("a second multiplication must be refused")
except ValueError as err:
print(err) # Catalano-Fiore transform supports only one multiplication. ...
package main
import (
"fmt"
"log"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
// paillier boosted with catalano-fiore - the underlying paillier is used as is
cs, err := lightphe.New(lightphe.Paillier, lightphe.WithBoost(lightphe.CatalanoFiore))
check(err)
c3, err := cs.EncryptInt(3)
check(err)
c4, err := cs.EncryptInt(4)
check(err)
c5, err := cs.EncryptInt(5)
check(err)
// one multiplication of two ciphertexts
c12, err := c3.Multiply(c4)
check(err)
m, err := cs.Decrypt(c12)
check(err)
fmt.Println(m) // 12
// followed by any number of additions and multiplications with plain constants
c17, err := c12.Add(c5)
check(err)
m, err = cs.Decrypt(c17)
check(err)
fmt.Println(m) // 17
c24, err := c12.MultiplyByInt(2)
check(err)
c15, err := c3.Multiply(c5)
check(err)
c39, err := c24.Add(c15)
check(err)
m, err = cs.Decrypt(c39)
check(err)
fmt.Println(m) // 39
// but not by a second multiplication of ciphertexts
if _, err := c12.Multiply(c5); err != nil {
fmt.Println(err) // Catalano-Fiore transform supports only one multiplication, ...
} else {
log.Fatal("a second multiplication must be refused")
}
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.CatalanoFioreCiphertext;
import java.math.BigInteger;
// paillier boosted with catalano-fiore - the underlying paillier is used as is
LightPHE cs = LightPHE.builder().algorithmName("Paillier").boost("Catalano-Fiore").build();
CatalanoFioreCiphertext c3 = cs.encryptBoosted(3);
CatalanoFioreCiphertext c4 = cs.encryptBoosted(4);
CatalanoFioreCiphertext c5 = cs.encryptBoosted(5);
// one multiplication of two ciphertexts
assert cs.decrypt(c3.multiply(c4)).equals(BigInteger.valueOf(12));
// followed by any number of additions and multiplications with plain constants
assert cs.decrypt(c3.multiply(c4).add(c5)).equals(BigInteger.valueOf(17));
assert cs.decrypt(c3.multiply(c4).multiply(2).add(c3.multiply(c5))).equals(BigInteger.valueOf(39));
// but not by a second multiplication of ciphertexts
try {
c3.multiply(c4).multiply(c5);
throw new AssertionError("a second multiplication must be refused");
} catch (IllegalArgumentException e) {
System.out.println(e.getMessage()); // Catalano-Fiore transform supports only one multiplication. ...
}
import { LightPHE } from 'lightphe-ts';
// paillier boosted with catalano-fiore - the underlying paillier is used as is
const cs = new LightPHE({ algorithmName: 'Paillier', boost: 'Catalano-Fiore' });
const [c3, c4, c5] = [3, 4, 5].map((m) => cs.encrypt(m));
// one multiplication of two ciphertexts
console.assert(cs.decrypt(c3.multiply(c4)) === 12n);
// followed by any number of additions and multiplications with plain constants
console.assert(cs.decrypt(c3.multiply(c4).add(c5)) === 17n);
console.assert(cs.decrypt(c3.multiply(c4).multiply(2).add(c3.multiply(c5))) === 39n);
// but not by a second multiplication of ciphertexts
try {
c3.multiply(c4).multiply(c5);
throw new Error('a second multiplication must be refused');
} catch (err) {
console.log((err as Error).message); // Catalano-Fiore transform supports only one multiplication. ...
}
Java snippets use assert for brevity, so run them with -ea to enable assertions.
Example 2: Standard Deviation of Encrypted Salaries
A company keeps its payroll encrypted in the cloud, and wants the mean and the standard deviation of salaries. The mean needs only a sum, but the variance needs a sum of squares, a degree-2 function: variance = (x_1^2 + ... + x_n^2) / n - mean^2. So the cloud computes two encrypted aggregates, and the company decrypts just those two numbers.
from lightphe import LightPHE # company builds the cryptosystem, and keeps the private key company_cs = LightPHE(algorithm_name = "Paillier", boost = "Catalano-Fiore") # company encrypts its employees' salaries in thousands, and uploads them to the cloud salaries = [62, 85, 47, 120, 71, 93] encrypted_salaries = [company_cs.encrypt(salary) for salary in salaries] # cloud computes the encrypted sum and sum of squares - ciphertexts carry the public key only encrypted_sum = sum(encrypted_salaries) encrypted_sum_of_squares = sum(salary * salary for salary in encrypted_salaries) # company decrypts the two aggregates, and computes the mean and standard deviation n = len(salaries) mean = company_cs.decrypt(encrypted_sum) / n variance = company_cs.decrypt(encrypted_sum_of_squares) / n - mean ** 2 assert round(mean, 2) == 79.67 assert round(variance ** 0.5, 2) == 23.41
package main
import (
"fmt"
"log"
"math"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
// sum adds encrypted values up homomorphically
func sum(values []*lightphe.Ciphertext) *lightphe.Ciphertext {
total := values[0]
for _, value := range values[1:] {
var err error
total, err = total.Add(value)
check(err)
}
return total
}
func main() {
// company builds the cryptosystem, and keeps the private key
companyCs, err := lightphe.New(lightphe.Paillier, lightphe.WithBoost(lightphe.CatalanoFiore))
check(err)
// company encrypts its employees' salaries in thousands, and uploads them to the cloud
salaries := []int64{62, 85, 47, 120, 71, 93}
var encryptedSalaries []*lightphe.Ciphertext
for _, salary := range salaries {
c, err := companyCs.EncryptInt(salary)
check(err)
encryptedSalaries = append(encryptedSalaries, c)
}
// cloud computes the encrypted sum and sum of squares - ciphertexts carry the public key only
var squares []*lightphe.Ciphertext
for _, c := range encryptedSalaries {
square, err := c.Multiply(c)
check(err)
squares = append(squares, square)
}
encryptedSum, encryptedSumOfSquares := sum(encryptedSalaries), sum(squares)
// company decrypts the two aggregates, and computes the mean and standard deviation
n := float64(len(salaries))
total, err := companyCs.Decrypt(encryptedSum)
check(err)
sumOfSquares, err := companyCs.Decrypt(encryptedSumOfSquares)
check(err)
mean := float64(total.Int64()) / n
variance := float64(sumOfSquares.Int64())/n - mean*mean
fmt.Printf("mean %.2f, standard deviation %.2f\n", mean, math.Sqrt(variance)) // mean 79.67, standard deviation 23.41
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.CatalanoFioreCiphertext;
import java.util.List;
// company builds the cryptosystem, and keeps the private key
LightPHE companyCs = LightPHE.builder().algorithmName("Paillier").boost("Catalano-Fiore").build();
// company encrypts its employees' salaries in thousands, and uploads them to the cloud
List<Long> salaries = List.of(62L, 85L, 47L, 120L, 71L, 93L);
List<CatalanoFioreCiphertext> encryptedSalaries = salaries.stream().map(companyCs::encryptBoosted).toList();
// cloud computes the encrypted sum and sum of squares - ciphertexts carry the public key only
CatalanoFioreCiphertext encryptedSum = encryptedSalaries.stream()
.reduce(CatalanoFioreCiphertext::add).orElseThrow();
CatalanoFioreCiphertext encryptedSumOfSquares = encryptedSalaries.stream()
.map(salary -> salary.multiply(salary))
.reduce(CatalanoFioreCiphertext::add).orElseThrow();
// company decrypts the two aggregates, and computes the mean and standard deviation
double n = salaries.size();
double mean = companyCs.decrypt(encryptedSum).doubleValue() / n;
double variance = companyCs.decrypt(encryptedSumOfSquares).doubleValue() / n - mean * mean;
assert Math.round(mean * 100) == 7967;
assert Math.round(Math.sqrt(variance) * 100) == 2341;
import { LightPHE } from 'lightphe-ts';
// company builds the cryptosystem, and keeps the private key
const companyCs = new LightPHE({ algorithmName: 'Paillier', boost: 'Catalano-Fiore' });
// company encrypts its employees' salaries in thousands, and uploads them to the cloud
const salaries = [62, 85, 47, 120, 71, 93];
const encryptedSalaries = salaries.map((salary) => companyCs.encrypt(salary));
// cloud computes the encrypted sum and sum of squares - ciphertexts carry the public key only
const encryptedSum = encryptedSalaries.reduce((sum, salary) => sum.add(salary));
const encryptedSumOfSquares = encryptedSalaries
.map((salary) => salary.multiply(salary))
.reduce((sum, square) => sum.add(square));
// company decrypts the two aggregates, and computes the mean and standard deviation
const n = salaries.length;
const mean = Number(companyCs.decrypt(encryptedSum)) / n;
const variance = Number(companyCs.decrypt(encryptedSumOfSquares)) / n - mean ** 2;
console.assert(mean.toFixed(2) === '79.67');
console.assert(Math.sqrt(variance).toFixed(2) === '23.41');
The company learns a mean of 79.67 and a standard deviation of 23.41, in thousands, and the cloud learns nothing. Notice that the cloud doesn’t even need a cryptosystem of its own: Catalano-Fiore ciphertexts carry the public key, so it simply adds and multiplies them.
Example 3: Do Ads Drive Sales? Correlation on Encrypted Data
A retailer keeps its monthly ad spend and sales encrypted in the cloud, and wants to know how strongly they move together. The Pearson correlation needs five sums: of x, of y, of x times y, of x squared and of y squared. Three of them are degree-2. The cloud computes all five under encryption, and the retailer plugs the decrypted sums into the formula.
from lightphe import LightPHE # retailer builds the cryptosystem, and keeps the private key retailer_cs = LightPHE(algorithm_name = "Paillier", boost = "Catalano-Fiore") # retailer encrypts its monthly ad spend and sales in thousands, and uploads them to the cloud ad_spend = [10, 12, 15, 9, 20, 18] sales = [120, 130, 160, 110, 205, 190] encrypted_x = [retailer_cs.encrypt(x) for x in ad_spend] encrypted_y = [retailer_cs.encrypt(y) for y in sales] # cloud computes the five sums pearson correlation needs, three of them degree-2 encrypted_sums = [ sum(encrypted_x), # sum of x sum(encrypted_y), # sum of y sum(x * y for x, y in zip(encrypted_x, encrypted_y)), # sum of x * y sum(x * x for x in encrypted_x), # sum of x^2 sum(y * y for y in encrypted_y), # sum of y^2 ] # retailer decrypts the five sums, and computes the correlation sx, sy, sxy, sxx, syy = [retailer_cs.decrypt(c) for c in encrypted_sums] n = len(ad_spend) r = (n * sxy - sx * sy) / ((n * sxx - sx ** 2) * (n * syy - sy ** 2)) ** 0.5 assert round(r, 4) == 0.9973
package main
import (
"fmt"
"log"
"math"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
// sum adds encrypted values up homomorphically
func sum(values []*lightphe.Ciphertext) *lightphe.Ciphertext {
total := values[0]
for _, value := range values[1:] {
var err error
total, err = total.Add(value)
check(err)
}
return total
}
// products multiplies encrypted vectors element by element
func products(xs, ys []*lightphe.Ciphertext) []*lightphe.Ciphertext {
var out []*lightphe.Ciphertext
for i := range xs {
product, err := xs[i].Multiply(ys[i])
check(err)
out = append(out, product)
}
return out
}
func main() {
// retailer builds the cryptosystem, and keeps the private key
retailerCs, err := lightphe.New(lightphe.Paillier, lightphe.WithBoost(lightphe.CatalanoFiore))
check(err)
// retailer encrypts its monthly ad spend and sales in thousands, and uploads them to the cloud
adSpend := []int64{10, 12, 15, 9, 20, 18}
sales := []int64{120, 130, 160, 110, 205, 190}
encrypt := func(values []int64) []*lightphe.Ciphertext {
var out []*lightphe.Ciphertext
for _, value := range values {
c, err := retailerCs.EncryptInt(value)
check(err)
out = append(out, c)
}
return out
}
encryptedX, encryptedY := encrypt(adSpend), encrypt(sales)
// cloud computes the five sums pearson correlation needs, three of them degree-2
encryptedSums := []*lightphe.Ciphertext{
sum(encryptedX), // sum of x
sum(encryptedY), // sum of y
sum(products(encryptedX, encryptedY)), // sum of x * y
sum(products(encryptedX, encryptedX)), // sum of x^2
sum(products(encryptedY, encryptedY)), // sum of y^2
}
// retailer decrypts the five sums, and computes the correlation
var s []float64
for _, c := range encryptedSums {
m, err := retailerCs.Decrypt(c)
check(err)
s = append(s, float64(m.Int64()))
}
sx, sy, sxy, sxx, syy := s[0], s[1], s[2], s[3], s[4]
n := float64(len(adSpend))
r := (n*sxy - sx*sy) / math.Sqrt((n*sxx-sx*sx)*(n*syy-sy*sy))
fmt.Printf("correlation %.4f\n", r) // correlation 0.9973
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.CatalanoFioreCiphertext;
import java.util.ArrayList;
import java.util.List;
// retailer builds the cryptosystem, and keeps the private key
LightPHE retailerCs = LightPHE.builder().algorithmName("Paillier").boost("Catalano-Fiore").build();
// retailer encrypts its monthly ad spend and sales in thousands, and uploads them to the cloud
List<Long> adSpend = List.of(10L, 12L, 15L, 9L, 20L, 18L);
List<Long> sales = List.of(120L, 130L, 160L, 110L, 205L, 190L);
List<CatalanoFioreCiphertext> x = adSpend.stream().map(retailerCs::encryptBoosted).toList();
List<CatalanoFioreCiphertext> y = sales.stream().map(retailerCs::encryptBoosted).toList();
// cloud computes the five sums pearson correlation needs, three of them degree-2
CatalanoFioreCiphertext sumX = x.get(0), sumY = y.get(0);
CatalanoFioreCiphertext sumXY = x.get(0).multiply(y.get(0));
CatalanoFioreCiphertext sumXX = x.get(0).multiply(x.get(0));
CatalanoFioreCiphertext sumYY = y.get(0).multiply(y.get(0));
for (int i = 1; i < x.size(); i++) {
sumX = sumX.add(x.get(i));
sumY = sumY.add(y.get(i));
sumXY = sumXY.add(x.get(i).multiply(y.get(i)));
sumXX = sumXX.add(x.get(i).multiply(x.get(i)));
sumYY = sumYY.add(y.get(i).multiply(y.get(i)));
}
// retailer decrypts the five sums, and computes the correlation
List<Double> s = new ArrayList<>();
for (CatalanoFioreCiphertext c : List.of(sumX, sumY, sumXY, sumXX, sumYY)) {
s.add(retailerCs.decrypt(c).doubleValue());
}
double n = adSpend.size();
double r = (n * s.get(2) - s.get(0) * s.get(1))
/ Math.sqrt((n * s.get(3) - s.get(0) * s.get(0)) * (n * s.get(4) - s.get(1) * s.get(1)));
assert Math.round(r * 10000) == 9973;
import { LightPHE } from 'lightphe-ts';
// retailer builds the cryptosystem, and keeps the private key
const retailerCs = new LightPHE({ algorithmName: 'Paillier', boost: 'Catalano-Fiore' });
// retailer encrypts its monthly ad spend and sales in thousands, and uploads them to the cloud
const adSpend = [10, 12, 15, 9, 20, 18];
const sales = [120, 130, 160, 110, 205, 190];
const x = adSpend.map((value) => retailerCs.encrypt(value));
const y = sales.map((value) => retailerCs.encrypt(value));
// cloud computes the five sums pearson correlation needs, three of them degree-2
type Encrypted = (typeof x)[number];
const sum = (values: Encrypted[]) => values.reduce((total, value) => total.add(value));
const encryptedSums = [
sum(x), // sum of x
sum(y), // sum of y
sum(x.map((xi, i) => xi.multiply(y[i]))), // sum of x * y
sum(x.map((xi) => xi.multiply(xi))), // sum of x^2
sum(y.map((yi) => yi.multiply(yi))), // sum of y^2
];
// retailer decrypts the five sums, and computes the correlation
const [sx, sy, sxy, sxx, syy] = encryptedSums.map((c) => Number(retailerCs.decrypt(c)));
const n = adSpend.length;
const r = (n * sxy - sx * sy) / Math.sqrt((n * sxx - sx ** 2) * (n * syy - sy ** 2));
console.assert(r.toFixed(4) === '0.9973');
A correlation of 0.9973 says ad spend and sales move almost in lockstep. As every statistics teacher will remind you, that’s correlation, not causation—but at least the cloud didn’t learn either column to find out.
More Scenarios
- Encrypted similarity search: A company stores the face embeddings of its employees encrypted in the cloud, and the cloud computes squared distances to an encrypted query, a degree-2 function, as we did in encrypted nearest neighbor search.
- Recommendations: A user’s encrypted preference vector and an item’s encrypted feature vector are both stored in the cloud, and their dot product scores the match without revealing either.
- Risk models with interactions: A model uses products of features, such as debt times interest rate, and both features arrive encrypted.
- Outsourced statistics: Variances, covariance matrices and regression sums over encrypted datasets, computed by a cloud that never sees a record.
Caveats
- Exactly one multiplication: Degree 3 and above, such as a product of three encrypted values or a cubic polynomial, are out of reach. For those, look at somewhat or fully homomorphic encryption.
- Ciphertexts grow: Each product adds a pair of ciphertexts. Keep the number of products in a single result moderate, or decrypt partial sums along the way.
- Structure leaks: Pairs reveal which ciphertexts were multiplied together, though not their values.
- Integers only: Scale floats to integers first, and remember that a product of two values scaled by 100 is scaled by 10,000. Results wrap around the plaintext modulus, which matters with small plaintext spaces such as Damgard-Geisler-Kroigaard’s.
Conclusion
Catalano-Fiore is one of those ideas that look obvious once you’ve seen them. Hide each message behind a one-time pad and keep the masked value in the clear, expand the product of two messages, compute the three terms an additive scheme can handle, and postpone the fourth to decryption time, where the private key makes it trivial. The result lifts any additive scheme with a public plaintext space and direct decryption to degree 2, with no new assumptions and no changes to the scheme, at the cost of ciphertexts that grow with every product.
That one extra multiplication unlocks variances, correlations, dot products and distances on encrypted data—in a few lines of Python, Go, Java or TypeScript.
Support this blog financially if you do like!
