Alice is shocked

April 14, 2021
Alice beats Bob

Bob has realized before that Key Generator is a touchy subject.

Key Generator needs to be managed by a trusted party because the administrators of the Key Generator can decrypt all the messages!

And who manages the Key Generator, which Bob uses for his sensitive communication with Alice?

Bob.

Who again?

Bob.

That's the most ridiculous thing Alice has ever heard! Bob?

Well, the thing is, Bob knew this wasn't OK. But the Key Generator was needed, and he saw no other way than to manage it himself. He installed it and launched it. And never touched it again.

Alice had previously been angry at Bob for a lesser problem. So Bob wasn't really going to tell her about the issue with Key Generator. About who was managing it.

But Bob now realized that there was a solution to his problem. There are schemes where the subjects that encrypt data can generate the key shares by themselves. Only a subject that obtains the key shares from all the encryptors can combine them into a functional encryption key. This eliminates the need for a trusted third-party.

Remember, Alice and her friends encrypted the vectors that contained the information about the number of shoes they needed each week.

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;

Since Bob has encrypted vectors, he only needs to collect a functional encryption key each week to calculate the amount of money he needs to pay for the Alice's and her friends' pets' shoes.

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;

Now, the Key Generator could be removed. Alice and her friends could generate the key shares by themselves. Bob would just need to collect the shares and reconstruct them into a key.

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->>A: derives key share k_a; A->>B: k_1 and encrypted x_a; F1->>F1: encrypts x_1; F1->>F1: derives key share k_1; F1->>B: k_2 and encrypted x_1; F2->>F2: encrypts x_2; F2->>F2: derives key share k_2; F2->>B: k_3 and encrypted x_2; B->>B: decrypts fooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo; B->>B: pays the bill;

There would no longer be a need for a Key Generator. Bob could compute the price directly using the key shares and the encrypted vectors. In fact, Bob would gladly upgrade the current system to the version using the scheme that doesn't need a Key Generator. There is a problem though. When new shoes are needed and if the prices for the shoes change, Alice and friends would need to send out new key shares. And that is quite an obstacle! Bob doesn't want Alice to be bothered with sending out the new key shares every week.

But on the other hand, he would eliminate the Key Generator! Bob needs to ask Alice what her preference is.

Bob was so excited about the new option that he completely forgot Alice could become really angry knowing he can actually decrypt all the messages.

And she did go crazy. She was in a state of shock. It was a sad affair. However, afterward, Bob was so desperate that Alice decided to cheer him up and let him upgrade the system to the new scheme.

Alice and her friends now send new key shares to Bob every week and everyone is happy again.

API

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

Alice does the following:

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

// create a (non-decentralized) multi-input scheme as the
// underlying scheme for decentralization
damgardMulti, err := fullysec.NewDamgardMultiPrecomp(numOfClients, l, 2048, bound)
if err != nil {
      t.Fatalf("Error when creating scheme: %v", err)
}

client1, err := fullysec.NewDamgardDecMultiClient(0, damgardMulti)
if err != nil {
      t.Fatalf("Error when creating client: %v", err)
}

pubKeys := make([]*big.Int, numOfClients)
pubKeys[0] = client1.ClientPubKey
// NOTE!!!
/// Here the public keys from the other two clients need to be obtained:
// pubKeys[1] =
// pubKeys[2] =

err = client1.SetShare(pubKeys)
if err != nil {
      t.Fatalf("Error during share generation: %v", err)
}
secKey1, err := client1.GenerateKeys()
if err != nil {
      t.Fatalf("Error during secret keys generation: %v", err)
}

vya := []*big.Int{big.NewInt(150), big.NewInt(180), big.NewInt(240)}
ya := data.NewVector(vya)

vy1 := []*big.Int{big.NewInt(130), big.NewInt(200), big.NewInt(215)}
y1 := data.NewVector(vy1)

vy2 := []*big.Int{big.NewInt(190), big.NewInt(195), big.NewInt(130)}
y2 := data.NewVector(vy2)

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

vx1 := []*big.Int{big.NewInt(2), big.NewInt(4), big.NewInt(8)}
x1 := data.NewVector(vx1)
c1, err := client1.Encrypt(x1, secKey1)
if err != nil {
      t.Fatalf("Error during encryption: %v", err)
}

partKey1, err := client1.DeriveKeyShare(secKey1, y)
if err != nil {
      t.Fatalf("Error during derivation of key: %v", err)
}

