Alice cannot believe

April 8, 2021
Angry Alice

Bob goes one by one. He reads a cryptographic paper, rests, and then reads the next one. He's never in a hurry. However, it is sometimes tempting to try new things immediately.

As you may know, he used one scheme for a while to protect Alice's big secret, and then he switched to another scheme.

And now he realized that it might have been better to study all the schemes first. He realized there are schemes that have a stronger security proof compared to the first one and second one that he used.

Some schemes are only selectively secure. This means that in the security proof, the attacker must specify in advance, before seeing the public parameters, what the challenge ciphertexts will be. Achieving adaptive security (also called full security), on the other hand, where security is guaranteed even for messages that are adaptively chosen at any point in time, is significantly more challenging.

Wait a minute! What are you talking about?

Well, nevermind. It's just that some schemes might be more secure than others.

How to explain that to Alice? She is so sensitive about her secret – she wants to eliminate any possibility of leakage. Bob knows this.

Bob explains it to Alice. He explains that the schemes they're currently using are completely secure, but there are a few others that seem to be even better.

No need to explain the details of their conversation. In a nutshell – after seven milliseconds, Bob agreed to switch to the fully secure scheme. Fortunately, the API is very similar to the API of the second scheme Bob was using.

API

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

Key Generator does the following:

l := 3
n := 64
boundX := big.NewInt(1000) // maximal size of the entry of the message
boundY := big.NewInt(1000) // maximal size of the entry of the other operand

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

fsLWE, err := fullysec.NewLWE(l, n, boundX, boundY)
Z, err := fsLWE.GenerateSecretKey()
U, err := fsLWE.GeneratePublicKey(Z)
zY, err := fsLWE.DeriveKey(y, Z)

Alice does the following:

vx := []*big.Int{big.NewInt(2), big.NewInt(4), big.NewInt(8)}
x := data.NewVector(vx)

encryptor := &fullysec.LWE{
        Params: &fullysec.LWEParams{
            L:       fsLWE.Params.L,
            N:       fsLWE.Params.N,      // Main security parameters of the scheme
            M:       fsLWE.Params.M,      // Number of samples
            BoundX:  fsLWE.Params.BoundX, // Message space size
            BoundY:  fsLWE.Params.BoundY, // Inner-product vector space size
            K:       fsLWE.Params.K,      // Modulus for the resulting inner-product
            Q:       fsLWE.Params.Q,      // Modulus for the ciphertext and keys
            SigmaQ:  fsLWE.Params.SigmaQ, // Standard deviation
            LSigmaQ: fsLWE.Params.LSigmaQ,
            Sigma1:  fsLWE.Params.Sigma1,
            LSigma1: fsLWE.Params.LSigma1,
            Sigma2:  fsLWE.Params.Sigma2,
            LSigma2: fsLWE.Params.LSigma2,
            A:       fsLWE.Params.A,
      },
}

cipher, err := encryptor.Encrypt(x, U)

Bob does the following:

decryptor := &fullysec.LWE{
      Params: &fullysec.LWEParams{
            L:       fsLWE.Params.L,
            N:       fsLWE.Params.N,      // Main security parameters of the scheme
            M:       fsLWE.Params.M,      // Number of samples
            BoundX:  fsLWE.Params.BoundX, // Message space size
            BoundY:  fsLWE.Params.BoundY, // Inner-product vector space size
            K:       fsLWE.Params.K,      // Modulus for the resulting inner-product
            Q:       fsLWE.Params.Q,      // Modulus for the ciphertext and keys
            SigmaQ:  fsLWE.Params.SigmaQ, // Standard deviation
            LSigmaQ: fsLWE.Params.LSigmaQ,
            Sigma1:  fsLWE.Params.Sigma1,
            LSigma1: fsLWE.Params.LSigma1,
            Sigma2:  fsLWE.Params.Sigma2,
            LSigma2: fsLWE.Params.LSigma2,
            A:       fsLWE.Params.A,
      },
}

xyDecrypted, err := decryptor.Decrypt(cipher, zY, y)

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