0
$\begingroup$

I've been checking the NIST PQC documents to find the requirements about the minimum required numbers of signatures to be generated with a signature scheme:

I think the other schemes don't have this limitation, but Hash Based Signature schemes do have a limited (though possibly big enough for anything) number of signatures that can be generated (that applies for stateful as well as for stateless HBS like SPHINCS+).

I'm sure such a requirement exists in the NIST PQC program -- could anyone point me to it?

Improve this question
$\endgroup$
1
  • $\begingroup$ Stateful signature schemes are not so much ewll as requiring a different API $\endgroup$
    – poncho
    Commented Dec 15, 2023 at 16:53

2 Answers 2

Reset to default
1
$\begingroup$

Page 15 section 4.A.4 of NIST call for proposal (the 2016 one) says:

... it may be assumed that the attacker has access to signatures for no more than $2^{64}$ chosen messages ...

IIRC, NIST or some of their staff said they consider it a denial of service attack against the signing oracle to query for more than $2^{64}$ signatures.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I've seen that sentence, but doesn't that just describe a maximum number of chosen plaintexts with signatures that are assumed for attacks, instead of a minimum number of possible signatures ? Imho any signature scheme with < 2^64 possible signatures would comply with this requirement... $\endgroup$
    – radix
    Commented Oct 26, 2023 at 7:10
  • $\begingroup$ @radix That sentence should be interpreted as the minimum number of signature queries that can be made to the signing oracle for the algorithm to remain secure (since it said "no more" than $2^{64}$). This seems to be a interpretation/understanding problem, rather than a technical one. You may get further help on english.stackexchange.com. $\endgroup$
    – DannyNiu
    Commented Oct 26, 2023 at 7:36
  • $\begingroup$ Hm, that may be the problem. I'm working mostly in English and usually have no trouble understanding technical documents, but with this sentence...even when I look at it over and over again, I can't see the meaning you're describing. $\endgroup$
    – radix
    Commented Oct 26, 2023 at 8:06
  • $\begingroup$ I've followed your advice and asked at English Language & Usage. So far they rather seem to confirm my understanding of the sentence. $\endgroup$
    – radix
    Commented Oct 26, 2023 at 11:42
  • $\begingroup$ I second radix: it seems clear to me that the sentence means that the signatures can be considered secure if it remains EUF-CMA given up to $2^{64}$ signatures, but needs not be secure given, say, $2^{70}$ signatures (probably because it's safe to assume no attacker will ever gather $2^{70}$ signatures with a given signing key in the real world). $\endgroup$
    – Geoffroy Couteau
    Commented Oct 27, 2023 at 6:41
0
$\begingroup$

After some more research I'm trying to answer my own question here:

The question does not make sense, because it's based on the false assumption that NIST's call for proposals makes a statement about a minimum number of signatures to be provided by a signature scheme.

The call for proposals requires that any proposed crypto scheme is stateless. Being stateless seems to be equivalent with allowing for a virtually unlimited number of signatures. So I think that it implicitly asks for an unlimited number of signatures.

So maybe this question should be deleted altogether.

I think I came to this false assumption because I did not (and still don't) know much about SPHINCS+. I've read that it uses a few-time signature scheme and thus drew the conclusion that, despite being stateless, there is a max. number of signatures that can be generated with SPHINCS+.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ "I've read that it uses a few-time signature scheme and thus drew the conclusion that, despite being stateless, there is a max. number of signatures that can be generated with SPHINCS+"; Sphincs+ can generate an unlimited number of signatures. There is a reduction in security if the attacker can see more than $2^{64}$ of them - however, the NIST call specifically states that we will assume that the attack can see no more than that... $\endgroup$
    – poncho
    Commented Dec 15, 2023 at 13:47
  • $\begingroup$ Even for stateless signatures, their security would degrade if "unlimited number" of signature queries are allowed. For example, LWE is secure if polynomial number (not unlimited) of independent samples in the security parameter are queried. Something similar holds for MPC in the Head signatures. For example, see Theorem 4 of eprint.iacr.org/2022/1645.pdf, $q_S$ is the number of signature queries and the probability of forgery is bounded by this value. $\endgroup$
    – lamba
    Commented Dec 16, 2023 at 15:30

Your Answer

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

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