Description:Complete specification: The following specification particularly describes the invention and the manner in which it is to be performed.

Field of the invention:
[0001] The presently disclosed subject matter relates to a method to compute a public key corresponding to a private key of a SHA3-based signature scheme, a method to compute a private key of a SHA3-based signature scheme, a system for computing a private key and/or a public key, a computer readable medium.

Background of the invention:
[0002] As quantum computing progresses, there is a strong interest in providing signature schemes that are resistant against attack using quantum computers. One candidate therefor are hash-based signature schemes. These include the Winternitz One-Time Signature Plus (WOTS+), and the eXtended Merkle Signature Scheme (XMSS), both described in RFC 8391.
[0003] These signature schemes provide cryptographic digital signatures without relying on the conjectured hardness of mathematical problems. Instead, it is proven that they only rely on the properties of cryptographic hash functions.
[0004] Unfortunately, such signature schemes require the evaluations of large number of hash functions, in case of RFC 8391, of SHA2 hash functions. This makes hash-based signature schemes very compute intensive.

Summary of the invention:
[0005] It would be advantageous to have an improved signature scheme. The hash-based signature schemes of RFC 8391 are based on SHA2. The inventors realized that this choice limits the efficiency of implementation. For example, SHA2 is hard to parallelize. It was an insight of the inventors that using SHA3 improves both security and parallelization possibilities. Interestingly, the inventors discovered that some of the hash operations that result when changing RFC 8391 to SHA3 are partially redundant. Although the full messages on which SHA3 is executed will typically differ, it will often happen that one or two initial blocks are used repeatedly in various algorithms of a signature scheme. In particular, this phenomenon may happen both during private key computation, public key computation, signature generation, and signature verification.
[0006] Some embodiments are directed to hash-based signature schemes, in particular SHA3 based ones. Embodiments include private key generation, public key generation, signature generation, and signature verification. For example, a hash function may be applied to form a pseudo-random function (PRF), taking as input various strings, wherein the string starts with an opcode, and e.g., a seed. In an embodiment, at least the start of some of the strings have a common start which has at least the length of one input block of the hash function.
[0007] In an aspect of the invention, a system is configured for one or more of private key computation, public key computation, signature generation, and signature verification, and which is configured to precompute repeating initial blocks. Such a system is an electronic device, e.g., a computer.
[0008] In an aspect of the invention, methods are provided for one or more of private key computation, public key computation, signature generation, and signature verification, and which precompute repeating initial blocks. Such a method may be implemented on an electronic device, e.g., on a computer.
[0009] An embodiment of the methods may be implemented on a computer as a computer implemented method, or in dedicated hardware, or in a combination of both. Executable code for an embodiment of the method may be stored on a computer program product. Examples of computer program products include memory devices, optical storage devices, integrated circuits, servers, online software, etc. Preferably, the computer program product comprises non-transitory program code stored on a computer readable medium for performing an embodiment of the method when said program product is executed on a computer.
[0010] In an embodiment, the computer program comprises computer program code adapted to perform all or part of the steps of an embodiment of the method when the computer program is run on a computer. Preferably, the computer program is embodied on a computer readable medium.

Brief description of the accompanying drawings:
[0011] Further details, aspects, and embodiments will be described, by way of example only, with reference to the drawings. Elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. In the figures, elements which correspond to elements already described may have the same reference numerals. In the drawings,
[0012] Figure 1a schematically shows an example of an embodiment of a signature system;
[0013] Figure 1b schematically shows an example of an embodiment of a signature system;
[0014] Figure 2a schematically shows an example of an embodiment of a SHA3 computation;
[0015] Figure 2b schematically shows an example of an embodiment of a public key computation;
[0016] Figure 3 schematically shows an example of an embodiment of a multi-use public key computation;
[0017] Figure 4a schematically shows an example of an embodiment of a method to compute a public key corresponding to a private key of a SHA3-based signature scheme;
[0018] Figure 4b schematically shows an example of an embodiment of a method to compute a public key corresponding to a private key in a SHA3-based Merkle Signature Scheme,
[0019] Figure 5a schematically shows a computer readable medium having a writable part comprising a computer program according to an embodiment; and
[0020] Figure 5b schematically shows a representation of a processor system according to an embodiment.
Reference Signs List
[0021] The following list of references and abbreviations corresponds to figures 1a-3, 5a, 5b, and is provided for facilitating the interpretation of the drawings and shall not be construed as limiting the claims.
100, 101 a signature system
110 a key generation device
120 a signing device
130 a verification device
111 a processor system
112 storage
113 a communication interface
121 a processor system
122 a storage
123 a communication interface
131 a processor system
132 a storage
133 a communication interface
172 a computer network
200 a public key computation
210 private key elements
220 chains
230 public key elements
300 a multi-use public key computation
301 multiple number of use-once public keys
302 L-tree
303 Hash tree
304 a Merkle tree root
1000, 1001 a computer readable medium
1010 a writable part
1020 a computer program
1110 integrated circuit(s)
1120 a processing unit
1122 a memory
1124 a dedicated integrated circuit
1126 a communication element
1130 an interconnect
1140 a processor system
Detailed description of the embodiments:
[0022] While the presently disclosed subject matter is susceptible of embodiment in many different forms, there are shown in the drawings and will herein be described in detail one or more specific embodiments, with the understanding that the present disclosure is to be considered as exemplary of the principles of the presently disclosed subject matter and not intended to limit it to the specific embodiments shown and described.
[0023] In the following, for the sake of understanding, elements of embodiments are described in operation. However, it will be apparent that the respective elements are arranged to perform the functions being described as performed by them.
[0024] Further, the subject matter that is presently disclosed is not limited to the embodiments only, but also includes every other combination of features described herein or recited in mutually different dependent claims.
[0025] Figure 1a schematically shows an example of an embodiment of a signature system 100, Signature system 100 comprises a key generation device 110, signing device 120, and verification device 130.
[0026] Key generation device 110 is configured to generate a private key and a corresponding public key for a hash-based signature scheme. Unlike most other signature systems, hash-based signatures can so far withstand known attacks using quantum computers. An unfortunate disadvantage of hash-based signatures is that they are very compute intensive, in particular, requiring a large amount of hash computations.
[0027] Signing device 120 is configured to generate a signature for a message using the private key generated by key generation device 110. Verification device 130 is configured to verify a signature for a message, using the public key generated by key generation device 110, the signature being generated by signing device 120 using the corresponding private key.
[0027] The signature system may be generated for any of the signature schemes defined in RFC 8391; we refer to the May 2018 version of RFC 8391, which is included herein by reference. We refer in particular the passages cited herein. Other version of RFC 8391 may be used instead though.
[0028] In particular, the signature system may be configured to support the one-time signature scheme Winternitz One-Time Signature Plus (WOTS+). The signature system may be configured to support the eXtended Merkle Signature Scheme (XMSS), and XMSS^MT, a multi-tree variant of XMSS. Both XMSS and XMSS^MT use WOTS+ as a main building block.

