botchains / frodo

practical quantum-secure key encapsulation from generic lattices

Frodo

Practical quantum-secure key encapsulation from generic lattices library.

Abstract. The FrodoKEM schemes are designed to be conservative yet practical post-quantum constructions whose security derives from cautious parameterizations of the well-studied learning with errors problem, which in turn has close connections to conjectured-hard problems on generic, “algebraically unstructured” lattices.

https://frodokem.org/

Progress

• Selected parameter sets;

• Success encode & decode matrices in Zq;

• Success pack & unpack matrices;

• Sampling from the error distribution;

• Pseudorandom matrix generation using SHAKE128, SHAKE256;

• IND-CPA-secure public-key encryption (PKE) scheme (encryption/decryption, key generation);

• IND-CCA-secure key encapsulation mechanism (KEM);

• Written tests.

Math & Implementations

The FrodoPKE scheme from this submission is an instantiation and implementation of the Lindner scheme with some modifications, such as the pseudorandom generation of the public matrix A from a small seed, more balanced key and ciphertext sizes, and new LWE parameters [FKEM]. The security of every public-key cryptosystem depends on the presumed intractability of one or more computational problems. In lattice-based cryptography, the (plain) LWE problem relates to solving a "noisy" linear system modulo a known integer; it can also be interpreted as the problem of decoding a random "unstructured" lattice from a certain class.

Vectors and matrices over the ring. The ring of integers Z for a positive integer q, the quotient ring of integers modulo q is denoted by Zq = Z/qZ.

Realisation of matrices over the ring. Matrix A (m*n) contains unsigned 16-bit numbers in ring of integers modulo q.

Realisation of bit-strings. Bit string s with length len defined like []byte slice with length (len / 8) in little-endian order.

Learning With Errors. The security of PKE and KEM relies on the hardness of the Learning With Errors (LWE) problem. Input instances are chosen at random from a prescribed probability distribution. Some parameterizations of LWE admit (quantum or classical) reductions from worst-case lattice problems. That is, any algorithm that solves n-dimensional LWE (with some non-negligible advantage) can be converted with some polynomial overhead into a (quantum) algorithm that solves certain short-vector problems on any n-dimensional lattice (with high probability). Therefore, if the latter problems have some (quantumly) hard instances, then random instances of LWE are also hard [FKEM].

LWE distribution. Let n,q be positive integers, and let X be a distribution over Z. For an s in (Zq)^n, the LWE distribution A(s,x) is the distribution over (Zq)^n * Zq obtained by choosing a in (Zq)^n uniformly at random and an integer error e in Z from X, and outputting the pair <a, <a, s> + e (mod q)> in (Zq)^n * Zq.

Pseudorandom matrix generation. As NIST currently does not standardize such a primitive, so I choose proposals in [FKEM] to use SHAKE128 & SHAKE256.

List of implementations/packages

👉 FrodoKEM specification papers;

👉 Matrix encoding of bit strings (decoding) frodo;

👉 Deterministic random bit generation & pseudorandom matrix generation using SHAKE128 frodo;

👉 SHAKE128 golang.org/x/crypto/sha3;

👉 Selected parameter sets frodo;

👉 Sampling from the error distribution frodo;

👉 IND-CPA-secure public-key encryption scheme pke;

👉 IND-CCA-secure key encapsulation mechanism kem;

👉 Testing PKE & KEM, unit tests test;

Advantages & Disadvantages of my implementation

😻 Pretty native Golang: using best practices of language;

😴 slower than portable C;

👾 written tests.

Inspiration

💥 microsoft git

💥 microsoft research

How to run

0. install GO if you need and initialise GOPATH

1. open terminal and go to your GOPATH folder

            $ cd ~/go/src

2. get this project and golang.org/x/crypto library

            $ go get "github.com/mariiatuzovska/frodo"
            $ go get "golang.org/x/crypto"

3. run test

	    $ go test 'github.com/mariiatuzovska/frodo'

4. if test ok, use anywhere 😈

Example

Encryption & Decryption

    package main

    import (
        "fmt"
        
        "github.com/mariiatuzovska/frodo"
    )

    func main() {

        frodo := frodo.Frodo976()
        pk, sk := frodo.KeyGen()

        m := []byte("This is my pure frodo976")
        
	ct := frodo.Enc(m, pk)
	pt := frodo.Dec(ct, sk)

	fmt.Println(string(pt))
        
    } 

Encaps & Decaps

    package main

    import (
        "fmt"
        
        "github.com/mariiatuzovska/frodo"
    )

    func main() {

        frodo := frodo.Frodo1344()

	pk, sk := frodo.EncapsKeyGen()
	ct, ss := frodo.Encaps(pk)
	s2 := frodo.Decaps(ct, sk)

	fmt.Printf("%x\n", ss)
        fmt.Printf("%x\n", s2)
    }