Friend 1 does the following:

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

// create a (non-decentralized) multi-input scheme as the
// underlying scheme for decentralization
damgardMulti, err := fullysec.NewDamgardMultiPrecomp(numOfClients, l, 2048, bound)
if err != nil {
      t.Fatalf("Error when creating scheme: %v", err)
}

client2, err := fullysec.NewDamgardDecMultiClient(1, damgardMulti)
if err != nil {
      t.Fatalf("Error when creating client: %v", err)
}

pubKeys := make([]*big.Int, numOfClients)
pubKeys[1] = client2.ClientPubKey
// NOTE!!!
/// Here the public keys from the other two clients need to be obtained:
// pubKeys[0] =
// pubKeys[2] =

err = client2.SetShare(pubKeys)
if err != nil {
      t.Fatalf("Error during share generation: %v", err)
}
secKey2, err := client2.GenerateKeys()
if err != nil {
      t.Fatalf("Error during secret keys generation: %v", err)
}

vya := []*big.Int{big.NewInt(150), big.NewInt(180), big.NewInt(240)}
ya := data.NewVector(vya)

vy1 := []*big.Int{big.NewInt(130), big.NewInt(200), big.NewInt(215)}
y1 := data.NewVector(vy1)

vy2 := []*big.Int{big.NewInt(190), big.NewInt(195), big.NewInt(130)}
y2 := data.NewVector(vy2)

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

vx2 := []*big.Int{big.NewInt(3), big.NewInt(1), big.NewInt(6)}
x2 := data.NewVector(vx2)
c2, err := client2.Encrypt(x2, secKey2)
if err != nil {
      t.Fatalf("Error during encryption: %v", err)
}

partKey2, err := client2.DeriveKeyShare(secKey2, y)
if err != nil {
      t.Fatalf("Error during derivation of key: %v", err)
}

Friend 2 does the following:

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

// create a (non-decentralized) multi-input scheme as the
// underlying scheme for decentralization
damgardMulti, err := fullysec.NewDamgardMultiPrecomp(numOfClients, l, 2048, bound)
if err != nil {
      t.Fatalf("Error when creating scheme: %v", err)
}

client3, err := fullysec.NewDamgardDecMultiClient(2, damgardMulti)
if err != nil {
      t.Fatalf("Error when creating client: %v", err)
}

pubKeys := make([]*big.Int, numOfClients)
pubKeys[2] = client3.ClientPubKey
// NOTE!!!
/// Here the public keys from the other two clients need to be obtained:
// pubKeys[0] =
// pubKeys[1] =

err = client3.SetShare(pubKeys)
if err != nil {
      t.Fatalf("Error during share generation: %v", err)
}
secKey3, err := client3.GenerateKeys()
if err != nil {
      t.Fatalf("Error during secret keys generation: %v", err)
}

vya := []*big.Int{big.NewInt(150), big.NewInt(180), big.NewInt(240)}
ya := data.NewVector(vya)

vy1 := []*big.Int{big.NewInt(130), big.NewInt(200), big.NewInt(215)}
y1 := data.NewVector(vy1)

vy2 := []*big.Int{big.NewInt(190), big.NewInt(195), big.NewInt(130)}
y2 := data.NewVector(vy2)

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

vx3 := []*big.Int{big.NewInt(6), big.NewInt(2), big.NewInt(2)}
x3 := data.NewVector(vx3)
c3, err := client2.Encrypt(x3, secKey3)
if err != nil {
      t.Fatalf("Error during encryption: %v", err)
}

partKey3, err := client3.DeriveKeyShare(secKey3, y)
if err != nil {
      t.Fatalf("Error during derivation of key: %v", err)
}

Bob does the following:

damgardMulti, err := fullysec.NewDamgardMultiPrecomp(numOfClients, l, 2048, bound)
if err != nil {
      t.Fatalf("Error when creating scheme: %v", err)
}
decryptor := fullysec.NewDamgardDecMultiDec(damgardMulti)

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

// Bob collects key parts / shares
partKeys := make([]*fullysec.DamgardDecMultiDerivedKeyPart, numOfClients)
partKeys[0] = partKey1
partKeys[1] = partKey2
partKeys[2] = partKey3

xy, err := decryptor.Decrypt(ciphertexts, partKeys, y)
if err != nil {
      t.Fatalf("Error during decryption: %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