[0029] In signature system 100 as shown, key generation device 110 generates a private key and a corresponding public key. This could be a one-time signature, or a multi-use signature.
[0030] In an embodiment, key generation device 110 and signature device 120 are integrated into a single device. This integration simplifies the architecture of the signature system 100 and reduces the need for secure communication channels between different devices for key transfers. Here, the private key, once generated, remains within the device, and is used by the signing device to create a signature.
[0031] The verification device 130, in this setup, receives the public key from the key generation device 110 through a trusted channel. The channel could be a secure digital pathway, such as an encrypted communication link, or a physical transfer of the public key through secure means. The public key be obtained from a trusted public key repository.
[0032] In an embodiment, key generation device 110 and signature device 120 are distinct devices. After the key generation device 110 creates the private and public keys, the private key is transferred to the signature device 120, which will use it to sign messages. This separation provides computational advantages, particularly in terms of resource allocation and efficiency. For instance, the key generation device 110 could be a more powerful system, such as a desktop computer, equipped to handle the resource-intensive process of generating keys. Signature device 120 could be a device with limited resources, like a smartphone.
[0033] Signature device 120 obtains the private key from key generation device. This may be done, for example, by a direct physical link. The public key may also be transferred to the signing device so that it may be further distributed from there.
[0034] Verification device 130 can obtain the public key either from the key generation device 110 through a trusted channel or from the signature device 120. The latter option can be advantageous in systems where the public key is bound to a signature or a certificate, making the verification process more streamlined.
[0035] One significant advantage of this setup is the reduced computational load on the signature device 120. Since key generation, especially in hash-based systems like XMSS or WOTS+, is resource-intensive due to the heavy computational requirements of hash computations, separating these processes allows the signature device 120 to be optimized for less resource-intensive tasks. This separation can be particularly beneficial in environments where the signing process needs to be quick and efficient, such as in high-traffic communication systems or devices with limited processing capabilities.
[0036] In both embodiments, the public key may be uploaded to a public key repository.
[0037] For example, the system 100 may be used to securely authenticate digital transactions in online banking, where the key generation device 110 creates a unique key for a user, the signing device 120 ensures the integrity of transactional data, and the verification device 130 validates the transaction's authenticity. Additionally, the system can be implemented in secure email communications, where emails are signed and verified for authenticity, ensuring that the content has not been tampered with. In the healthcare sector, the system could be used to protect sensitive patient data, with each piece of data being signed and verified to ensure confidentiality and compliance with regulations. Furthermore, the system could be applied in blockchain technologies to provide enhanced security for cryptocurrency transactions. The system can also be used in software distribution, ensuring that software updates are authentic and have not been altered. For example, locally installed software may have a public key according to an embodiment and use it to verify signed software updates.
[0038] Key generation device 110 may comprise a processor system 111, a storage 112, and a communication interface 113. Signing device 120 may comprise a processor system 121, a storage 122, and a communication interface 123. Verification device 130 may comprise a processor system 131, a storage 132, and a communication interface 133.
[0039] In the various embodiments of communication interfaces 113, 123 and/or 133, the communication interfaces may be selected from various alternatives. For example, the interface may be a network interface to a local or wide area network, e.g., the Internet, a storage interface to an internal or external data storage, an application interface (API), etc.
[0040] Storage 112, 122 and 132 may be, e.g., electronic storage, magnetic storage, etc. The storage may comprise local storage, e.g., a local hard drive or electronic memory. Storage 112, 122 and 132 may comprise non-local storage, e.g., cloud storage. In the latter case, storage 112, 122 and 132 may comprise a storage interface to the non-local storage. Storage may comprise multiple discrete sub-storages together making up storage 112, 122, 132.
[0041] Storage 112, 122 and 132 may be non-transitory storage. For example, storage 112, 122 and 132 may store data in the presence of power such as a volatile memory device, e.g., a Random Access Memory (RAM). For example, storage 112, 122 and 132 may store data in the presence of power as well as outside the presence of power such as a non-volatile memory device, e.g., Flash memory. Storage may comprise a volatile writable part, say a RAM, a non-volatile writable part, e.g., Flash. Storage may comprise a non-volatile non-writable part, e.g., ROM.
[0042] The devices 110, 120 and 130 may communicate internally, with each other, with other devices, external storage, input devices, output devices, and/or one or more sensors over a computer network. The computer network may be an internet, an intranet, a LAN, a WLAN, a WAN, etc. The computer network may be the Internet. The devices 110, 120 and 130 may comprise a connection interface which is arranged to communicate within system 100 or outside of system 100 as needed. For example, the connection interface may comprise a connector, e.g., a wired connector, e.g., an Ethernet connector, an optical connector, etc., or a wireless connector, e.g., an antenna, e.g., a Wi-Fi, 4G or 5G antenna.
[0043] The communication interface 113 may be used to send or receive digital data, e.g., a public key to device 130, a private key to device 120. The communication interface 123 may be used to send or receive digital data, e.g., to receive data for signing, or to send a signature. The communication interface 133 may be used to send or receive digital data, e.g., to receive a public key, a signed messaged, etc.
[0044] Key generation device 110, signing device 120, and verification device 130 may have a user interface, which may include well-known elements such as one or more buttons, a keyboard, display, touch screen, etc. The user interface may be arranged for accommodating user interaction for performing key generation, message signing, message verification.
[0045] The execution of devices 110, 120 and 130 may be implemented in a processor system. The devices 110, 120 and 130 may comprise functional units to implement aspects of embodiments. The functional units may be part of the processor system. For example, functional units shown herein may be wholly or partially implemented in computer instructions that are stored in a storage of the device and executable by the processor system.
[0046] The processor system may comprise one or more processor circuits, e.g., microprocessors, CPUs, GPUs, etc. Devices 110, 120 and 130 may comprise multiple processors. A processor circuit may be implemented in a distributed fashion, e.g., as multiple sub-processor circuits. For example, devices 110, 120 and 130 may use cloud computing.
[0047] Typically, the key generation device 110, signing device 120, and verification device 130 each comprise a microprocessor which executes appropriate software stored at the device; for example, that software may have been downloaded and/or stored in a corresponding memory, e.g., a volatile memory such as RAM or a non-volatile memory such as Flash.
[0048] Instead of using software to implement a function, the devices 110, 120 and/or 130 may, in whole or in part, be implemented in programmable logic, e.g., as field-programmable gate array (FPGA). The devices may be implemented, in whole or in part, as a so-called application-specific integrated circuit (ASIC), e.g., an integrated circuit (IC) customized for their particular use. For example, the circuits may be implemented in CMOS, e.g., using a hardware description language such as Verilog, VHDL, etc. In particular, key generation device 110, signing device 120 and verification device 130 may comprise circuits, e.g., for cryptographic processing, and/or arithmetic processing.
[0049] In hybrid embodiments, functional units are implemented partially in hardware, e.g., as coprocessors, e.g., cryptographic coprocessors, and partially in software stored and executed on the device. In particular, the cryptographic coprocessors may be configured for SHA3 hash computations.
[0050] Figure 1b schematically shows an example of an embodiment of a signature system 101. System 101 may comprise multiple key generation devices; shown is key generation device 110. System 101 may comprise multiple signing devices; shown is signing device 120. System 101 may comprise multiple verification devices; shown is verification device 130. The devices are connected through a computer network 172, e.g., the Internet. The key generation device 110 and signing device 120 may be according to an embodiment.
[0051] SHA-3: Figure 2a schematically shows an example of an embodiment of a SHA3 computation. We refer to ‘The Keccak reference’ Version 3.0, by Guido Bertoni, et al., of January 14, 2011, for implementation details of SHA3, and in particular for SHA3-512, SHA3-384, and SHAKE256. We also refer to the page on SHA-3 at Wikipedia.
[0052] SHA-3 uses the sponge construction in which data is absorbed into the sponge, then the result is squeezed out. In the absorbing phase, message blocks are XORed into a subset of the state, which is then transformed as a whole using a permutation function f. In the squeeze phase, output blocks are read from the same subset of the state, alternated with the state transformation function f. The size of the part of the state that is written and read is called the rate (denoted r), and the size of the part that is untouched by input/output is called the capacity (denoted c).

