This week's Study Group was led by
Peter Scholl who spoke about hash-based signatures and in particular
a recent paper by Bernstein, Hopwood, Hulsing, Lange, Niederhagen,
Papchristodoulou, Schwabe and Wilcox O'Hearn, called SPHINCS:
practical stateless hash-based signatures [1].
Most real-world signature schemes like RSA and DSA can be broken by a quantum computer, due to Shor's algorithm [2]. One could use lattice-based signatures but their security is not well understood: the authors of [1] note that "their quantitative security levels are highly unclear" even in the pre-quantum setting.
Most real-world signature schemes like RSA and DSA can be broken by a quantum computer, due to Shor's algorithm [2]. One could use lattice-based signatures but their security is not well understood: the authors of [1] note that "their quantitative security levels are highly unclear" even in the pre-quantum setting.
On the other hand, hash-based signature schemes using 'quantum-resistant' one-way hash functions are secure in the quantum setting [3], although the symmetric security parameter needs to be doubled for quantum resistance due to Grover's algorithm [4]. The trouble is that such schemes tend to be inefficient or stateful, where the latter means one cannot have a signing key shared across multiple devices and the scheme may be vulnerable to 'restart attacks' where the scheme is forced to re-use a secret key, compromising security. The paper of Peter's talk seeks to address this by constructing a (relatively) efficient, stateless, hash-based signature scheme called SPHINCS. The construction is proved secure “based on weak standard-model assumptions, avoiding collision resistance and the random-oracle model”.
One Time Signature Schemes
First, we revisited the Lamport One
Time Signature (OTS) scheme. (This isn't the OTS used in the paper but it will serve as a reasonable approximation.) Here your secret key is a sequence of
pairs of bitstrings $(x_0, y_0), ..., (x_n, y_n)$ and the public key is
the sequence of pairs of hashes $(H(x_0), H(y_0)), ..., (H(x_n),
H(y_n))$. To sign a message $m$ one takes each bit $m_i$ of $m$ and selects
$x_i$ or $y_i$ according to whether $m_i$ is 0 or 1. To verify a signature
one hashes each $x_i$ or $y_i$ in the signature and checks the output
against the public key. This is called “One Time” since the
secret key can only sign one message before security is seriously compromised: your
signature reveals half of the elements of the secret key.
From 'One Time' to 'Many Times'
From 'One Time' to 'Many Times'
A natural way to build “many time”
signature schemes is to iterate OTS schemes. The trouble is that
doing this in a naive way means the verification algorithm needs
a huge number of public key components, enough for all the bits of all the messages you ever want to sign!
Instead, we compress each OTS public key using a “Merkle tree”
where the (original) OTS public keys are the leaf nodes and parents are
constructed by hashing the concatenation of the children (together with a bitmask for added security). We want the (new) public key to be the root of this tree and so our signature must supply enough information (in as brief a way as possible) for the verifier to recover the root. This is how we do it:
- Given the path from a leaf to the root, let the sequence of siblings of each node on the path be called the authentication path of the leaf.
- In a signature, supply the index of the leaf node used and its authentication path.
- With the leaf and its sibling, the verifier can construct the parent.
- Then with the sibling of the parent, the verifier can construct the grandparent.
- The verifier continues like this, using the siblings given in the authentication path to recover the root node i.e. the public key.
"Eliminating the State"
Goldreich's [5] answer
to this problem was to deterministically choose which OTS key to use
next, rather than just use them in order, i.e. some hash of the
message determines the index of the OTS secret key to use in signing.
Of course, now one needs a much bigger tree in order to avoid
accidentally using a “one time” key more than once. In fact, for
security, there needs to be exponentially many OTS key pairs, so we
can't just have one leaf of the tree for each OTS secret key or the
tree would be far too big for efficient signing. Instead, we
associate every node with an OTS key pair and at each step
from a leaf to the root, sign the hash of the public keys of the child nodes with
the secret key of the parent node. The new (longer) signature contains the
index of the leaf node used and the OTS signatures of all the nodes on the path to the root. The trouble with this scheme is that the length of the signature is cubic in the security parameter. This is where the authors of [1] come in.
From 'One Time' to 'A Few Times'
The main idea of the paper is to use a 'few times signature' scheme (instead of an OTS) at the bottom of the tree to reduce the number of leaves needed for security and hence the overall height of the tree, thus shortening the signature. Their choice of scheme for the bottom of the tree is called HORS: Hash to Obtain Random Subset. In HORS, the secret key is the tuple $(s_1, ..., s_t)$, the public key is the hashes $(H(s_1), ..., H(s_t))$ and a message $m$ determines a (“random”) subset $S$ of $\lbrace1, 2, ..., t\rbrace$ with fixed size $k$ (much smaller than $t$). Then the signature for $m$ is the set of secret key components corresponding to $S$, i.e. $\lbrace s_i | i \in S\rbrace$. Now we can use the secret key 'a few times' before security is compromised as only a small number of the components $s_i$ of the secret key are revealed in each signature. But again we have the problem that the public key needs to be very large and so a Merkle tree is once again employed: the new public key becomes the root node, recoverable from the index of a leaf node and the corresponding authentication path. Notice that this means the bottom of the tree in SPHINCS, the construction proposed in [1], is itself a tree. So SPHINCS consists of a hyper-tree (a tree of trees).
The SPHINCS Tree of Trees
The SPHINCS hyper-tree has total height $h$ consisting of $d$ layers, each of height $h/d$. The index from the hash of the message determines a HORS tree on the bottom layer of the hyper-tree and a leaf of this HORS tree from which we compute the HORS signature of the message. Then this signature is signed according to the OTS scheme on the next layer (where the initial index in some way determines the tree and the leaf to use). We repeat this OTS signing on each layer and finally output the SPHINCS signature consisting of the index, the HORS signature (which contains all the information needed to recover the HORS public key) and each OTS signature and each authentication path needed to recover the root at each layer.
Real World Considerations (in the Quantum Computing World!)
From 'One Time' to 'A Few Times'
The main idea of the paper is to use a 'few times signature' scheme (instead of an OTS) at the bottom of the tree to reduce the number of leaves needed for security and hence the overall height of the tree, thus shortening the signature. Their choice of scheme for the bottom of the tree is called HORS: Hash to Obtain Random Subset. In HORS, the secret key is the tuple $(s_1, ..., s_t)$, the public key is the hashes $(H(s_1), ..., H(s_t))$ and a message $m$ determines a (“random”) subset $S$ of $\lbrace1, 2, ..., t\rbrace$ with fixed size $k$ (much smaller than $t$). Then the signature for $m$ is the set of secret key components corresponding to $S$, i.e. $\lbrace s_i | i \in S\rbrace$. Now we can use the secret key 'a few times' before security is compromised as only a small number of the components $s_i$ of the secret key are revealed in each signature. But again we have the problem that the public key needs to be very large and so a Merkle tree is once again employed: the new public key becomes the root node, recoverable from the index of a leaf node and the corresponding authentication path. Notice that this means the bottom of the tree in SPHINCS, the construction proposed in [1], is itself a tree. So SPHINCS consists of a hyper-tree (a tree of trees).
The SPHINCS Tree of Trees
The SPHINCS hyper-tree has total height $h$ consisting of $d$ layers, each of height $h/d$. The index from the hash of the message determines a HORS tree on the bottom layer of the hyper-tree and a leaf of this HORS tree from which we compute the HORS signature of the message. Then this signature is signed according to the OTS scheme on the next layer (where the initial index in some way determines the tree and the leaf to use). We repeat this OTS signing on each layer and finally output the SPHINCS signature consisting of the index, the HORS signature (which contains all the information needed to recover the HORS public key) and each OTS signature and each authentication path needed to recover the root at each layer.
Real World Considerations (in the Quantum Computing World!)
After
proving its security, the authors demonstrate the practicality of
SPHINCS with certain choices of parameters: the hyper-tree has
total height 60 consisting of 12 layers (each of height 5), the
number of HORS secret key elements is $2^{16}$ and 32 of these are
revealed in each HORS signature (i.e. $t=2^{16}$, $k = 32$). There is also
a parameter that affects the OTS scheme but we haven't detailed it
here. With these choices, the signatures have size 41KB, the keys
have size around 1KB and
one can sign hundreds of messages per second on
a modern quad-core computer.
By most accounts, quantum computers are something of a pipe-dream at the moment. Nevertheless, it's reassuring to know that security is still achievable - and indeed practical - against adversaries who can exploit the enormous power of quantum computers, whenever that day comes.
[5] - Foundations of Cryptography: Volume 2, Basic Applications (2004)
No comments:
Post a Comment