Method for generating stateful hash based signatures of messages to be signed

A non-transitory memory comprising a computer program product directly loadable into a memory of at least one computer, the computer program product having software code instructions for performing a method for generating stateful hash based signatures of messages to be signed in a key management system (“KMS”) including a manager device and a plurality of tamper-proof computing devices, wherein the manager device and tamper-proof computing devices respectively comprise a processor and memory, the respective memory storing said software code instructions, the software code instructions comprising instructions to cause the respective processors to:

• generate, by said manager device, a master merkle tree having a root and leaves, the root of the master merkle tree being a master public signature key and the leaves of the master merkle tree being master One-Time Signature (“OTS”) public keys, associated with master OTS private keys,
• trigger, by said manager device, generation of a predetermined number of slave merkle trees, wherein each leaf of the slave merkle trees is an OTS public key associated with an OTS private key, said predetermined number of slave merkle trees being equal to the number of tamper-proof computing devices and each generated slave merkle tree has its root signed by one of the master OTS private keys of the master merkle tree to build-up a multi-tree structure,
• for each message to be signed:
• select, by said manager device, one of the signing tamper-proof computing devices for signing,
• dynamically assign, by said manager device, one yet unassigned generated slave merkle tree to said signing tamper-proof computing device for issuance of one signature only,
• generate and sending, by said manager device to said signing tamper-proof computing device a command comprising said message to be signed, data enabling obtaining the OTS private key of the assigned slave merkle tree to be used to generate an OTS signature of the message to be signed, and a state value associated to said assigned slave merkle tree and keeping track of the OTS private keys of said assigned slave merkle tree already used for generating a signature,
• obtain, by said signing tamper-proof computing device, a signing OTS private key from said data enabling to obtain an obtaining the an OTS private key,
• generate, by said signing tamper-proof computing device, an OTS signature of said message to be signed with said signing OTS private key,
• update, by said signing tamper-proof computing device, said state value associated to said assigned slave merkle tree such that said obtained OTS private key cannot be used anymore for generating signatures,
• generate a stateful hash based signature of said message to be signed from said generated OTS signature using an authentication path, in the slave merkle tree assigned to said signing tamper-proof computing device, of the OTS public key corresponding to said obtained OTS private key,
• said generated stateful hash based signatures being configured to be verified by a verification process which uses the master public signature key at the root of the master merkle tree as the only public signature key.

A key management system (KMS) comprising a manager device and a number greater than one of tamper-proof computing devices, wherein the manager device and tamper-proof computing devices respectively comprise a processor and memory, the respective memory storing instructions which when executed by the respective processor causes the respective processor to perform:

• generate, by said manager device, a master merkle tree having a root and leaves, the root of the master merkle tree being a master public signature key and the leaves of the master merkle tree being master One-Time Signature (“OTS”) public keys, associated with master OTS private keys,
• trigger, by said manager device, generation of a predetermined number of slave merkle trees, wherein each leaf of the slave merkle trees is an OTS public key associated with an OTS private key, said predetermined number of slave merkle trees being equal to the number of tamper-proof computing devices and each generated slave merkle tree has its root signed by one of the master OTS private keys of the master merkle tree to build-up a multi-tree structure,
• for each message to be signed:
• select, by said manager device, one of the signing tamper-proof computing devices for signing,
• dynamically assign, by said manager device, one yet unassigned generated slave merkle tree to said signing tamper-proof computing device for issuance of one signature only,
• generate and sending, by said manager device to said signing tamper-proof computing device a command comprising said message to be signed, data enabling obtaining the OTS private key of the assigned slave merkle tree to be used to generate an OTS signature of the message to be signed, and a state value associated to said assigned slave merkle tree and keeping track of the OTS private keys of said assigned slave merkle tree already used for generating a signature,
• obtain, by said signing tamper-proof computing device, a signing OTS private key from said data enabling to obtain an obtaining the an OTS private key,
• generate, by said signing tamper-proof computing device, an OTS signature of said message to be signed with said signing OTS private key,
• update, by said signing tamper-proof computing device, said state value associated to said assigned slave merkle tree such that said obtained OTS private key cannot be used anymore for generating signatures,
• generate a stateful hash based signature of said message to be signed from said generated OTS signature using an authentication path, in the slave merkle tree assigned to said signing tamper-proof computing device, of the OTS public key corresponding to said obtained OTS private key,
• said generated stateful hash based signatures being configured to be verified by a verification process which uses the master public signature key at the root of the master merkle tree as the only public signature key.