[0053] Computing a hash function works as follows.
[0054] Pad the input message, yielding a padded bit string P, with a length divisible by r.
[0055] Absorbing phase:
P is broken in consecutive r-bit blocks P0, P1, …
The state is initialized and each of the blocks is absorbed into the state.
[0056] Squeezing phase:
After the full string P has been absorbed, the first r bits of the state as the output form block Z0. If more output bits are needed, the permutation f is applied and the first r bits are appended, e.g., Z1, until enough bits are obtained. The blocks Z0, Z1, … are concatenated and truncated to d output bits; d depending on the particular hash function in the SHA3 suite.
[0057] For SHA3-384, and SHA3-512 instances, r is greater than d, so there is no need for additional block permutations in the squeezing phase; the leading d bits of the state are the desired hash. However, SHAKE256 allows an arbitrary output length, and may require it.
[0058] We have the following rates:
SHA3-512: 576 bits (or 72 bytes)
SHA3-382: 832 bits (or 104 bytes)
SHAKE256: 1088 bits (or 136 bytes)
[0059] For the SHA3 variants with fixed-length output (e.g., SHA3-224, SHA3-256, SHA3-384 and SHA3-512), the 01 bits are appended to the message, and for the SHA3 variants with variable-length output (e.g., SHAKE128 and SHAKE256), the bits 1111 are appended to the message.
[0060] To ensure the message can be evenly divided into r-bit blocks, padding is required. All the SHA-3 variants use the pattern 10*1 in its padding function: the 1 bit, followed by zero or more 0 bits (maximum r - 1) and a final 1 bit. See “The Keccak reference” by Guido Bertoni, et al., Version 3.0, January 14, 2011 for details (included herein by reference).
[0061] A (cryptographic) digital signature scheme provides asymmetric message authentication. The key generation algorithm produces a key pair consisting of a private and a public key. A message is signed using a private key to produce a signature. A message/signature pair can be verified using a public key. A One-Time Signature (OTS) scheme allows using a key pair to sign exactly one message securely. A Many-Time Signature (MTS) system can be used to sign multiple messages.
[0062] We will first discuss private key generation for a one-time signature.
[0063] Private key generation: For private key generation we refer to RFC 8391, in particular WOTS+ Private key generation. According to RFC 8391, the private key in WOTS+, denoted by sk (s for secret), is a length len array of n-byte strings. Herein, the parameter n refers to the message length that the signature scheme supports, and len is derived from the length of the message, the size of message elements msg[i] as defined by the Winternitz parameter w, and the size of a checksum that may be needed. Accordingly, sk is an array of strings.
[0064] If one is willing to depart from the RFC 8391, then various standards are possible. For example, the size of individual elements could be more or less than n-bytes, depending on the security. The length of len could be more or less depending on whether the RFC 8391 checksum is used or another checksum algorithm.
[0065] Section 3.1.3. RFC 8391 provides two ways to generate a private key. The first option is described in Algorithm 3, and initializes the elements sk[i] with uniformly random strings. As no hash computation is done, there is no scope to improve on hash computations. Also, it incurs the additional cost of storing the private key sk, until used. Nevertheless, the computation of other values, in particular, the public key may benefit from an embodiment.

