EP-4742589-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

• van Vredendaal, Christine
• CUSTERS, Frank
• VERBAKEL, Denise Elisabeth Petronella
• van NIEKERK, Eva

Assignees

• NXP B.V.

Dates

Publication Date

20260513

Application Date

20241107

Claims (15)

1. A computer implemented method of generating authentication path data for a cryptographic signature generation process, the method implemented by processing resource, the method comprising: traversing a hash tree, wherein the hash tree is associated with a signature generation process on a 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 the computation associated with the identified cryptographic signature; 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.
2. A method according to Claim 1, wherein the method further comprises receiving a request for a cryptographic signature.
3. A method according to Claim 2, wherein the request is from an external computing resource or is generated by a computational process implemented on the processing resource.
4. A method according to any preceding claim, wherein the signature generation threshold is based on a maximum signature generation time and signature node computation cost
5. A method according to Claim 4 wherein the maximum signature generation time is specified by an entity which implements or requests the signature generation.
6. A method according to any preceding claim, wherein the method further comprises, prior to applying the signature generation threshold, optimising the signature generation threshold by iteratively modifying the signature generation threshold.
7. A method according to any preceding claim, wherein the dummy signature is based on a randomly generated character sequence.
8. A method according to any preceding claim wherein the randomly generated character sequence is an alphanumeric sequence.
9. A method according to any preceding claim wherein the processing resource is hosted within an embedded computing device.
10. A method according to any preceding claim, the method further comprising providing an authentication path as part of a cryptographic signature, wherein the authentication path comprises the dummy signature.
11. A method according to any preceding claim, wherein the identification of future signatures is based on the identification of right hand nodes in the hash tree.
12. A method according to any preceding claim, wherein, upon identifying a signature which exceeds the signature generation threshold, signatures proceeding the signature are discarded.
13. A non-transitory computer readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform the method of any one of claims 1 to 12.
14. A system configured to implement the method of Claims 1 to 12.
15. A processing resource comprising a processor and memory including executable instructions that, as a result of execution by the processor, causes the reader to perform the method of Claims 1 to 12.

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