Generous Bob

April 12, 2021
Bob and friends

In fact, Alice has quite a few friends. And they have pets too.

Bob wasn't aware of this until recently. He was surprised to hear that they are as secretive about the number of pets as Alice is.

Really? All of them? Yes, all of them. They might be even more paranoid than Alice.

Since Bob is a generous guy and a good friend, he suggested paying for friends' pets' shoes, too.

Wow, really? Alice was stunned. She assured Bob he really doesn't need to. But Bob insisted.

Anyway, it turned out that Alice's friends are total privacy nuts. Not only do they not want to reveal the number of pets they have, they also don't want to reveal how much money each of them has to pay for new shoes every week.

All they are willing to disclose is the amount of money they all collectively need each week. After all, that's all Bob needs, right?

Yeah, that's all Bob needs. And he knows how to make this work too. It's pretty similar to the single-input inner-product scheme he and Alice have been using. It is called a multi-input inner-product scheme. Multi-input meaning inputs from multiple users.

Alice trusted Bob he can make it work. She and her friends just need to encrypt vectors that contain the information about how many shoes they need each week, and send the encrypted vectors to Bob. Let's say

is Alice's vector – the same vector as
in the first version of the system.

Similarly,

is the vector of Friend 1 (insisted to be anonymous). And
is the vector of Friend 2 (insisted to be anonymous too).

sequenceDiagram; participant A as Alice; participant F1 as Friend 1; participant F2 as Friend 2; participant B as Bob; A->>A: encrypts x_a; A->>B: encrypted x_a; F1->>F1: encrypts x_1; F1->>B: encrypted x_1; F2->>F2: encrypts x_2; F2->>B: encrypted x_2;

Let's say:

That means Alice needs 2 pairs for 2 geese, 4 pairs for 2 pigs, and 8 pairs for 4 sheep.

Let's say a pair of shoes for geese costs 150€, a pair of shoes for pigs costs 180€, and a pair of shoes for sheep costs 240€.

That means:

Furthermore, let's say:

This means that Friend 1 needs 4 pairs for 2 cows, 2 pairs for 1 horse, and 2 pairs for 2 chickens.

Let's say a pair of shoes for cows costs 130€, a pair of shoes for horses costs 200€, and a pair of shoes for chickens costs 215€.

That means:

Finally, let's say:

That means Friend 2 needs 2 pairs for 2 crows, 2 pairs for 1 camel, and 2 pairs for 1 lion.

Let's say a pair of shoes for cows costs 190€, a pair of shoes for horses costs 195€, and a pair of shoes for chickens costs 130€.

That means:

Every week Bob has to pay the following amount:

Bob obtains a functional encryption key

for the concatenated vector
each week. He then computes the amount he needs to pay. The important thing is – he doesn't know the individual values
and
Alice and her friends can sleep peacefully.

sequenceDiagram; participant B as Bob; participant K as Key Generator; K->>B: functional encryption key k_y fooooooooooooooooooo; B->>B: computes <x_a, y_a> + <x_1, y_1> + <x_2, y_2>; B->>B: pays the bill;

API

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

Key Generator does the following:

numClients := 3
l := 3
bound := big.NewInt(1024)

damgardMulti, err := fullysec.NewDamgardMultiPrecomp(numClients, l, 2048, bound)
if err != nil {
      t.Fatalf("Failed to initialize multi input inner product: %v", err)
}

secKeys, err := damgardMulti.GenerateMasterKeys()
if err != nil {
      t.Fatalf("Error during keys generation: %v", err)
}

// shoe prices for Alice's pet types
vya := []*big.Int{big.NewInt(150), big.NewInt(180), big.NewInt(240)}
ya := data.NewVector(vya)

// shoe prices for Friend 1 pet types
vy1 := []*big.Int{big.NewInt(130), big.NewInt(200), big.NewInt(215)}
y1 := data.NewVector(vy1)