[0066] The second option according to the RFC may follow section 3.1.7 of RFC 8391. Here the n-byte value of the private key is computed as sk[i] = PRF(S, toByte(i, 32)), wherein, S is a secret seed. Expanding the PRF according to section 5.1 introduces an OPCODE_3.
[0067] For example, according to section 3.1.7 of the RFC, the elements of sk may be computed as sk[i] = PRF(S, toByte(i, 32)). PRF is defined in section 5.1 and comprises for n=64, the SHA3 application to toByte(3, 64) || KEY || M, which in this case evaluates to toByte(3, 64) || S || toByte(i, 32). The toByte(i, 32) functions as the address.
[0068] Here S is a secret seed used to generate the private key. Assuming a 64 byte secret seed S, this means that the first 128 bytes are constant. Furthermore the first 30 bytes of the address, that is the toByte(i, 32) part, is also constant (assuming the largest value of i to be 216-1=65535), giving a total of 158 bytes. Accordingly, for SHAKE256, the first block (consisting of 136 bytes) is constant, and for SHA3-512, the first two blocks (consisting of 144 bytes) are constant.
[0069] The PRF comprises for n=48, the SHA3 application to toByte(3, 48) || KEY || M, which in this case evaluates to toByte(3, 48) || S || toByte(i, 32). Assuming a 48 byte secret seed S, this means that the first 96 bytes are constant. Furthermore the first 30 bytes of the address, that is the toByte(i, 32) part, is also constant (assuming the largest value of i to be 216-1=65535), giving a total of 126 bytes. Accordingly, for SHA3-384, the first block (consisting of 104 bytes) is constant. The toByte function converts a number to a byte string of predetermined length, and is detailed in the RFC.
[0070] We refer to a constant value used at the beginning of a SHA3 computation as an opcode. In this case the opcode is toByte(3, 64) for SHAKE256 and SHA3-512, and toByte(3, 48) for SHA3-384. The secret seed (e.g., S) is also constant for each element in the private key, but it is only constant for this particular private key. For example, toByte(3, 64) or toByte(3, 48) is referred to as OPCODE_3 or OPCODE for short. Variant schemes, that do not adhere to RFC 8391 may take any random value for the OPCODE.
[0071] Another option, which is used in practice and which is also used in the reference implementation of the RFC, to generate a private key is to generate the sequence of random values by repeatedly applying a PRF_KGen function. The PRF_KGen function comprises applying a SHA3 hash to a string starting with a concatenation of: an opcode (e.g., OPCODE_4), and a secret seed (e.g., SK_SEED), the string further comprising the public seed (e.g., SEED) and an address (e.g., ADRS) in the private key (sk). For example, opcode (e.g., OPCODE_4), secret seed (e.g., SK_SEED) and public seed (e.g., SEED) are longer than an input block size of the SHA3 hash function. Furthermore, the first 16 bytes of the address are also constant for the OTS Hash Addresses.
[0072] For example, in this option to generate the private key is to apply SHA3 to the concatenation of OPCODE?SK_SEED?SEED?ADRS. Other elements may be added, e.g., padding.
[0073] Here SK_SEED is the same secret seed S as above, but SEED is a public seed. The public seed is used to generate the public key, and including it in the generation of the private key links the two keys to each other. ADRS is an index into the private key. For example, it increases for each i in sk[i].
[0074] For SHA3-512, the size of each of OPCODE_4, SK_SEED and SEED is 64 bytes, bringing the number of constant bytes up to 64+64+64+16 = 208. The 208 constant bytes are even twice as long as the 72 bytes input block size of SHA3-512, allowing for precomputation of two input blocks.
[0075] For SHA3-384, the size of OPCODE_4 is 4 bytes, and the size of each of SK_SEED and SEED is 48 bytes, bringing the number of constant bytes up to 4+48+48+16 = 116. The 116 constant bytes are longer than the 104 bytes input block size of SHA3-384; allowing precomputation of one input block.
[0076] For SHAKE256, the size of each of OPCODE_4, SK_SEED and SEED is 64 bytes, bringing the number of constant bytes up to 64+64+64+16 = 208. The 208 constant bytes are longer than the 136 bytes input block size of SHAKE256; allowing precomputation of one input block.
[0077] In an embodiment, at least a first block of the string is constant during the computing of the private key. That is, for each element of the private key, the string on which SHA-3 is applied starts with the same block or blocks. A block has the size of an input block of the used SHA-3 algorithm, also referred to as r. For example, the following algorithm may be used
- Apply the absorb function of SHA-3 on the constant at least first block(s). Store the state S’ of the SHA3 function
- For each element of the private key,
o Initialize the SHA-3 function from stored state S’
o Absorb the remaining non-constant blocks
o Apply the squeeze function to obtain the private key element.
[0078] Instead of computing a single private key, the algorithm may be adapted to generate a string of private keys, also by repeatedly running the PRF, but in this case repeating it for longer. This is useful for generating a multi-use private key.
[0079] In an embodiment, OPCODE, SK_SEED, and SEED and part of the address are together at least one block size, e.g., SHA3-384, or SHAKE256, or two block sizes of the SHA3 hash function, e.g., SHA3-512.
[0080] Public key generation: Figure 2b schematically shows an example of an embodiment of a public key computation 200.
[0081] Given a private key, e.g., generated as above, a corresponding public key is generated. The private key comprises a sequence of random values, e.g., sk[0], sk[1], sk[2], …, sk[len-1]. A pseudorandom value is considered a random value herein.
[0082] Shown in figure 2b at 210 are the private key elements generated by the private key generation. Each value, e.g., of length n bytes, is shown as a small circle. For each value of sk[i], a chain is computed. For each element of the private key, e.g., for each sk[i], a hash chain is generated. The chains are shown at 220. To generate a chain, a chain function is repeatedly applied, each time to a previous value in the chain, starting with the private key element. For example, if x=sk[i], then the chain may be computed as chain(x), chain(chain(x)), chain(chain(chain(x))), etc., up to the chain length. The chain length may be determined by the Winternitz constant. The resulting public key is indicated at 230.
[0083] In an embodiment, the chain function may be computed as follows by
- applying a first PRF to generate a key,
- applying a second PRF to generate a bitmask,
- XOR-ing the bitmask with the previous value in the chain, and
- applying a SHA3 hash function to a concatenation of an opcode (e.g., OPCODE_0), the key and the XOR result.
[0084] The string to which the first and second PRF are applied may comprise in order a concatenation of: an opcode (e.g., OPCODE_3), a public seed (e.g., SEED), an address (e.g., ADRS), and padding. The results of the two PRFs are combined to compute the output of the chain function.
[0085] The public key is then derived from the final value for each of the chains. Interestingly, in an embodiment, at least a first block of the string is constant during the computing of the chains, e.g., during application of the first and second PRF. This can be used to precompute the sponge function on the constant at least a first block.
[0086] For example, in an embodiment generating a public key (e.g., pk) corresponding to a private key (e.g., sk), may use algorithm 4 of RFC 8391. According to this algorithm, a chain function is applied to each element of the private key. The chain function may be implemented as in Algorithm 2 of RFC 8391. The latter contains the following three function calls:
KEY = PRF(SEED, ADRS);
BM = PRF(SEED, ADRS);
tmp = F(KEY, tmp XOR BM);
[0087] The first and second PRF computations may be computed following section 5.1 by applying SHA3 on: toByte(3, 64) || SEED || ADRS. We will refer to toByte(3, 64) as OPCODE_3. The two calls are distinguished because the ADRS field which indicates the chain and location in the chain is computed differently in the two cases. First of all OPCODE_3||SEED is constant, that is the first 128 bytes are constant throughout the public key computation. Furthermore, at least the first 16 bytes of ADRS are constant, together providing 144 constant bytes.
[0088] For example, the address ADRS may be 32-byte OTS hash address as specified in Section 2.5 of RFC 8391. The OTS hash address may have the fields: layer address (32 bits), tree address (64 bits), type = 0 (32 bits), OTS address (32 bits), chain address (32 bits), hash address (32 bits), and keyAndMask (32 bits). In an embodiment, the fields layer address, tree address, and type, are constant.
[0089] Accordingly, choosing the SHA3 function SHAKE256 for this public key computation yields one constant block throughout the computation, of 136 bytes. Precomputing this block and storing the SHA3 states saves two SHA3 calls for each element in the chains.
[0090] Choosing the SHA3 function SHA3-512 for this public key computation yields two constant blocks throughout the computation, of 72 bytes each. Precomputing this block and storing the SHA3 states saves four SHA3 calls for each element in the chains.
[0091] Signature generation: A private key (e.g., sk) corresponding to a public key (e.g., pk) may be used to generate a signature (e.g., sig). To compute a signature for a message comprising a sequence of values, one may compute as follows for each value in the sequence of values in the message.
[0092] Repeatedly the chain function is applied to the corresponding value in the private key as many times as indicated by the corresponding value in the message. The signature comprising the final computed value in the chain for each private key value.
[0093] The same chain function is used for signing a message as for generating the public key (e.g., pk). Accordingly, the same advantages due to constant initial blocks apply to the signing of a message as well. In an embodiment, at least a first block of the string hashed in the chain function is constant during the computing of the chains. This constant block(s) is precomputed for the sponge function.
[0094] In an embodiment, a checksum may be included in the message to ensure that the signature cannot be tampered with. A simple checksum is shown in RFC 8391, which is appended to the message. Other types of checksums could be used.
[0095] For example, generating a signature from a private key may use algorithm 5 of RFC 8391. The core part of this function
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS);
}
Note that the third parameter msg[i] indicates the number of iterations, which for a public key computation would be w-1 (w being the Winternitz parameter, e.g., the maximum value of msg[i]+1).
[0096] A different number of iterations is possible. For example a permutation function p may be applied to msg[i], e.g., p(msg[i]), which may then be used as the number of iterations in both the signing and verifying algorithm. This would provide a valid signature scheme—though not conforming to RFC 8391.
[0097] The signature (e.g., sig) may be verified using the public key (e.g., pk). For each value in the sequence of values in the signature, a temporary public key value is computed by applying the chain function to each value in the signature as many times as indicated by the difference between a predetermined maximum value and the corresponding value in the message. The value derived from the temporary public key values to the public key is used to determine the validity of the signature. If the temporary public key is equal to the public key, the signature is considered valid.
[0098] For example, this may use algorithm 6 in RFC 8391. The core part of this algorithm is
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS);
}
Note that the signature verification should include the same checksum included during signature generation.
[0099] Note that the third parameter w - 1 - msg[i] indicates the number of iterations, which for a public key computation would be w-1. Note that the sum of the number of iterations done during signature generation for a message value plus the number of iterations done during signature verification equals the number of iterations done during public key generation. This principle may be extended to create an arbitrary number of different signature/verification schemes.
[0100] Both signature verification and generation use the chain function, which includes a constant block for SHAKE256, and two for SHA3-512 and so benefits from precomputation.
[0101] The algorithms have been described in the context of use-once signature schemes. This is not necessary though. An XMSS signature scheme combines many private keys into one public key, thus saving space, though at the expense of additional computation.
[0102] Figure 3 schematically shows an example of an embodiment of a multi-use public key computation 300. Figure 3 shows a tree. At 301 there are a number of use-once public keys according to an embodiment. At the right of figure 3, the bottom of layer 301, are the elements of the private keys (e.g., sk) 210. Above the private key elements are their corresponding chains 220, and the top of layer 301, are the elements of the public keys (e.g., pk) 230. At 302 and 303 the public key values are combined according to a Merkle tree, culminating in a Merkle tree root 304. The part 302 of the trees that correspond to exactly one use-once public key are called the L-tree. The part 303 is called the Hash tree. The L-trees and Hash tree from a Merkle tree. Accordingly, the signature scheme may be called a Merkle Signature Scheme.
[0103] To compute the tree for multiple private keys (e.g., sk0, sk1,…, sk2^h-1 also referred to as the WOTS+ private keys), first the corresponding public keys (e.g., pk0, pk1,…, pk2^h-1 also referred to as the WOTS+ public keys) are computed. This may use an embodiment as described herein, e.g., with respect to figure 2b.
[0104] Next a Merkle tree of hash values is computed, starting from the values in the public keys, that is the final values in the chains computed from the private key values sk[i]. A Merkle tree is computed by repeatedly computing a hash value on a next level of the tree by applying a tree function to two hash values on a lower level of the tree.
[0105] The tree function may comprise
- applying a fourth pseudo-random function (PRF) to generate a key,
- applying a fifth PRF to generate a first bitmask,
- applying a sixth PRF to generate a second bitmask.
- XOR-ing the first bitmask with a first value on the lower level of the tree,
- XOR-ing the second bitmask with a second value on the lower level of the tree,
- applying a SHA3 hash function to a concatenation of an opcode (e.g., OPCODE_1), the key, the first XOR result, and the second XOR result.
[0106] The fourth, fifth, and sixth PRF comprise applying a SHA3 hash to a string starting with an opcode, a public seed, and an address. For example, the string may comprise in order a concatenation of: an opcode, a public seed, and an address. As the opcode and public seed for n=64, are each 64 bytes, the first 128 bytes of the PRFs are constant throughout the tree computation. Of the address, the first 16 bytes are constant as well. This means that in total 144 bytes are constant.
[0107] This means that for SHA3-512, which has an input block size r=72 bytes, the first two blocks are constant. This means that for SHAKE256, which has an input block size r=136 bytes, the first block is constant. The sponge function for this block may be precomputed, and all other calls to the fourth, fifth and sixth PRFs may start from the precomputed state, and start absorbing the next blocks, e.g., third block for SHA3-512, and second block for SHAKE256.
[0108] The key, first bitmask and second bitmask are then used to combine two values on a lower level of the tree to obtain a value on the next higher level of the tree. For example as indicated above in the final three bullet points.
[0109] The public key (e.g., PK) may be derived from the root value of the Merkle tree. The rest of the tree as shown in figure 3, need not be part of the public key. Also in the computations for the hash tree, in particular, when applying the fourth PRF, fifth PRF and sixth PRF may start with at least a first constant block, which may be precomputed.
[0110] An example of an XMSS key generation, which is an example of such a tree as above, is given in RFC 8391, algorithm 10, calling algorithms 8, 9, which in turn call the algorithm 7, the RAND_HASH algorithm. This algorithm comprises the following lines:
KEY = PRF(SEED, ADRS);
BM_0 = PRF(SEED, ADRS);
BM_1 = PRF(SEED, ADRS);
node = H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1);

