Post-quantum cryptography
This section describes implementations of cryptographic schemes that are believed to be secure against attacks by quantum computers: the multivariate signature scheme UOV, the lattice-based encryption scheme LWE and several hash-based signature schemes. They are meant for experiments and teaching. The implementations are neither constant-time nor hardened against side channels and must not be used to protect real data.
The common interface
All schemes use the same functions, which dispatch on the parameter object p of the scheme, the first argument:
keygen(p)returns a key pair(pk, sk),sign(p, msg, sk)signs a message andverify(p, sig, msg, pk)checks a signature (signature schemes),open(p, sm, pk)returns the message of a signed messagesm(a message followed by its signature) ornothing,encrypt(p, pk, msg)anddecrypt(p, sk, ct)(encryption schemes).
Parameter sets are created with instantiate_uov, instantiate_lwe and instantiate_hbs, or taken from the predefined ones such as uov_1p, lwe_toy or hbs_mss_toy.
UOV signatures
The Unbalanced Oil and Vinegar signature scheme with the parameter sets of the NIST submission, see [BCDGKPPS.EA25].
instantiate_uov — Function
instantiate_uov(gf::Int, n::Int, m::Int, pkc::Bool, skc::Bool,
name::String) -> UOVCreate a UOV parameter set over $\mathrm{GF}(gf)$ with $n$ variables and $m$ equations. The parameters must satisfy the following restrictions:
gfis16or256;m > 0andn >= 2m, so that the number of univariate variablesv = n - mis at leastm;- if
gf == 16, thennandmare even.
The Boolean flags pkc and skc switch on public-key and secret-key compression, respectively, and name labels the parameter set. The predefined sets uov_1p, uov_1s, uov_3, uov_5 (and their _pkc and _pkc_skc variants) are created this way.
Examples
julia> u = instantiate_uov(256, 112, 44, false, false, "my-uov"); (u.n, u.m, u.v)
(112, 44, 68)
julia> instantiate_uov(4, 10, 3, false, false, "bad")
ERROR: ArgumentError: gf must be 16 or 256, got 4
[...]This function is part of the experimental code in Oscar. Please read here for more details.
keygen — Method
keygen(uov::UOV) -> (pk, sk)Generate a public/private key pair for the UOV parameter set uov, returning the public key pk first and the secret key sk second. Both are byte vectors whose layout depends on the pkc and skc flags of uov.
Examples
julia> uov = uov_1p;
julia> pk, sk = keygen(uov);
julia> length(pk)
278432
julia> length(sk)
237896This function is part of the experimental code in Oscar. Please read here for more details.
sign — Method
sign(uov::UOV, msg::Vector{UInt8}, sk::Vector{UInt8}) -> sigSign the message msg (a byte vector) with the secret key sk of the UOV parameter set uov, returning the signature as a byte vector.
Examples
julia> uov = uov_1p;
julia> pk, sk = keygen(uov);
julia> msg = zeros(UInt8, 32);
julia> sig = sign(uov, msg, sk);
julia> verify(uov, sig, msg, pk)
trueThis function is part of the experimental code in Oscar. Please read here for more details.
verify — Method
verify(uov::UOV, sig::Vector{UInt8}, msg::Vector{UInt8}, pk::Vector{UInt8}) -> BoolReturn true if the signature sig is a valid signature of the message msg under the public key pk of the UOV parameter set uov.
Examples
julia> uov = uov_1p;
julia> pk, sk = keygen(uov);
julia> msg = zeros(UInt8, 32);
julia> sig = sign(uov, msg, sk);
julia> verify(uov, sig, msg, pk)
true
julia> sig_bad = copy(sig);
julia> sig_bad[1] ⊻= 0xff;
julia> verify(uov, sig_bad, msg, pk)
falseThis function is part of the experimental code in Oscar. Please read here for more details.
open — Method
open(uov::UOV, sm::Vector{UInt8}, pk::Vector{UInt8})Recover the message from a signed message sm (message concatenated with its signature), verifying it against the public key pk. Returns nothing if the signature is invalid.
Examples
julia> uov = uov_1p;
julia> pk, sk = keygen(uov);
julia> msg = UInt8[1, 2, 3];
julia> sm = vcat(msg, sign(uov, msg, sk));
julia> open(uov, sm, pk)
3-element Vector{UInt8}:
0x01
0x02
0x03Learning with errors
Public key encryption based on the learning with errors problem, see [Reg05].
instantiate_lwe — Function
instantiate_lwe(n::Int, m::Int, q::Int, eta::Int, name::String) -> LWECreate a parameter set for Regev's LWE encryption scheme with secret dimension $n$, $m$ samples, modulus $q$ and noise drawn from the centered binomial distribution with parameter $\eta$ (with values in $[-\eta, \eta]$). The parameters must satisfy the following restrictions:
n,m,etaare positive;q >= 8;- the worst-case decryption noise
m * etais less thanq / 4, so that decryption is always correct.
The label name is only used for printing. The predefined sets lwe_toy, lwe_light and lwe_standard are created this way.
Examples
julia> p = instantiate_lwe(16, 32, 1031, 2, "my-lwe")
LWE parameters my-lwe (n = 16, m = 32, q = 1031, eta = 2)
julia> instantiate_lwe(16, 32, 100, 2, "bad")
ERROR: ArgumentError: worst-case noise m*eta = 64 must be less than q/4 = 25.0
[...]This function is part of the experimental code in Oscar. Please read here for more details.
keygen — Method
keygen(p::LWE; rng::AbstractRNG = RandomDevice()) -> Tuple{Tuple{Matrix{Int}, Vector{Int}}, Vector{Int}}Generate a key pair for the LWE parameters p. The public key is a pair (A, b) where A is a uniformly random $m \times n$ matrix modulo $q$ and $b = As + e \bmod q$ for a secret vector s and a small noise vector e. The secret key is s. Return (pk, sk).
Examples
julia> (A, b), s = keygen(lwe_toy);
julia> size(A), length(b), length(s)
((32, 16), 32, 16)This function is part of the experimental code in Oscar. Please read here for more details.
encrypt — Method
encrypt(p::LWE, pk, msg::AbstractVector{UInt8}; rng::AbstractRNG = RandomDevice()) -> Tuple{Matrix{Int}, Vector{Int}}Encrypt the bytes msg under the public key pk bit by bit. For each bit $\mu$ a random $r \in \{0,1\}^m$ is chosen and the pair $(A^T r, b^T r + \mu \lfloor q/2 \rfloor)$ modulo $q$ is formed. The ciphertext (U, v) consists of the matrix U with the vectors $A^T r$ as columns and the vector v of the second components.
Examples
julia> pk, sk = keygen(lwe_toy);
julia> U, v = encrypt(lwe_toy, pk, UInt8[1, 2, 3]);
julia> size(U), length(v)
((16, 24), 24)This function is part of the experimental code in Oscar. Please read here for more details.
decrypt — Method
decrypt(p::LWE, sk, ct) -> Vector{UInt8}Decrypt the ciphertext ct = (U, v) with the secret key sk. A bit is decoded as $1$ if $v_i - s^T U_i \bmod q$ is closer to $\lfloor q/2 \rfloor$ than to $0$. Since the noise is bounded by $m \eta < q/4$ for all parameter sets created by instantiate_lwe, decryption is always correct.
Examples
julia> pk, sk = keygen(lwe_toy);
julia> ct = encrypt(lwe_toy, pk, Vector{UInt8}("oscar"));
julia> String(decrypt(lwe_toy, sk, ct))
"oscar"This function is part of the experimental code in Oscar. Please read here for more details.
Hash-based signatures
Signature schemes whose security rests on the properties of a hash function only (here SHAKE256): the one-time signatures of Lamport [Lam79] and Winternitz (WOTS+, [Hls13]), Merkle trees [Mer90], the few-time signatures HORST and FORS, and their combination into signature schemes with a single Merkle tree or with a hypertree in the style of SPHINCS [BHHLNPSS.EA15] and SPHINCS+ [BHKNRS19]. The parameter sets are not compatible with the NIST standard FIPS 205.
Signatures
instantiate_hbs — Function
instantiate_hbs(n::Int, w::Int, h::Int, name::String; d::Int = 1, fts::Symbol = :none, tau::Int = 0, k::Int = 0, x::Int = 0) -> HBSCreate a parameter set for a hash-based signature scheme with hashes of n bytes and Winternitz parameter w. There are two kinds of schemes:
- With
fts = :none(the default) the scheme uses a single Merkle tree of heighth, whose leaves are the public keys of $2^h$ Winternitz keys. It can sign $2^h$ messages and is stateful: signing changes the secret key. - With
fts = :horstorfts = :forsthe scheme uses a hypertree of total heighthwithdlayers of Merkle trees, so that $2^h$ few-time keys can sign. A message is signed by a few-time key chosen by its digest, which is then certified by the layers of the hypertree. For HORST,tauis the height of the tree,kthe number of revealed values andxthe number of top levels of the tree that are part of the signature. For FORS, there arektrees of heighttau, andxis not used. The scheme is stateless.
The parameters must satisfy the following restrictions:
n >= 1andwis a power of two between 2 and 256;h >= 1andddividesh; forfts = :none, we needd = 1andh <= 24;- for
fts != :none,tau,k >= 1,tau <= 24, and for HORST0 <= x <= tau.
The label name is only used for printing. The predefined sets hbs_mss_toy, hbs_mss_light, hbs_horst_toy, hbs_horst_light, hbs_fors_toy, hbs_fors_light and hbs_fors_standard are created this way.
Examples
julia> instantiate_hbs(16, 16, 10, "my-mss")
Hash-based signature parameters my-mss (mss, n = 16, w = 16, h = 10)
julia> instantiate_hbs(16, 16, 12, "my-fors"; d = 3, fts = :fors, tau = 8, k = 16)
Hash-based signature parameters my-fors (hypertree, fors, n = 16, w = 16, h = 12, d = 3)
julia> instantiate_hbs(16, 15, 10, "bad")
ERROR: ArgumentError: w must be a power of two between 2 and 256, got 15
[...]This function is part of the experimental code in Oscar. Please read here for more details.
keygen — Method
keygen(p::HBS; rng::AbstractRNG = RandomDevice()) -> Tuple{Vector{UInt8}, Vector{UInt8}}Generate a key pair for the parameter set p, returning the public key pk first and the secret key sk second. Both are byte vectors of the lengths p.pk_sz and p.sk_sz. For a scheme with a single Merkle tree this computes the public keys of all $2^h$ Winternitz keys, for the schemes with a hypertree only those of the single tree in the top layer.
Examples
julia> pk, sk = keygen(hbs_mss_toy);
julia> length(pk), length(sk)
(16, 40)
julia> pk, sk = keygen(hbs_fors_toy);
julia> length(pk), length(sk)
(16, 32)This function is part of the experimental code in Oscar. Please read here for more details.
sign — Method
sign(p::HBS, msg::Vector{UInt8}, sk::Vector{UInt8}) -> Vector{UInt8}Sign the message msg with the secret key sk of the parameter set p, returning the signature, a byte vector of length p.sig_sz.
For a scheme with a single Merkle tree (p.scheme == :mss) the scheme is stateful: the counter at the end of sk is increased in place, and at most $2^h$ messages can be signed with a key. Signing then needs to rebuild the whole tree, which makes it as expensive as the key generation. The schemes with a hypertree are stateless, but the few-time keys at the bottom lose security if the number of signatures comes near to $2^h$.
Examples
julia> pk, sk = keygen(hbs_mss_toy);
julia> sig = sign(hbs_mss_toy, UInt8[1, 2, 3], sk);
julia> length(sig) == hbs_mss_toy.sig_sz
true
julia> verify(hbs_mss_toy, sig, UInt8[1, 2, 3], pk)
trueThis function is part of the experimental code in Oscar. Please read here for more details.
verify — Method
verify(p::HBS, sig::Vector{UInt8}, msg::Vector{UInt8}, pk::Vector{UInt8}) -> BoolReturn true if sig is a valid signature of the message msg under the public key pk of the parameter set p.
Examples
julia> pk, sk = keygen(hbs_fors_toy);
julia> msg = Vector{UInt8}("oscar");
julia> sig = sign(hbs_fors_toy, msg, sk);
julia> verify(hbs_fors_toy, sig, msg, pk)
true
julia> verify(hbs_fors_toy, sig, Vector{UInt8}("Oscar"), pk)
falseThis function is part of the experimental code in Oscar. Please read here for more details.
open — Method
open(p::HBS, sm::Vector{UInt8}, pk::Vector{UInt8})Recover the message from a signed message sm (the message followed by its signature), verifying it against the public key pk. Returns nothing if the signature is invalid.
Examples
julia> pk, sk = keygen(hbs_fors_toy);
julia> msg = UInt8[1, 2, 3];
julia> sm = vcat(msg, sign(hbs_fors_toy, msg, sk));
julia> open(hbs_fors_toy, sm, pk)
3-element Vector{UInt8}:
0x01
0x02
0x03One-time signatures
lamport_keygen — Function
lamport_keygen(n::Int = 16; rng::AbstractRNG = RandomDevice()) -> Tuple{Vector{UInt8}, Vector{UInt8}}Generate a key pair of Lamport's one-time signature scheme with hash length n bytes. The secret key consists of $2 \cdot 8n$ random strings of n bytes, the public key consists of their hashes, both stored as one byte vector. Return (pk, sk). A key pair must be used for one signature only.
Examples
julia> pk, sk = lamport_keygen(4);
julia> length(pk), length(sk)
(256, 256)This function is part of the experimental code in Oscar. Please read here for more details.
lamport_sign — Function
lamport_sign(n::Int, msg::Vector{UInt8}, sk::Vector{UInt8}) -> Vector{UInt8}Sign msg with the secret key sk. For the $i$-th bit $b_i$ of the hash of msg the string number $2i + b_i$ of the secret key is revealed, so the signature has $8n \cdot n$ bytes.
Examples
julia> pk, sk = lamport_keygen(4);
julia> length(lamport_sign(4, UInt8[1, 2, 3], sk))
128This function is part of the experimental code in Oscar. Please read here for more details.
lamport_verify — Function
lamport_verify(n::Int, sig::Vector{UInt8}, msg::Vector{UInt8}, pk::Vector{UInt8}) -> BoolReturn true if sig is a valid Lamport signature of msg for the public key pk, that is, if the hash of each revealed string is the matching entry of pk.
Examples
julia> pk, sk = lamport_keygen(4);
julia> sig = lamport_sign(4, UInt8[1, 2, 3], sk);
julia> lamport_verify(4, sig, UInt8[1, 2, 3], pk)
true
julia> lamport_verify(4, sig, UInt8[1, 2, 4], pk)
falseThis function is part of the experimental code in Oscar. Please read here for more details.
Merkle trees
merkle_tree — Function
merkle_tree(leaves::Vector{Vector{UInt8}}; node = ...) -> Vector{Vector{Vector{UInt8}}}Build the Merkle tree over leaves, whose number must be a power of two. The result is the vector of the levels of the tree, starting with the leaves and ending with the level that contains only the root. A node is the hash of its two children, computed by node(height, index, left, right); by default this is the first n bytes of SHAKE256 applied to the concatenation, where n is the length of left.
Examples
julia> leaves = [UInt8[i] for i in 1:4];
julia> levels = merkle_tree(leaves);
julia> length.(levels)
3-element Vector{Int64}:
4
2
1
julia> merkle_root(levels) == merkle_root(merkle_tree(leaves))
trueThis function is part of the experimental code in Oscar. Please read here for more details.
merkle_root — Function
merkle_root(levels::Vector{Vector{Vector{UInt8}}}) -> Vector{UInt8}Return the root of the Merkle tree levels created by merkle_tree.
This function is part of the experimental code in Oscar. Please read here for more details.
merkle_auth_path — Function
merkle_auth_path(levels::Vector{Vector{Vector{UInt8}}}, index::Int) -> Vector{Vector{UInt8}}Return the authentication path of the leaf with the zero-based position index in the Merkle tree levels. It consists of the siblings of the nodes on the way from the leaf to the root, starting at the leaf.
Examples
julia> levels = merkle_tree([UInt8[i] for i in 1:8]);
julia> length(merkle_auth_path(levels, 5))
3This function is part of the experimental code in Oscar. Please read here for more details.
merkle_verify — Function
merkle_verify(root::Vector{UInt8}, leaf::Vector{UInt8}, index::Int, path::Vector{Vector{UInt8}}; node = ...) -> BoolReturn true if path is the authentication path of leaf at the zero-based position index in the Merkle tree with the given root. The function node must be the one used to build the tree.
Examples
julia> levels = merkle_tree([UInt8[i] for i in 1:8]);
julia> path = merkle_auth_path(levels, 5);
julia> merkle_verify(merkle_root(levels), UInt8[6], 5, path)
true
julia> merkle_verify(merkle_root(levels), UInt8[6], 4, path)
falseThis function is part of the experimental code in Oscar. Please read here for more details.
Hash function
shake_256 — Function
shake_256(msg::AbstractVector{UInt8}, outlen::Int) -> Vector{UInt8}Return the first outlen bytes of the SHAKE256 extendable output function applied to the byte vector msg, see [NIS15] for details.
Examples
julia> bytes2hex(shake_256(UInt8[], 32))
"46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762f"This function is part of the experimental code in Oscar. Please read here for more details.