I'm following the advice of a user who answered a question on StackOverflow.

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

For the purpose of estimating security strengths, it may be assumed that the attacker has access to signatures for no more than 2⁶⁴ chosen messages;

My original question was where I'd find NIST's requirements about the minimum number of signatures that can be generated with a digital signature scheme (let's say some algorithm).

I don't manage to get the meaning about a minimum number of possible signatures from this sentence, as @DannyNiu seems to understand it in his response (i.e. a signature scheme has to provide at least this lower bound number of signatures).

What I rather understand from that sentence is that it's just an assumption for the security evaluation, i.e. the evaluation is done assuming an attacker has less than 2⁶⁴ chosen plaintexts with their matching signatures. We ideally want signature schemes with a virtually unlimited amount of possible signatures.

Maybe someone could try to explain this sentence to me, in case the @DannyNiu is right, or otherwise confirm that I understand it correctly.


I should provide some background/context: This document is (among others) about so-called hash-bashed signatures. Current signature schemes can be used endlessly (i.e. you can create an infinite number of signatures). Hash-based signature schemes, on the other side, have a limited number of signatures that can be generated. So NIST should have a requirement like any proposed signature scheme SHALL be usable for at least x signatures.

2^64 would imho indeed be a reasonable value, but it might also be 2^50 or 2^80.

[For the purpose of ELU, 2⁶⁴ is merely an extremely large number, approximately 18.4 trillion.]



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.

Browse other questions tagged or ask your own question.