Using for the PRF and H functions the definitions in section 5.1, adapted to SHA3
H: SHA3-512(toByte(1, 64) || KEY || M),
PRF: SHA3-512(toByte(3, 64) || KEY || M)
toByte(1, 64) and toByte(3, 64) are used as the opcode.
[0111] The three calls to PRF each expand to a SHA3 call on a string of the form OPCODE||SEED||ADRS. The first two of which are constant. Of the address ADRS, the first 16 bytes are constant as well. That is the first 144 bytes are constant, e.g., 2*64+16 bytes. This means that if SHA3 is SHAKE256, the first block is constant throughout the public key computation, and if the SHA3 is SHA3-512, the first 2 blocks are constant.
[0112] A multi-use computation according to RFC 8391 may use three different addresses, according to section 2.5. The address included in the public key computations for the individual use-once private keys may use an OTH hash address. To combine the public key for one individual use-once private key into a single value—the L-tree—a different address scheme (e.g., L-Tree Address) may be used. The L-tree address comprises, in order: layer address (32 bits), tree address (64 bits), type = 1 (32 bits), L-tree address (32 bits), tree height (32 bits), tree index (32 bits), and keyAndMask (32 bits). Also here the first 16 bytes are constant. Finally, the combination of the L-tree roots, sometimes referred to as the Hash tree, uses Hash tree addresses having the fields: layer address (32 bits), tree address (64 bits), type = 2 (32 bits), Padding = 0 (32 bits), tree height (32 bits), tree index (32 bits), and keyAndMask (32 bits). Also here the first 16 bytes are constant.
[0113] Signing a message for verification with a multi-use public key comprises the same signature computation as for a single use key which is part of the multi-use tree. This provides the same advantages as for single-use signature computation.
[0114] To verify a signature using a multi-use public key may comprise computing a temporary public key as is done for verifying with a single use public key. However, instead of directly comparing public key with the temporary public key, a value is derived from both—the Merkle tree root. A multi-use public key comprises the Merkle tree root. A temporary Merkle tree root is computed from the temporary public key using additional values which allow this computation, the so-called authentication path (e.g., AUTH), which is provided with the signature. The computing of authentication path (e.g., AUTH) requires computing of the intermediate nodes of the Hash tree 303. The computing of authentication path requires generating the entire Merkle tree, but due to the optimization by BDS08 Algorithm, the execution cost is substantially reduced at the price of storage memory. See, “Merkle Tree Traversal Revisited”, by Johannes Buchmann, Erik Dahmen & Michael Schneider, part of the Lecture Notes in Computer Science book series (LNCS, volume 5299). Furthermore, the above mentioned optimizations are applicable for generating WOTS+ private keys (e.g., sk), computing WOTS+ public keys (e.g., pk), computing the L-tree and then combining several L-trees to form the intermediate node of the Hash tree. By comparing the Merkle tree root to the temporary Merkle tree root the validity of the signature is determined.
[0115] Figure 4a schematically shows an example of an embodiment of a method 400 to compute a public key corresponding to a private key of a SHA3-based signature scheme. Method 400 comprises
- obtaining (405) the private key, the private key comprising a sequence of random values (e.g., sk[0], sk[1], sk[2], …, sk[len-1]),
- computing (410) a set of chains by, for each value in the sequence of random values in the private key, computing a chain of hash values starting from the value by repeatedly applying a chain function to a previous value in the chain, the chain function comprising
- applying (411) a first pseudo-random function (PRF) to generate a key, e.g., KEY = PRF(SEED, ADRS);
- applying (412) a second PRF to generate a bitmask, wherein the first and second PRF comprise applying a SHA3 hash to a string starting with a concatenation of: an opcode (e.g., OPCODE_3), a public seed (e.g., SEED), and an address (e.g., ADRS), e.g., BM = PRF(SEED, ADRS); For example, opcode, public seed and a few starting bytes of the address may together be longer than the input block size of the SHA3 hash function, e.g., they may each be 64 bytes for n=64.
- XOR-ing (413) the bitmask with the previous value in the chain, e.g., tmp;
- applying (414) a SHA3 hash function to a concatenation of an opcode (e.g., OPCODE_0), the key and the XOR result, e.g., tmp = F(KEY, tmp XOR BM), and
- deriving (420) the public key from the final value for each of the chains,
- wherein the SHA3 function comprises a sponge function to iteratively receive one or more inputs blocks of the string, and a squeeze function to iteratively generate one or more output blocks, at least a first block of the string being constant during the computing of the chains, the method further comprising precomputing the sponge function on the constant at least a first block.
[0116] Figure 4b schematically shows an example of an embodiment of a method 430 to compute a public key (e.g., PK) corresponding to a private key in a SHA3-based Merkle Signature Scheme. Method 430 comprise
- obtaining (440) multiple private keys (e.g., sk0, sk1,…, sk2^h-1), and generating therefor multiple sets of chains,
- computing (450) a Merkle tree of hash values, starting from the final values of each of the chains in each of the multiple sets, and repeatedly computing a hash value on a next level of the tree by applying a tree function to two hash values on a lower level of the tree, the tree function comprises

