SPHINCS+ is a stateless hash-based signature scheme, which is quantum robust. It was proposed by Bernstein et al. in 2015 [paper] and updated in [1]. SPHINCS+ 256 128-bit has a public key size of 32 bytes, a private key size of 64 bytes, and a signature of 17kB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor. In this case we will implement using SHA-256. SPHINCS+ uses many trees. In tis case the first tree is defined in a simple way than a Merkle Tree, but we use a level mask. If we have four root nodes \((A, B, C\) and \(D)\), and a first level mask of \(Q_1\), we get two Level 1 nodes of \(L1_0=H((A || B) \oplus Q_1\) and \(L1_1=H((C || D) \oplus Q_1\). We then create a root hash of \(Root=H((L1_0 || L1_1) \oplus Q_2\). The public key is defined with the root hash along and the bitmasks. Each of the leaves of the tree are then public keys for the WOTS+ L-trees using in SPHINCS+ [more details].
SPHINCS+ Tree |
Details
Coding
The following is an implementation of SPHINCS+:
import hashlib import numpy as np import binascii def hashit(a,b,Q): m = hashlib.sha256() m.update(a+b) m=m.digest() c = bytes([aa ^ bb for aa, bb in zip(m,Q)]) return (c) def printnodes(title,n): print (title) for i in n: print (binascii.b2a_hex(i)) n_nodes=4 n_levels=2 node = [0]*n_nodes Q = [0]*(n_levels) level1 = [0]*(n_nodes//2) for i in range (0,n_nodes): node[i]=np.random.bytes(32) for i in range (0,n_levels): Q[i]=np.random.bytes(32) i=0 for n in range(0,n_nodes,2): level1[i]=hashit(node[n],node[n+1],Q[0]) i=i+1 pub = hashit(level1[0],level1[1],Q[1]) printnodes("Nodes:",node) printnodes("\nLevel 1:",level1) print("\nRoot: ",binascii.b2a_hex(pub))
A sample run is
Nodes: b'b69c70c9d4e53008800fa00a5d3c7da7066ebadea7347eb1f94d0b52edd825a5' b'cc12c073709d5be5095a0d4e81fae36b98a34e715cb747e990679c6ed8f7ae51' b'8559e17789a1d4ddb2cc6d6515c1c0f3a594ad49570ddb39be6d920b799844dc' b'bf5b092aab50616d290c43881715de5bd6aaa8b6adbf59554483769355dcdf9f' Level 1: b'a3e1c96fb6cbb684b8546b66791632c929f0d77e3bebde0339535488caf551c8' b'782d270b840a84379ecbe871007855cf4d7114351b4962a2c0326fa8c58cff4c' Root: b'e1e72492dd0adccb8c74a566261b013ebfbc1f079df35a50ad8e8bc35cf5a639'
Reference
[1] Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., & Schwabe, P. (2019, November). The SPHINCS+ signature framework. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (pp. 2129-2146) [paper].