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.
-
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.
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.
👉 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
;
😻 Pretty native Golang: using best practices of language;
😴 slower than portable C;
👾 written tests.
-
install GO if you need and initialise GOPATH
-
open terminal and go to your GOPATH folder
$ cd ~/go/src
- get this project and golang.org/x/crypto library
$ go get "github.com/mariiatuzovska/frodo"
$ go get "golang.org/x/crypto"
- run test
$ go test 'github.com/mariiatuzovska/frodo'
- if test ok, use anywhere 😈
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))
}
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)
}