- applying (451) a fourth pseudo-random function (PRF) to generate a key, e.g., KEY = PRF(SEED, ADRS);
- applying (452) a fifth PRF to generate a first bitmask, e.g., BM_0 = PRF(SEED, ADRS);
- applying (453) a sixth PRF to generate a second bitmask, e.g., BM_0 = PRF(SEED, ADRS);wherein the fourth, fifth, and sixth PRF comprise applying a SHA3 hash to a string starting with an opcode (e.g., OPCODE_3), a public seed (e.g., SEED), and an address (e.g., ADRS). For example, opcode, public seed and a few starting bytes of the address may together be longer than the input block size of the SHA3 hash function, e.g., they may each be 64 bytes for n=64.
- XOR-ing (454) the first bitmask with a first value on the lower level of the tree, e.g., left,
- XOR-ing (455) the second bitmask with a second value on the lower level of the tree, e.g., right,
- applying (456) a SHA3 hash function to a concatenation of an opcode (e.g., OPCODE_0), the key, the first XOR result, and the second XOR result, e.g., node = H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); and
- deriving (460) the public key from the root value of the Merkle tree,
- wherein, at least a first block of the string being constant during the computing of the tree, the method further comprising precomputing the sponge function on the constant at least a first block.
[0117] Many different ways of executing methods according to an embodiment are possible, including those of figure 4a and 4b, as will be apparent to a person skilled in the art. For example, the order of the steps can be performed in the shown order, but the order of the steps can be varied or some steps may be executed in parallel. Moreover, in between steps other method steps may be inserted. The inserted steps may represent refinements of the method such as described herein, or may be unrelated to the method. For example, some steps may be executed, at least partially, in parallel. Moreover, a given step may not have finished completely before a next step is started.
[0118] Embodiments of the method may be executed using software, which comprises instructions for causing a processor system to perform a method according to an embodiment, e.g., method 400 and/or 430. Software may only include those steps taken by a particular sub-entity of the system. The software may be stored in a suitable storage medium, such as a hard disk, a floppy, a memory, an optical disc, etc. The software may be sent as a signal along a wire, or wireless, or using a data network, e.g., the Internet. The software may be made available for download and/or for remote usage on a server. Embodiments of the method may be executed using a bitstream arranged to configure programmable logic, e.g., a field-programmable gate array (FPGA), to perform the method.
[0119] It will be appreciated that the presently disclosed subject matter also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the presently disclosed subject matter into practice. The program may be in the form of source code, object code, a code intermediate source, and object code such as partially compiled form, or in any other form suitable for use in the implementation of an embodiment of the method. An embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the processing steps of at least one of the methods set forth. These instructions may be subdivided into subroutines and/or be stored in one or more files that may be linked statically or dynamically. Another embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the devices, units and/or parts of at least one of the systems and/or products set forth.
[0120] Figure 5a shows a computer readable medium 1000 having a writable part 1010, and a computer readable medium 1001 also having a writable part. Computer readable medium 1000 is shown in the form of an optically readable medium. Computer readable medium 1001 is shown in the form of an electronic memory, in this case a memory card. Computer readable medium 1000 and 1001 may store data 1020 wherein the data may indicate instructions, which when executed by a processor system, cause a processor system to perform an embodiment of a method of private key generation, public key generation, signature generation, signature verification according to an embodiment. The computer program 1020 may be embodied on the computer readable medium 1000 as physical marks or by magnetization of the computer readable medium 1000. However, any other suitable embodiment is conceivable as well. Furthermore, it will be appreciated that, although the computer readable medium 1000 is shown here as an optical disc, the computer readable medium 1000 may be any suitable computer readable medium, such as a hard disk, solid state memory, flash memory, etc., and may be non-recordable or recordable. The computer program 1020 comprises instructions for causing a processor system to perform said method of private key generation, public key generation, signature generation, signature verification.
[0121] Figure 5b shows in a schematic representation of a processor system 1140 according to an embodiment of system configured for one or more of private key generation, public key generation, signature generation, signature verification. The processor system comprises one or more integrated circuits 1110. The architecture of the one or more integrated circuits 1110 is schematically shown in Figure 5b. Circuit 1110 comprises a processing unit 1120, e.g., a CPU, for running computer program components to execute a method according to an embodiment and/or implement its modules or units. Circuit 1110 comprises a memory 1122 for storing programming code, data, etc. Part of memory 1122 may be read-only. Circuit 1110 may comprise a communication element 1126, e.g., an antenna, connectors or both, and the like. Circuit 1110 may comprise a dedicated integrated circuit 1124 for performing part or all of the processing defined in the method. Processor 1120, memory 1122, dedicated IC 1124 and communication element 1126 may be connected to each other via an interconnect 1130, say a bus. The processor system 1110 may be arranged for contact and/or contact-less communication, using an antenna and/or connectors, respectively.
[0122] For example, in an embodiment, processor system 1140, e.g., the system configured for one or more of method of private key generation, public key generation, signature generation, signature verification may comprise a processor circuit and a memory circuit, the processor being arranged to execute software stored in the memory circuit. For example, the processor circuit may be an Intel Core i7 processor, ARM Cortex-R8, etc. The memory circuit may be an ROM circuit, or a non-volatile memory, e.g., a flash memory. The memory circuit may be a volatile memory, e.g., an SRAM memory. In the latter case, the device may comprise a non-volatile software interface, e.g., a hard drive, a network interface, etc., arranged for providing the software.
[0123] While device 1140 is shown as including one of each described component, the various components may be duplicated in various embodiments. For example, the processor 1120 may include multiple microprocessors that are configured to independently execute the methods described herein or are configured to perform steps or subroutines of the methods described herein such that the multiple processors cooperate to achieve the functionality described herein. Further, where the device 1140 is implemented in a cloud computing system, the various hardware components may belong to separate physical systems. For example, the processor 1120 may include a first processor in a first server and a second processor in a second server.
[0124] It should be noted that the above-mentioned embodiments illustrate rather than limit the presently disclosed subject matter, and that those skilled in the art will be able to design many alternative embodiments.
[0125] In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. Use of the verb ‘comprise’ and its conjugations does not exclude the presence of elements or steps other than those stated in a claim. The article ‘a’ or ‘an’ preceding an element does not exclude the presence of a plurality of such elements. Expressions such as “at least one of” when preceding a list of elements represent a selection of all or of any subset of elements from the list. For example, the expression, “at least one of A, B, and C” should be understood as including only A, only B, only C, both A and B, both A and C, both B and C, or all of A, B, and C. The presently disclosed subject matter may be implemented by hardware comprising several distinct elements, and by a suitably programmed computer. In the device claim enumerating several parts, several of these parts may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.
[0126] In the claims references in parentheses refer to reference signs in drawings of exemplifying embodiments or to formulas of embodiments, thus increasing the intelligibility of the claim. These references shall not be construed as limiting the claim.
, Claims:We Claim:
1. A method (400) to compute a public key (e.g., pk) corresponding to a private key (e.g., sk) of a SHA3-based (e.g., SHA3-512) signature scheme, the method comprising
- obtaining (405) the private key, the private key comprising a sequence of random values (e.g., sk[0], sk[1], sk[2], …, sk[len-1]),
- computing (410) a set of chains by, for each value in the sequence of random values in the private key, computing a chain of hash values starting from the value by repeatedly applying a chain function to a previous value in the chain, the chain function comprising
- applying (411) a first pseudo-random function (PRF) to generate a key,
- applying (412) a second PRF to generate a bitmask, wherein the first and second PRF comprise applying a SHA3 hash to a string starting with a concatenation of: an opcode (e.g. OPCODE_3), and a public seed (e.g., SEED),
- XOR-ing (413) the bitmask with the previous value in the chain;
- applying (414) a SHA3 hash function to a concatenation of an opcode (e.g., OPCODE_0), the key and the XOR result, and
- deriving (420) the public key from the final value for each of the chains,
- wherein the SHA3 function comprises a sponge function (e.g., f) to iteratively receive one or more inputs blocks of the string, and a squeeze function to iteratively generate one or more output blocks, at least a first block of the string being constant during the computing of the chains, the method further comprising precomputing the sponge function on the constant at least a first block.

