Alice and her pets

March 11, 2021
Alice and her pets

Alice loves animals. She adores them. As a matter of fact, she lives with a bunch of animals. She has pigs, sheep, chickens ... well, nobody really knows how many animals Alice has. That's her little secret. In fact, she's quite sensitive about it.

Cryptographers would say Alice possesses a secret vector

that contains the numbers of different pets she has.

For example,

could mean that there are 2 animals of a certain kind (perhaps geese), 2 animals of another kind (perhaps pigs), and 4 animals of a third kind (perhaps sheep).

Now, all of these pets need shoes. Considering the vector

, the number of pairs of shoes could be given by the vector
:

This means that 2 pairs are needed for 2 geese, 4 pairs for 2 pigs, and 8 pairs for 4 sheep.

Unfortunately, these animals walk a lot. In fact, they need new shoes every week. That's a lot of money for Alice.

Luckily, Alice has Bob. Every week, Alice calculates the price (prices change frequently) and informs Bob about it. As soon as Bob knows the price, he pays the bill.

Let's see. The pair of shoes for geese might cost 150€. A pair of shoes for pigs might cost 180€. A pair of shoes for sheep might cost 240€.

sequenceDiagram; participant A as Alice; participant B as Bob; A->>A: price = x_1 * 150 + x_2 * 180 + x_3 * 240; A->>B: send price; B->>B: pays the bill

Now, the price is:

The price is the inner-product of the vectors

and
:

Bob doesn't want to bother Alice week after week by asking her to calculate the price. He knows the price of each particular shoe type (publicly known, of course), but without knowing the required number of pairs of shoes for each type, he cannot calculate the total price.

But Bob knows about functional encryption now. He can compute

having only
and the encryption of
.

Every week:

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

No need to trouble Alice anymore. She just needs to encrypt

once and send it to Bob. From there on, Bob retrieves an FE key
from the Key Generator every week and computes the price.

New shoes are delivered to Alice every week without her having anything to do with it. And the most important thing – Bob still doesn't know how many pets Alice has. What a gentleman!

API

But what is the technology Bob is using behind the scene? How to encrypt the vectors? How to decrypt them? How to generate the keys?

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

Key Generator does the following:

l := 3 // Yeah, this is the number of different pets.

// Parameter bound is the maximum value for the vector x and y coordinates.
// In our scenario both numbers are small - x contains the number
// of pairs of legs for each type of pet, y contains the prices of shoes.
// Thus, bound can be for example set to 300 if we expect no shoes
// will go above that price.

// This parameter is needed due to the decryption phase - if bound
// is big, the decryption process will take more time to finish.
bound := new(big.Int).Exp(big.NewInt(2), big.NewInt(10), nil)

var simpleDDH *simple.DDH
var err error
if param.precomputed {
    // Scheme instantiation is faster if you use precomputed values.
    // Also, it makes it is easier for Alice and Bob. They just use
    // the same precomputed values.
    simpleDDH, err = simple.NewDDHPrecomp(l, 2048, bound)
} else {
    // If you do not trust the precomputed values, use the instantiation
    // below. Note, however, that Alice and Bob must use the same
    // scheme parameters, namely the values G, P, and Q (see ddh.go).
    simpleDDH, err = simple.NewDDH(l, 2048, bound)
}
if err != nil {
    t.Fatalf("Error during simple inner product creation: %v", err)
}

// Be careful - only Key Generator should know masterSecKey.
masterSecKey, masterPubKey, err := simpleDDH.GenerateMasterKeys()
if err != nil {
    t.Fatalf("Error during master key generation: %v", err)
}

// The price for each type (for a pair) of shoes.
vy := []*big.Int{big.NewInt(150), big.NewInt(180), big.NewInt(240)}
y := data.NewVector(vy)

// Key to be given to Bob. Note that it depends on y.
funcKey, err := simpleDDH.DeriveKey(masterSecKey, y)
if err != nil {
    t.Fatalf("Error during key derivation: %v", err)
}

Alice does the following:

// The number of pairs of shoes for each type of pet.
vx := []*big.Int{big.NewInt(2), big.NewInt(4), big.NewInt(8)}
x := data.NewVector(vx)

encryptor, err := simple.NewDDHPrecomp(l, 2048, bound)
if err != nil {
    t.Fatalf("Error during simple inner product creation: %v", err)
}

// Alice sends the ciphertext to Bob.
ciphertext, err := encryptor.Encrypt(x, masterPubKey)
if err != nil {
    t.Fatalf("Error during encryption: %v", err)
}

Bob does the following:

decryptor, err := simple.NewDDHPrecomp(l, 2048, bound)

// funcKey has been obtained from Key Generator.
xy, err := decryptor.Decrypt(ciphertext, funcKey, y)
if err != nil {
    t.Fatalf("Error during decryption: %v", err)
}

Bob now knows the price to be paid. He could also use the C programming language. The API is similar to the one in Go. The scheme is implemented here and the test can be found here.

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