SABER: Learning with Rounding … For Post-Quantum Crypto, It’s All About Lattice

SABER: Learning with Rounding … For Post-Quantum Crypto, It’s All About Lattice

NIST is now finalising the post-quantum cryptography competition. Overall the methods we can use to replace our existing public key methods are:

Hash-based/symmetric-based. This includes Merkle signatures, SPHINCS and Picnic, and are used to create digital signatures. They cannot be used for public-key encryption and involve creating a range of private/public key pairs, and which are only used once. We must keep a track of the key pairs that we have used, in order to not use the again.
Code-based. This includes McEliece and Niederreiter, and have been studied for decades.
Multivariate. This involves multivariate quadratic methods. An example of this is the oil-and-vinegar method [here].
Lattice-based. This includes NTRU (Nth degree TRUncated polynomial ring), learning with errors (LWE), Ring LWE, and Learning with Rounding. These have some of the best attributes for creating digital signatures, key exchange and encryption, and with reasonably small encryption keys and ciphertext sizes.
Isogenies. This includes Supersinglar elliptic curve isogenies. These are interesting but are rather slow at the current time.

For Public-Key Encryption and KEMs (Key Exchange), NIST has the following as finalists:

Classic McEliece. This has been around for around 40 years and has been shown to be fairly resistant to attack. It produces a fairly long encryption key but produces a fairly small amount of ciphertext.
CRYSTALS-KYBER (Lattice). Uses LWE (Learning with Errors) with lattice methods. A new lattice attack was discovered within the period of the assessment, but it is hoped that an updated version of KYBER can be produced for the final assessment. NIST have some worries about its side-channel robustness and is a strong contender for KEM.
NTRU (Lattice). This is a traditional structured lattice-based approach, and has been around for longer than the other lattice methods — showing that it is perhaps more robust against attack and against intellectual property claims.
SABER (Lattice). This is based on modular learning with rounding, and uses lattice methods. SABER has excellent performance and is possibly near production-ready. NIST’s only recommendation is that updates should perhaps consider side-channel attacks.

and for digital signatures:

CRYSTALS-DILITHIUM (Lattice).
FALCON (Lattice).
Rainbow (Oil and Vinegar).

SABER

So, let’s look at one of the finalists: SABER. It uses Learning with Rounding (LWR), and which is based on learning with errors (LWE) where random errors are replaced with deterministic rounding. It was created by Banerjee, Peikert and Rosen [1] at EUROCRYPT 2012.

Learning With Errors was defined by Oded Regev in 2005 [here]. First, we select a random series of values for our public key (A). For example, let’s select 20 random values from 0 to 100:

[80, 86, 19, 62, 2, 83, 25, 47, 20, 58, 45, 15, 30, 68, 4, 13, 8, 6, 42, 92]

Next we create a list (B) and where the elements are B_i=A_i s+e_i (mod q), and where s is a secret value, and e is a list of small random values (the error values). If we take a prime number (q) of 97, and an error array (e) of:

[3, 3, 4, 1, 3, 3, 4, 4, 1, 4, 3, 3, 2, 2, 3, 2, 4, 4, 1, 3]

we generate a list (B) of:

[15, 45, 2, 20, 13, 30, 32, 45, 4, 3, 34, 78, 55, 51, 23, 67, 44, 34, 17, 75]

The A and B list will be our public key, and s will be our secret key. We can now distribute A and B to anyone who wants to encrypt a message for us (but keep s secret). To encrypt we take samples from the A and B lists, and take a message bit (M), and then calculate two values:

u=∑(A_samples)(mod q)

v=∑(B_samples)+q/2 M(mod q)

The encrypted message is (u,v). To decrypt, we calculate:

Dec=v−su (mod q)

If Dec is less than q/2, the message is a zero, else it is a 1 [here]. While LWE uses:

B=A . s+e

and where B and A are the public keys, s is the secret key, and e is the error array.

within LWR the noise is removed (B=A . s) and where we round down the elements with a smaller sampling size than the prime number. This makes the problem as hard as LWE.

Let’s implement a KEM with SABER, and which allows a symmetric key to be passed using public-key methods. In this case, Alice will generate her key pair of a public key (pk) and a private key (sk). She then passes her public key to Bob, and then Bob creates a ciphertext (ct) with Alice’s public key. He passes the ciphertext to Alice, and who decrypts with her private key. This will reveal the key that Bob wants Alice to use.

The following is the code [here]:

#include stddef.h
#include stdio.h
#include string.h
#include stdlib.h
#include stdint.h
#include "kem.h"
#include "randombytes.h"
#include "SABER_params.h"

#define CRYPTO_PUBLICKEYBYTES SABER_PUBLICKEYBYTES

#define CRYPTO_SECRETKEYBYTES (SABER_SECRETKEYBYTES)
#define CRYPTO_CIPHERTEXTBYTES SABER_BYTES_CCA_DEC
#define CRYPTO_BYTES SABER_KEYBYTES

char *showhex(uint8_t a[], int size) ;

char *showhex(uint8_t a[], int size) {


    char *s = malloc(size * 2 + 1);

    for (int i = 0; i < size; i++)
        sprintf(s + i * 2, "%02x", a[i]);

    return(s);
}



int main(void)
{
  uint8_t pk[CRYPTO_PUBLICKEYBYTES];
  uint8_t sk[CRYPTO_SECRETKEYBYTES];
  uint8_t ct[CRYPTO_CIPHERTEXTBYTES];
  uint8_t key_a[CRYPTO_BYTES];
  uint8_t key_b[CRYPTO_BYTES];
  int rtn;

  printf("SABER");    
  printf("\nPublic key size: %d\nSecret key size: %d\nCiphertext  size: %d\n",CRYPTO_PUBLICKEYBYTES,CRYPTO_SECRETKEYBYTES,CRYPTO_BYTES);
  //Alice generates a public key
  crypto_kem_keypair(pk, sk);
  //Bob derives a secret key and creates a response
  crypto_kem_enc(ct, key_b, pk);

  //Alice uses Bobs response to get her shared key
  crypto_kem_dec(key_a, ct, sk);


  printf("\nPublic key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/8));
  printf("Secret key (only showing 1/8 of key): %s\n",showhex(sk,CRYPTO_SECRETKEYBYTES/8));
  printf("Cipher text: %s\n",showhex(ct,CRYPTO_CIPHERTEXTBYTES/8));

  printf("\nKey (A): %s\n",showhex(key_a,CRYPTO_BYTES));  
  printf("Key (B): %s\n",showhex(key_b,CRYPTO_BYTES));



  rtn=memcmp(key_a, key_b, CRYPTO_BYTES);

  if (rtn==0) { printf("Keys are the same");}
  else printf("Error in the keys!");
  

  return 0;
}

A sample run of Kyber512 shows that the public key size is 800 bytes, the secret key is 1,632 bytes, and the ciphertext size is 32 bytes [here]:

SABER
Public key size: 672
Secret key size: 1568
Ciphertext  size: 32

Public key (only showing 1/8 of key): 5998968e0ddae8c0c910b7625e3960ad74ac56585083934963c8934bff920076e1b73ff7acb02fe904fe5fbe463c7691f0d2ee069a3d090a933d4d44adbbb5e8e09d3bcbc4637f71289e8ef9d92a5b73643139fc
Secret key (only showing 1/8 of key): 022000008000d0ff0140ffffff032000fc7fffffff0100000000ff3f0004000120000440ffffff024000000000f0ff030000f0ffff3f000400000000feff001000ff3f000080ff0f000040ff070000c0ff0300ff3f00fe7fffffffff3f000880001000febfff17000220000800014000feffff0f00012000fc7f000000fabfff0f00022000f47f00d0fffd7f00100001e0fff7ff00000000c0ff1f000140000400001000fabf000800006000f47f01f0fffd3f00f8fffe1f00fc7f00000004c000000002
Cipher text: 8b7a3eb9a2358fddbd1364bd3472c3dd8952debbdb6a94329e468769fae9e7dfa2be550e64628b8225f2b390e7d559fd9539347f752371724276fbb59b2ed1458655aee46362166b5057f28455b54f0e01ac59c184c6b7a8bfb1bec3

Key (A): c0164eb4ffa98abf2e927e6d47a14b2fc10bc8bb5a2e22271a0bb3213b967e79
Key (B): c0164eb4ffa98abf2e927e6d47a14b2fc10bc8bb5a2e22271a0bb3213b967e79
Keys are the same

Conclusions

In an era of quantum computers, we will be saying goodbye to RSA and ECC, and hello to lattice methods. This could be NTRU, Learning With Errors (LWE) and Learning With Rounding (LWR).

References

[1] Banerjee, A., Peikert, C., & Rosen, A. (2012, April). Pseudorandom functions and lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 719–737). Springer, Berlin, Heidelberg.