// shoe prices for Friend 2 pet types
vy2 := []*big.Int{big.NewInt(190), big.NewInt(195), big.NewInt(130)}
y2 := data.NewVector(vy2)

y := data.Matrix{ya, y1, y2}

derivedKey, err := damgardMulti.DeriveKey(secKeys, y)
if err != nil {
      t.Fatalf("Error during key derivation: %v", err)
}

Alice does the following:

client1 := fullysec.NewDamgardMultiClientFromParams(bound, &fullysec.DamgardParams{
      L:     damgardMulti.Params.L,
      Bound: damgardMulti.Params.Bound,
      G:     damgardMulti.Params.G,
      H:     damgardMulti.Params.H,
      P:     damgardMulti.Params.P,
      Q:     damgardMulti.Params.Q,
})

vxa := []*big.Int{big.NewInt(2), big.NewInt(4), big.NewInt(8)}
xa := data.NewVector(vxa)
c1, err := client1.Encrypt(xa, secKeys.Mpk[0], secKeys.Otp[0])
if err != nil {
      t.Fatalf("Error during encryption: %v", err)
}

Friend 1 does the following:

client2 := fullysec.NewDamgardMultiClientFromParams(bound, &fullysec.DamgardParams{
      L:     damgardMulti.Params.L,
      Bound: damgardMulti.Params.Bound,
      G:     damgardMulti.Params.G,
      H:     damgardMulti.Params.H,
      P:     damgardMulti.Params.P,
      Q:     damgardMulti.Params.Q,
})

vx1 := []*big.Int{big.NewInt(4), big.NewInt(2), big.NewInt(2)}
x1 := data.NewVector(vx1)
c2, err := client2.Encrypt(x1, secKeys.Mpk[1], secKeys.Otp[1])
if err != nil {
      t.Fatalf("Error during encryption: %v", err)
}

Friend 2 does the following:

client3 := fullysec.NewDamgardMultiClientFromParams(bound, &fullysec.DamgardParams{
      L:     damgardMulti.Params.L,
      Bound: damgardMulti.Params.Bound,
      G:     damgardMulti.Params.G,
      H:     damgardMulti.Params.H,
      P:     damgardMulti.Params.P,
      Q:     damgardMulti.Params.Q,
})

vx2 := []*big.Int{big.NewInt(2), big.NewInt(2), big.NewInt(2)}
x2 := data.NewVector(vx2)
c3, err := client3.Encrypt(x2, secKeys.Mpk[2], secKeys.Otp[2])
if err != nil {
      t.Fatalf("Error during encryption: %v", err)
}

Bob does the following:

// Bob collects all the ciphertexts
ciphertexts := make([]data.Vector, numClients)
ciphertexts[0] = c1
ciphertexts[1] = c2
ciphertexts[2] = c3

decryptor := fullysec.NewDamgardMultiFromParams(numClients, bound, &fullysec.DamgardParams{
      L:     damgardMulti.Params.L,
      Bound: damgardMulti.Params.Bound,
      G:     damgardMulti.Params.G,
      H:     damgardMulti.Params.H,
      P:     damgardMulti.Params.P,
      Q:     damgardMulti.Params.Q,
})

xy, err := decryptor.Decrypt(ciphertexts, derivedKey, y)
if err != nil {
      t.Fatalf("Error during decryption: %v", err)
}

Private-key or public-key setting?

Bob noticed there is a difference between the single-input inner-product schemes he was using until now and the multi-input inner-product scheme he deployed for Alice and her friends.

Until now Alice was using public key to encrypt her vector containing the number of shoes, but now she and her friends need a private (secret) key to encrypt their vectors.

And there is a good reason for this. Private-key setting is necessary as otherwise Bob could use the public key to encrypt, for example,

and
.

He would now use the ciphertexts of

,
, and
to compute

Similarly, Bob could compute

and
.

Can you imagine Alice's reaction when she would realize Bob is able to compute the price for the shoes individually for her and her friends?

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