2
$\begingroup$

Unlike pretty much every other signature scheme that I am aware of (excluding Picnic, the original SPHINCS, and SPHINCS-gravity) SPHINCS+ requires that the whole message be available during the signing operation. This is because it uses a "message randomization value" which if I am not mistaken it is used in order to avoid multi-target attacks. From the SPHINCS+ reference implementation:

/* Compute the digest randomization value. */
gen_message_random(sig, sk_prf, optrand, m, mlen);

/* Derive the message digest and leaf index from R, PK and M. */
hash_message(mhash, &tree, &idx_leaf, sig, pk, m, mlen);

In order to bypass that requirement one could first hash the whole message and then sign the result but this means that the whole scheme will be broken if said hash function is not collision resistant (SPHINCS+ by itself only depends on the [second?] preimage resistance of the hash function).

My question is as follows: Is it possible to use "tree signing" (kinda like a merkle tree but for signatures) in order to avoid storing the whole message in memory and at the same time have the whole scheme depend only on the preimage resistance of the hash function?

The scheme that I have in mind would work as such (assuming that each node has exactly 2 children): $$ \begin{align} N_{i, 0} &= S_{sk}(0\| 0 \| i \| m_i) \\ N_{i, j + 1} &= S_{sk}(0\| j + 1 \| i \| N_{2i, j} \|N_{2i+1, j} ) \\ Sig &= S_{sk}(1 \| N_{0, J} \|N_{1, J}) \end{align} $$

Improve this question
$\endgroup$
  • $\begingroup$ If I've understood your problem correctly; If you hash the message then you already read all of it, right? $\endgroup$ – kelalaka Aug 22 '20 at 8:10
  • $\begingroup$ Doesn't this always hold true? $\endgroup$ – user83146 Aug 22 '20 at 8:18
  • $\begingroup$ Your proposal uses the function $S_{sk}$; is $sk$ a secret value (if so, how does the verification process work), or is it a public value (and if so, how does that not rely on collision resistance)? $\endgroup$ – poncho Aug 22 '20 at 13:58
  • $\begingroup$ sk is the private key for sphincs+. The verification process is the same but uses the public key instead. I should note that the tree nodes will be available to the one verifying. $\endgroup$ – user83146 Aug 22 '20 at 15:54
  • $\begingroup$ Apologies, I forgot to tag you: @kelalaka $\endgroup$ – user83146 Aug 24 '20 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.