Does Bob really need functional encryption?

March 26, 2021
Friends with pets

As we have seen, Bob pays for the shoes of Alice's many pets. He doesn't know how many animals Alice has though.

Having encryption of Alice's vector

(which contains the number of different shoes needed) and a functional encryption key
for a publicly known vector
(the price of different shoes), Bob can compute
which is exactly the price he needs to pay.

sequenceDiagram; participant A as Alice; participant B as Bob; participant K as Key Generator; K->>B: functional encryption key k_y fooooooooooooooooooo; A->>A: encrypts health status; A->>B: send ciphertext; B->>B: computes inner-product by using functional encryption key

But Bob now has a better idea. He thinks that the same thing can be achieved with traditional public-key cryptography.

Alice simply needs to encrypt

with Bob's public key. And everything is pretty much the same – the message is encrypted and Bob knows only
, nothing else about
.

sequenceDiagram; participant A as Alice; participant B as Bob; A->>A: encrypts <x, y> with Bob's public key; A->>B: encrypted <x, y>; B->>B: decrypts <x, y> foooooooooooooooooooooooo

But there's a catch. Remember, Bob pays for Alice's pets' shoes each and every week. However, he doesn't have to interact with Alice at all. Alice only has to send the encrypted

once. Bob just has to get a new functional encryption key
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

Getting one key from Key Generator every week might seem pretty much the same as getting one message from Alice every week. And it is. But imagine Alice has hundreds or even thousands of friends. All with pets that need new shoes every week. And Bob would love to pay Alice's friends' bills too.

Now it makes a huge difference whether Bob needs to receive thousands of messages from Alice's friends every week, or just one from Key Generator. With traditional public-key cryptography, each friend would have to send a message (containing encrypted price) to Bob every week.

sequenceDiagram; participant A as Alice; participant F1 as Friend 1; participant F1000 as Friend 1000; participant B as Bob; A->>A: encrypts <x, y> with Bob's public key; A->>B: encrypted <x, y>; B->>B: decrypts <x, y> foooooooooooooooooooooooo; F1->>F1: encrypts <x_1, y> with Bob's public key; F1->>B: encrypted <x_1, y>; B->>B: decrypts <x_1, y> foooooooooooooooooooooooo; F1000->>F1000: encrypts <x_{1000}, y> with Bob's public key; F1000->>B: encrypted <x_{1000}, y>; B->>B: decrypts <x_{1000}, y> foooooooooooooooooooooooo;

Note that the only value that changes is

. With functional encryption, Bob would only need a new functional encryption key from the Key Generator each week.

The vectors

would only need to be sent to Bob once. Smart, right?

sequenceDiagram; participant A as Alice; participant F1 as Friend 1; participant F1000 as Friend 1000; participant B as Bob; participant K as Key Generator; K->>B: functional encryption key k_y fooooooooooooooooooo; B->>B: computes the price; B->>B: computes the price; B->>B: computes the price; B->>B: pays the bill

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