US-20260127322-A1 - USING DUMMY SIGNATURES FOR FASTER HBS ON THE FLY SIGNING TIMES

Abstract

A method is proposed to make more efficient use of limited computing resources in signature generation.

Inventors

• Christine Van Vredendaal
• Frank Custers
• Denise Elisabeth Petronella Verbakel
• Eva van Niekerk

Assignees

• NXP B.V.

Dates

Publication Date

20260507

Application Date

20251031

Priority Date

20241107

Claims (20)

1. 1 .- 15 . (canceled)
2. 16 . A method of generating authentication path data for a cryptographic signature generation process, the method implemented by a processing resource of a computing device, the method comprising: traversing a hash tree that is associated with a signature generation process on the computing device; based on the traversal of the hash tree, identifying future cryptographic signatures to be generated in association with the hash tree; applying a signature generation threshold to the identified future cryptographic signatures to identify future cryptographic signatures which exceed the signature generation threshold and cryptographic signatures which do not exceed the signature generation threshold, wherein the signature generation threshold is based on a computation associated with the identified future cryptographic signatures; and wherein, if the signature generation threshold is exceeded by at least one future cryptographic signature, the method further comprises generating a dummy signature to be used as part of authentication path data associated with the at least one future cryptographic signature.
3. 17 . The method according to claim 16 , wherein the method further comprises receiving a request for a cryptographic signature.
4. 18 . The method according to claim 17 , wherein the request is received from an external computing resource.
5. 19 . The method according to claim 17 , wherein the request is generated by a computational process implemented on the processing resource.
6. 20 . The method according to claim 16 , wherein the signature generation threshold is based on a maximum signature generation time and signature node computation cost.
7. 21 . The method according to claim 20 , wherein the signature generation threshold is defined as: T_F = t / C wherein t is the maximum signature generation time and C is the signature node computation cost.
8. 22 . The method according to claim 20 , wherein the maximum signature generation time is specified by an entity which implements or requests the signature generation.
9. 23 . The method according to claim 20 , wherein the signature node computation cost is based on an average hash computation time.
10. 24 . The method according to claim 16 , wherein the method further comprises, prior to applying the signature generation threshold, optimizing the signature generation threshold by iteratively modifying the signature generation threshold.
11. 25 . The method according to claim 24 , wherein modifying the signature generation threshold comprises increasing the signature generation threshold if a threshold number of future signatures do not exceed the signature generation threshold.
12. 26 . The method according to claim 16 , wherein the dummy signature is based on a randomly generated character sequence.
13. 27 . The method according to claim 26 , wherein the randomly generated character sequence is an alphanumeric sequence.
14. 28 . The method according to claim 16 , wherein the processing resource is hosted within an embedded computing device.
15. 29 . The method according to claim 16 , the method further comprising providing an authentication path as part of a cryptographic signature, wherein the authentication path comprises the dummy signature.
16. 30 . The method according to claim 16 , wherein the identification of the future cryptographic signatures is based on identification of right hand nodes in the hash tree.
17. 31 . The method according to claim 16 , wherein, upon identifying a signature which exceeds the signature generation threshold, discarding the cryptographic signatures preceding the signature.
18. 32 . The method according to claim 16 , wherein generating the cryptographic signatures comprises generating the cryptographic signatures based on LMS or XMSS signature generation.
19. 33 . A non-transitory computer readable storage medium comprising executable instructions that, when executed by a processor of a computer system, cause the processor to: traverse a hash tree that is associated with a signature generation process on the computing device; based on the traversal of the hash tree, identifying future cryptographic signatures to be generated in association with the hash tree; apply a signature generation threshold to the identified future cryptographic signatures to identify future cryptographic signatures which exceed the signature generation threshold and cryptographic signatures which do not exceed the signature generation threshold, wherein the signature generation threshold is based on a computation associated with the identified future cryptographic signatures; and if the signature generation threshold is exceeded by at least one future cryptographic signature, generate a dummy signature to be used as part of authentication path data associated with the at least one future cryptographic signature.
20. 34 . The non-transitory computer readable storage medium of claim 33 , wherein the signature generation threshold is based on a maximum signature generation time and signature node computation cost.

Description

FIELD The invention relates to a method and system. Particularly, but not exclusively, the invention relates to the generation of authentication path data. BACKGROUND Digital signatures are of vital importance to our cryptographic infrastructure. For example, they underpin the authentication infrastructure in the form of digital certificates on the internet, which is shifting more and more to resource-constrained devices as part of the Internet of Things (IoT). In order to make digital signatures accessible to such small devices, it is important to minimize the resource requirements and optimize the efficiency of the involved algorithms (e.g., key generation, signing and verification). These signatures can be computationally intensive to generate, and this can be problematic for signature generation by devices which have limited memory resources. Aspects and embodiments were conceived with the foregoing in mind. SUMMARY Aspects relate to the generation of cryptographic signatures and authentication path data to be used alongside cryptographic signatures or as part of cryptographic signatures. Viewed from a first aspect, there is provided a computer implemented method of generating authentication path data for a cryptographic signature generation process. An authentication path may comprise data to be used in support of authenticating the generated cryptographic signature. The data may comprise a series of hashes corresponding to nodes on the authentication path. The method may be implemented by processing resource. The processing resource may be hardware or software implemented. The processing resource may be hosted by an embedded computing device. The processing resource may be hosted within a computing device. The processing resource may be a cryptographic processing resource which is configured to perform cryptographic operations. The processing resource may receive input requests from an external computing entity or another computing entity which shares the same chip. The method may comprise traversing a hash tree. The traversal may comprise the application of a computer program which comprises instructions which can be used to access each node on the hash tree to determine the hash value. The hash tree may be associated with a signature generation process on a computing device. The signature generation process may implement hash-based signature generation in accordance with, for example, Leighton-Micali Signatures (LMS) or Extended Merkle Signature Scheme (XMSS). The method may, based on the traversal of the hash tree, identify future cryptographic signatures to be generated in association with or using the hash tree. The method may comprise applying a signature generation threshold to the identified future cryptographic signatures to identify future cryptographic signatures which exceed the signature generation threshold and cryptographic signatures which do not exceed the signature generation threshold. The signature generation threshold may be based on the computation associated with the identified cryptographic signature. If the signature generation threshold is exceeded by at least one future cryptographic signature, the method further comprises generating a dummy signature to be used as part of authentication path data associated with the at least one future cryptographic signature. The method may further comprise updating the state of the underlying hash tree to indicate the future signature has been used or has a dummy signature associated with it. A dummy signature is a cryptographic signature which may be generated in response to identifying computationally intensive signatures. The dummy signature is a cryptographic signature which, for example, is generated in accordance with the LMS or XMSS approaches described in NIST Special Publication 800-208, which assigns a cryptographic signature to a randomly generated sequence of characters. The randomly generated sequence of characters does not correspond to a message or data item to be signed responsive to input from a user or a computing entity. That is to say, the dummy signature is generated responsive to the identification of computationally intensive signatures in that the dummy signature is a cryptographic signature which is used to sign a random sequence of characters The randomly generated sequence of characters may be randomly or pseudo-randomly generated by the processing resource or it may be retrieved from an external entity. A dummy signature may also be generated in association with a message which is made up solely of zeros in that a cryptographic signature may be generated to sign a sequence of zeros of a message length specified by a user, the processing resource or a manufacturer of the processing resource or an entity external to the processing resource. The use of the all zero message in this response further improves signing times. Also, in accordance with NIST Special Publication 800-208, an authentication path is generated