2. The method of Claim 1, wherein obtaining the private key (e.g., sk) comprises
- generating the sequence of random values (e.g., sk[0], sk[1], sk[2], …, sk[len-1]) by repeatedly applying a third PRF, wherein the third PRF comprises applying a SHA3 hash to a string starting with a concatenation of: an opcode (e.g., OPCODE_4), and a secret seed (e.g., SK_SEED), and optionally the public seed (e.g., SEED), wherein at least a first block of the string is constant during the computing of the private key, the method further comprising precomputing the sponge function on the constant at least a first block.

3. The method of Claim 1, wherein the string starts with a concatenation of: an opcode (e.g. OPCODE_3), a public seed (e.g., SEED), and an address (e.g., ADRS), the address in the concatenated string for a pseudo-random function (PRF) identifying a specific position in the sequence of random values of the private key, wherein the opcode, secret seed, public seed, and an initial part of the address is constant.

4. The method of Claim 2, wherein the string start with a concatenation of: an opcode (e.g., OPCODE_4), and a secret seed (e.g., SK_SEED), optionally the public seed (e.g., SEED), and an address, the address in the concatenated string for a pseudo-random function (PRF) identifying a specific position in the sequence of random values of the private key and chains, wherein the opcode, secret seed, public seed, and an initial part of the address is constant.

