Alice worries about quantum computers

April 7, 2021
Alice and quantum computer

You think Alice doesn't care about cryptography? Well, she does! In a way.

She doesn't exactly care about cryptography, but she's definitely concerned about not revealing the number of her pets.

Remember, Alice doesn't want to reveal the vector

which contains the number of shoes needed for her pets. She encrypted
once and sent it to Bob.

sequenceDiagram; participant A as Alice; participant B as Bob; A->>A: encrypts x; A->>B: sends encrypted x;

Each week, Bob receives a functional encryption key

for vector
. He can thus compute
which is exactly the price he has to pay for the shoes.

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

The whole story went well for a couple of weeks. But Alice was starting to get a little worried. Can she really trust this strange technology Bob is using to hide the number of her pets? It is called cryptography, right?

She still vividly remembers the cryptographer who turned Bob into a cryptography fanatic. He didn't look entirely sane. Of course, everyone knows what ROFL means. It's "Rolling On Floor Laughing". But does anyone literally do that? Besides cryptographers when they meet Alice and Bob?

And now she is using the technology that this guy and his friends developed. Is she crazy?

No, she's not. At least that's what Bob says. She should trust the software library they're using to protect the privacy of her animals. But then again – Alice took a look at it and she found it confusing. What are all these different schemes? Come on, what is a scheme anyway?

Bob knows what a scheme is. He had an idea why there are different schemes that do pretty much the same thing, too. Different schemes are based on different hard mathematical problems.

Well, you know, Alice couldn't care less. And she's right. Who cares which mathematical problem makes the scheme secure? Alice just wants it to be secure.

At some point, Bob mentioned one thing that seemed important to Alice. There are schemes that are believed to be secure even in the post-quantum age.

And Alice immediately asked if they were using such a scheme. Well, not really, Bob said. But they could switch to it.

They switched to it straight away. Bob switched from Decisional Diffie-Hellman (DDH) based scheme to the Learning With Errors (LWE) based scheme.

You know, LWE is based on lattices, and many fundamental lattice problems are thought to be hard even against a quantum computer. But these are the details nobody cares about. Well, at least Alice doesn't. It just needs to be secure.

API

The post-quantum secure 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 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.

bound := new(big.Int).Exp(big.NewInt(2), big.NewInt(10), nil)
n := 128 // the main security parameter of the scheme

simpleLWE, err := simple.NewLWE(l, bound, bound, n)

SK, err := simpleLWE.GenerateSecretKey()
PK, err := simpleLWE.GeneratePublicKey(SK)

// 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 := simpleLWE.DeriveKey(y, SK)

Alice does the following:

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

// The same parameters need to be used as for the KeyGenerator.
// We assume here simpleLWE.Params are the parameters used
// by the KeyGenerator.
encryptor := &simple.LWE{
      Params: &simple.LWEParams{
            L:      simpleLWE.Params.L,
            BoundX: simpleLWE.Params.BoundX,
            BoundY: simpleLWE.Params.BoundY,
            N:      simpleLWE.Params.N,
            M:      simpleLWE.Params.M,
            P:      simpleLWE.Params.P,
            Q:      simpleLWE.Params.Q,
            A:      simpleLWE.Params.A,
            SigmaQ: simpleLWE.Params.SigmaQ,
            LSigma: simpleLWE.Params.LSigma,
      },
}

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

Bob does the following:

decryptor := &simple.LWE{
      Params: &simple.LWEParams{
            L:      simpleLWE.Params.L,
            BoundX: simpleLWE.Params.BoundX,
            BoundY: simpleLWE.Params.BoundY,
            N:      simpleLWE.Params.N,
            M:      simpleLWE.Params.M,
            P:      simpleLWE.Params.P,
            Q:      simpleLWE.Params.Q,
            A:      simpleLWE.Params.A,
            SigmaQ: simpleLWE.Params.SigmaQ,
            LSigma: simpleLWE.Params.LSigma,
      },
}

// funcKey has been obtained from Key Generator.
xy, err := decryptor.Decrypt(ciphertext, funcKey, 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