House full of pets

April 13, 2021
Alice in the house

It's a little surprising that Bob has never been to Alice's house. But just imagine – if Bob were in the house, he would see what kind and how many pets Alice has. And Alice doesn't want Bob to know that.

Bob does know, however, that there are some animals, and when animals live in the house, you usually have to clean up a little here and there. He has been increasingly concerned about the cleanliness of Alice's house.

He shouldn't worry, Alice assured him, she calls a cleaning service here and there. Once a month, actually.

Now Bob was a little disappointed. So the guys from the cleaning service can see Alice's pets?

No, not really. Alice always hides them long before the service van arrives in front of the house.

Bob has forgotten that he was ever disappointed. Of course – he will pay for the cleaning service from now on, too!

He did start paying for cleaning service. The cost of cleaning service depends on the square meters. However, different rooms require different effort to clean the mess. Just imagine a lion in one room and a sparrow in another. It may not be totally the same.

Yes, Alice could just let him know the amount every month, but Bob doesn't want to bother Alice each and every month.

Alice's house has nine rooms. She let Bob know that. But the size of the rooms must remain a secret. Top secret.

Thus, Bob introduced the variables to denote the width and length of each room:


The areas of the rooms are:

, and

The cleaning cost for a square meter in a room indexed by

(with area
) is

The total cleaning costs are:

So, let's say Alice encrypts her two vectors

representing the dimensions of the rooms. Using functional encryption for quadratic polynomials, Bob can decrypt
, given that he obtained the functional encryption key for the values

Yeah, Alice just needs to send the encrypted vectors

to Bob once. Bob then obtains the functional encryption key for the values
each month to be able to compute the amount he has to pay for the cleaning service.

sequenceDiagram; participant A as Alice; participant B as Bob; participant K as Key Generator; K->>B: functional encryption key k_y fooooooooooooooooooo; B->>B: computes inner-product by using; B->>B: pays the bill

Of course, Bob could also use the inner-product scheme: he would just have to ask Alice to encrypt the vector

. But there's a catch! Note that the vector
contains 9 values as opposed to the 3 + 3 values in the vectors

Imagine one day Bob starts paying for the cleaning service for some Alice's friend. And this friend has a house with 12 x 12 = 144 rooms (Alice's friends are strange and might have strange houses too).

Using a quadratic scheme, Alice's friend would need to encrypt 24 = 12 + 12 values. Using the inner-product scheme, the poor friend would have to encrypt 144 values. This can quickly get out of hands!


The quadratic polynomial scheme used below is implemented here and the test can be found here.

Key Generator does the following:

bound := big.NewInt(100)
n := 3

// The price for a square meter for each of the rooms:
// 100, 120, 130, 85, 110, 70, 95, 75, 50.

vf1 := []*big.Int{big.NewInt(100), big.NewInt(120), big.NewInt(130)}
f1 := data.NewVector(vf1)

vf2 := []*big.Int{big.NewInt(85), big.NewInt(110), big.NewInt(70)}
f2 := data.NewVector(vf2)

vf3 := []*big.Int{big.NewInt(95), big.NewInt(75), big.NewInt(50)}
f3 := data.NewVector(vf3)

f := data.Matrix{f1, f2, f3}

q := quadratic.NewSGP(n, bound)
msk, err := q.GenerateMasterKey()
if err != nil {
    t.Fatalf("error when generating master keys: %v", err)

feKey, err := q.DeriveKey(msk, f)
if err != nil {
    t.Fatalf("error when deriving key: %v", err)

Alice does the following:

q := quadratic.NewSGP(n, bound)

// The dimensions:
// x1 = 3, x2 = 5, x3 = 4
// y1 = 6, y2 = 4, y3 = 5

vx := []*big.Int{big.NewInt(3), big.NewInt(5), big.NewInt(4)}
x := data.NewVector(vx)

vy := []*big.Int{big.NewInt(6), big.NewInt(4), big.NewInt(5)}
y := data.NewVector(vy)

c, err := q.Encrypt(x, y, msk)
if err != nil {
    t.Fatalf("error when encrypting: %v", err)

Bob does the following:

// Bob obtains ciphertext c and
// functional encryption key feKey
dec, err := q.Decrypt(c, feKey, f)
if err != nil {
    t.Fatalf("error when decrypting: %v", err)

The Alice and Bob newsletter

Get highlights of Alice and Bob's adventures delivered to your email box.

Made by XLAB with ❤️
Follow us
Twitter Twitter