5. The method (430) of any of the preceding claims, wherein the signature scheme is a Merkle Signature Scheme, the method computing a public key for multiple uses, the method comprising
- obtaining (440) multiple private keys (e.g., sk0, sk1,…, sk2^h-1), and generating therefor multiple sets of chains,
- computing (450) a Merkle tree of hash values, starting from the final values of each of the chains in each of the multiple sets, and repeatedly computing a hash value on a next level of the tree by applying a tree function to two hash values on a lower level of the tree, the tree function comprises
- applying (451) a fourth pseudo-random function (PRF) to generate a key,
- applying (452) a fifth PRF to generate a first bitmask,
- applying (453) a sixth PRF to generate a second bitmask, wherein the fourth, fifth, and sixth PRF comprise applying a SHA3 hash to a string starting with an opcode (e.g., OPCODE_3), a public seed SEED, and an address ADRS,
- XOR-ing (454) the first bitmask with a first value on the lower level of the tree,
- XOR-ing (455) the second bitmask with a second value on the lower level of the tree,
- applying (456) a SHA3 hash function to a concatenation of an opcode (e.g., OPCODE_1), the key, the first XOR result, and the second XOR result, and
- deriving (460) the public key (e.g., PK) from the root value of the Merkle tree,
- wherein, at least a first block of the string being constant during the computing of the tree, the method further comprising precomputing the sponge function on the constant at least a first block.

6. The method of any of the preceding claims, further comprising generating a signature for a message using the private key, the method comprising
- obtaining the message, the message comprising a sequence of values,
- for each value in the sequence of values in the message, repeatedly computing the chain function for each value in the private key as many times as indicated by the corresponding value in the message, the signature comprising the final computed value in the chain for each private key value, wherein at least a first block of the string hashed in the chain function being constant during the computing of the chains, the method further comprising precomputing the sponge function on the constant at least a first block.

7. The method of any of the preceding claims, further comprising verifying a signature for a message using the obtained private key, the method comprising:
- receiving the signature and the message, wherein the signature comprises a sequence of values corresponding to the message,
- for each value in the sequence of values in the signature, computing a temporary public key value by applying the chain function to each value in the signature as many times as indicated by the difference between a predetermined maximum value and the corresponding value in the message,
- comparing a value derived from the temporary public key values to the public key to determine the validity of the signature.

8. The method of any one of Claims 1-5, wherein the SHA3-based function is either SHA3-512 or SHAKE256.

9. A method to compute a private key (e.g., sk) of a SHA3-based (e.g., SHA3-384) signature scheme, the method comprising
- obtaining the private key, the private key comprising a sequence of random values (e.g., sk[0], sk[1], sk[2], …, sk[len-1]), obtaining the private key comprising generating the sequence of random values by repeatedly applying a third PRF, wherein the third PRF comprises applying a SHA3 hash to a string comprising in order a concatenation of: an opcode, a secret seed, the public seed, an address, and padding, wherein at least a first block of the string is constant during the computing of the private key, the method further comprising precomputing the sponge function on the constant at least a first block.

10. The method of Claim 9, wherein the SHA3-based function is SHA3-384.

11. A system comprising: one or more processors; and one or more storage devices storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations for any of claims 1-10.

12. A transitory or non-transitory computer readable medium (1000) comprising data (1020) representing instructions, which when executed by a processor system, cause the processor system to perform the method according to any of claims 1-10.