1
$\begingroup$

I have questions on “SPHINCS: practical stateless has-based signature” by Bernstein et al. And I really hope that someone can help me with it. To help me understand it, I read the https://cryptoservices.github.io/quantum/2015/12/08/XMSS-and-SPHINCS.html blog.

SPHINCS is really composed of WOTS+, XMSS, and HORST building blocks. I understand each one of these alone, but I am still having a problem figuring out how to sign a message in SPHNICS. I understand the hyper-tree structure of layers of L-Trees (WOTS+ trees) where the final layer is the HORST tree. Here are my questions:

Q1. If I have to sign a message, M, do I randomly pick any of the HORST trees and sign my message? The signature is going to be pretty huge to reach all the way up to the PK. i.e. the signature must contain the authentication path of all roots to reach the PK. Is this correct?

Q2. According to the example parameters mentioned in https://cryptoservices.github.io/quantum/2015/12/08/XMSS-and-SPHINCS.html of h=3 and d=3 which yields three layers of height 1 each. In layer 2, each node in the two WOTS+ trees can sign k roots of layer 1 WOTS+ trees? So when I reach layer 0, the total number of messages I can sign is (2*k)^3. Is this correct?

Thank you very much for your help

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If I have to sign a message, M, do I randomly pick any of the HORST trees and sign my message?

With the original Sphincs, yeah, that's what you do.

(As an aside, the designers of Sphincs+ (and IIRC, Gravity-Sphincs) realized that this was a nonoptimal design; it allowed a forgery to select the HORST tree that gave him the best probability of success; that is, the one that was used the most). Hence, what they did in Sphincs+ to do specify a mapping from the randomized message to both a FORS (used in replacement of HORST in Sphincs+) few-time-signature AND the combination of FORS leafs; that way, the attacker doesn't get such an advantage).

The signature is going to be pretty huge to reach all the way up to the PK

Well, yes, yes it is.

According to the example parameters mentioned of h=3 and d=3 which yields three layers of height 1 each. In layer 2, each node in the two WOTS+ trees can sign k roots of layer 1 WOTS+ trees? So when I reach layer 0, the total number of messages I can sign is (2*k)^3. Is this correct?

Well, no; in the notation they use in Sphincs, h is the total number of XMSS levels in the combined hypertree, and d is the number of levels of XMSS trees (that is, the number of one-time signatures). With h=d=3, then each XMSS tree is of height h/d = 1; that is, each XMSS tree has two leaf nodes (and so can sign two messages). In addition, if h=3, then there is a total of $2^h = 8$ HORST trees (as h is the total hypertree height); of course, each HORST tree can sign several messages (and the security of the HORST tree degrades as it signs more messages)

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you very much.. This really helps. I am looking at the original paper,and I think the d-1 layer is always a single tree where the rest are 2^(layer)(h/d)... $\endgroup$
    – Mona
    May 22, 2019 at 23:44
  • $\begingroup$ Then the maximum numbers of signatures is always 2^h. Because each layer will have 2^(d-1-i)h/d trees $\endgroup$
    – Mona
    May 22, 2019 at 23:48
  • $\begingroup$ assuming that each HORST can sign only one message $\endgroup$
    – Mona
    May 22, 2019 at 23:52
  • $\begingroup$ @Mona: of course, the whole point of HORST is that it can safely sign several messages... $\endgroup$
    – poncho
    May 23, 2019 at 2:45
  • $\begingroup$ I am just curious to know, how do we pronounce HORS? Is it "H," "O," "R," "S," or "horse"? $\endgroup$
    – Mona
    May 23, 2019 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.