On the Role of Hash-based Signatures in Quantum-Safe Internet of Things: Current Solutions and Future Directions

Among the stateful signature schemes, OTS schemes form a fundamental building block for HBS. Common examples of seminal OTS are Lamport-Diffie scheme [25], Winternitz scheme [26], and its variants WOTS⁺ [27], WOTS^PRF. To sign a message with OTS schemes, the private key is uniformly generated at random, whereas the public key is derived as a function of the private key, involving the underlying hash function.

Lamport-Diffie scheme provides very strong security on minimal assumptions; however, it has some major downsides which prevented its wide adoption. Firstly, it is one-time, making it in-apposite for the majority of use cases of digital signatures. Secondly, the keys and the signatures are extremely large (as shown in Table IV). The deterring issue of extremely large key length and signature size in the Lamport-Diffie scheme is resolved through WOTS by introducing a Winternitz parameter that controls time/memory trade-off. Therefore, reducing the space required for keys and signatures makes WOTS a good choice for memory-constrained embedded devices (and hence IoT), but at the cost of slower signing and verifying process. Overall, OTS schemes are single-use in nature (i.e., can only sign a pre-defined number of messages with a key pair, which introduce a key renewal overhead) and therefore inadequate to use in real-world applications. This is because using the same key multiple times may enable an attacker to reveal more parts of the private key, and hence compromise the security of the underlying scheme.

To untangle the peculiarity of the one-time nature of OTS schemes, MTS schemes are proposed to construct many-time signatures by using OTS as an under-structure. In [30], Ralph Merkle proposed Merkle Signature Scheme (MSS) to generate multiple aggregated public and private keys by combining a large number of OTS key pairs into a single binary hash tree structure (as shown in Fig. 2). To authenticate the relation of a one-time public key with the global public key (also referred to as tree root), signatures keep on appending a sequence of intermediate tree nodes, called authentication paths (as shown in Fig. 2). Such paths allow the validator to reconstruct the path from the relevant one-time public key to the tree’s root upon signature verification. To enhance the efficacy and practicability of MSS, the following optimization strategies are adopted based on different flavors of Merkle tree construction, leaves calculation, and parameter specifications. Firstly, the global private key can be efficiently constructed by using a cryptographically secure Pseudo-Random Number Generator (PRNG) such that from an initial seed value (which acts as a private key), both successive seeds and one-time secret keys are derived. Thus, in lieu of storing all OTS secret keys, it is sufficient to store only the seed value of the PRNG, while generating other seed values on-the-fly. It ultimately minimizes storage requirements. Such a strategy for global private key construction also provides forward secrecy and existential unforgeability under adaptive chosen message attack [31]. Nevertheless, it necessitates precise counter management for tracking the used keys, particularly across multiple invocations of signing algorithm, because using any one-time private key twice is imperative to security. Secondly, the performance-optimized BDS algorithm [32] is used for efficient computation of authentication path such that it caches the authentication path from the previous signature, thus, instigate time/memory trade-off. To this end, concrete examples of M-time signature schemes are Extended Merkle Signature Scheme (XMSS) [33],  [34], and  [35].

Although the use of the optimized BDS algorithm provides sufficient performance during the signature generation of XMSS implementation, it is still relatively slower in generating a new key pair due to the requirement of constructing the entire hash tree [31]. Hence, to further improve performance, HS schemes are proposed. In essence, HS schemes are MTS schemes that use other hash-based signatures in its construction. The idea of HS is based on the formation of a hyper-tree that involves tree chaining by using multiple layers of MSS tree. In this form of Merkle tree construction, the upper layers are used to sign the roots of the layers below while only the lowest layer is used to sign messages. Notable examples of HS are XMSS-Multi Tree (XMSS^MT) [36], XMSS with tightened security (XMSS-T) [37], and Leighton Micali Scheme (LMS) [34]. XMSS^MT is particularly ideal for applications that require virtually a large number of messages to be signed. Note that, XMSS^MT should be used in conjunction with other optimization strategies, including the BDS algorithm, PRNG, and caching of the authentication paths, otherwise the required storage and the long time for random number generation outweigh the performance gain of XMSS^MT. Additionally, the LMS has two variants, i.e., Leighton Micali one-time signature (LM-OTS) and the many-time signature scheme LMS [38].

Some of the examples of the stateless HS scheme are SPHINCS [40] and its variants SPHINCS-Simpira [41], Gravity-SPHINCS [15], and SPHINCS⁺ [42]. Similar to XMSS^MT, SPHINCS uses a hypertree such that the upper layers use XMSS with WOTS⁺ to sign roots of their ancestors, while the lowest layer uses a Merkle tree construction with HORS-T for signing messages(as shown in Fig. 3). Since the stateless schemes do not keep a record of used key pairs, hence to ensure the correct few-time usage of key pairs, SPHINCS deploys multiple HORS-T key pairs and selects a random one for each signature generation. As a result, no path-state tracking is required.

Generating all HORS-T and WOTS⁺ private keys with a PRNG for key generation and computing one tree in each layer for signature generation results in the feasible computation for SPHINCS. Nevertheless, stateless schemes pose the following performance issues. Firstly, the signature generation is more expensive because the key pairs are used in random order rather than successive order; hence, the optimization algorithm BDS is no longer suitable. Secondly, in contrast to WOTS⁺, HORS-T signatures are relatively much larger. We summarize the stateless and stateful class of HBS schemes along with their signature size, key length, and other relevant details in Table IV and Table V.

Here we discuss technical challenges related to IoT devices with reference to quantum computing.

a) State Management: In the stateful signing algorithms schemes, state management is one of the challenging snags to the widespread use of HBS schemes. In this problem, the version of the private key in non-volatile memory (disk) must be continuously synchronized with that in volatile memory (RAM) to avoid key synchronization failure. Crash of an application or an operating system, corruption of the nonvolatile state, power outage, or a software bug could be among the potential causes of synchronization failure [11]. The delay caused by the synchronization of the private key between the storage unit and execution unit results in additional latency for the signature generation time, thus highly deteriorating the overall performance of the system.

b) Cloning: Another problem in the stateful signature scheme is cloning. Such type of risk occurs when a private key is copied and then used without coordination with execution units (known as non-volatile cloning) or without coordination with storage units (known as volatile cloning). Live Virtual Machine (VM) cloning or restoration of a key file to a previous state from a backup system could potentially cause volatile or non-volatile cloning. The cloning problem results in the generation of multiple signatures from the same system state, thus crucially undermining security. For instance, in case of live VM cloning, values that may only be used once, are at risk, including initialization vectors, pseudorandom numbers, counters for encryption, one-time passwords, and seeds for digital signatures [65]. Similarly, initial sequence numbers could be reused for hijacking in the case of the S/Key (a one-time password system) and the TCP protocol [11]. Issues with such primitives can be problematic even for classical digital signature schemes. To summarize, nonvolatile cloning may not cause any issue to a system devoted only to the signature generation; however, it can cause significant risk to the general-purpose software system. On the other hand, volatile cloning leads to catastrophic results particularly due to the vulnerabilities pertaining to caching of random numbers. Therefore, tailored to specific use-cases, the state management strategies must be gauged in a nuanced way. For instance, resource-constrained sensor nodes piggyback on UAVs for computation and processing of tasks (as shown in Fig. 5 (middle)). In this scenario, the issues of state management (either key synchronization or cloning risk), may cause problems including (i) performance issues at delivering results to control unit, (ii) energy issues at UAVs, and (iii) data integrity risks at the control unit.

Though stateless signing algorithms solve the state and key synchronization concerns; however, signature size is still a problem. To resolve the issues of stateless and stateful schemes, a hybrid approach discerns the essential worth with smaller signatures and faster signing deserves further exploration. Other possible solutions suggested in [11] include state reservation strategy and hierarchical signature schemes. Simply put, in a state reservation approach, the private key that is ahead of the current signature among the available $N$ signatures is written back into storage, thereby avoiding the need to write the updated private key into nonvolatile storage. In the case of a hierarchical signature scheme, a volatile bottom level enforces the reservation property such that the private key of the volatile level is not synchronized in nonvolatile storage. Such combined volatile/nonvolatile hierarchical signature scheme property avoids synchronization problems and is considered a reasonable model for problems related to writing operation scenarios such as power outage or crash of an application. However, both of these solutions do not address the nonvolatile cloning problem.

c) Specification of Parameters: Another issue is that the universal specification of a parameter set highly depending on the intended use-cases. Since constraints on performance aspects such as signing speed and key size are highly dependent on underlying use-cases, therefore, it is hard to define one universal parameter set for every scenario. For example, software update authentication does not entail high-frequency signing, however, the converse is true for Hypertext Transfer Protocol (HTTP) over Transport Layer Security (TLS). Another example is the individual user’s email signing that does not require frequent signing though, however, keeping in view the usability considerations, the priority is given to the signature size to limit message expansion [13].

HBS schemes need to offer concrete parameter choices to provide user guidance while considering constraints on performance aspects such as signing speed and key size. For concrete instantiations, proper guidance (rules and regulations with concrete steps) should be included in standards. In this regard, [66, 60] suggest concrete parameter sets and discuss the crucial element of security levels for the proposed parameter sets, however, unable to address their adequacy tailored to specific applications. Thus, the use of underlying hash function, state management strategies and other construction parameters must be evaluated in a nuanced way depending on the intended use-case as also discussed in subsection IV-A and IV-C. Though the recommended parameters should be provided by the cryptographic community; however, customizing signing speed, key size, and other construction parameters depending on the application scenario is a crucial asset.

d) Trade-off Between Excessive Data and Performance: Depending on the application and underlying infrastructure, a network of things may have a dynamic and rapidly changing dataflow and workflow where data inputs are provided from a variety of sources such as sensors, external databases or clouds, and other external subsystems. As the generation of vast amounts of data over time renders IoT systems as potential big data generators, in this regard, how can we ensure the speed and performance of underlying HBS schemes? One potential solution is to adopt hybrid HBS schemes to enable a trade-off between performance-constrained and resource-constrained environment. Besides, more efficient algorithms may open the way to application in the diverse and constrained reality of the vast majority of IoT devices.

Bringing quantum computing could enable advances in many futuristic technologies; however, it requires consideration of many significant factors. Here, we discuss non-technical challenges related to IoT devices with reference to quantum computing.

a) Business and Economic Setbacks: As the age of quantum computing is gradually dawning, it seems that new hardware systems are among constantly increasing requirements. Therefore, the question, how IoT devices can adapt to quantum computing with their current embedded hardware (such as crypto-processors) that is generally optimized to carry out certain cryptographic operations?, must be answered. However, the implications of such demands are likely to face huge business and economic setbacks in terms of expenditures on new or upgraded IoT infrastructures to handle the increased workload. Thus, bringing in new hardware may be too expensive for cost-sensitive large-scale applications that are usually looking forward to cost-effective solutions by drastically reducing capital expenditure (CapEX) and operational expenditure (OpEX).

b) Entanglement in Legacy Systems, Existing Applications, Standards, and Protocols: In addition to the aforementioned demand for new hardware systems, one of the substantial concern is how to retrofit legacy systems with advanced security solutions? Because shifting to novel quantum-based infrastructure for IoT demands fragile engineering environment, for example, temperature constraints for operating quantum infrastructure, the limited range for terrestrial quantum communication networks, the staggering cost of various hardware for carrying out QKD, budget funding, and other obstacles that may limit the usability of quantum-based systems at the moment.

Similarly, another question is how existing applications and protocols can adapt to quantum computing with their current standards? One solution is to modify the existing protocols to handle larger signature or key size by segmenting the data into multiple massages for bandwidth-constrained applications (e.g., self-driving cars). However, the status quo will change as new applications and protocols must set their standards keeping in mind the demands of quantum schemes. Existing protocols might need to be modified to handle larger signatures or key size, for example, through the segmentation of messages. Also, protocol designers should be aware that changes in the underlying cryptography may certainly be necessary for the future, either due to quantum computing or other unforeseen advances in cryptanalysis. For new applications, implementations must keep the demands of PQC in mind and allow the new schemes to adapt to them as PQC requirements might shape future application standards.

c) Heterogeneity in Terms of Application and System: Another unique characteristic of IoT devices is heterogeneity. On one hand, heterogeneity may appear in terms of divergent application requirements, for instance, resource constraints in sensor networks, security constraints for medical implantable devices, performance constraints for IIoT, etc. On the other hand, it may appear in terms of diversified architecture requirements, for instance, interoperability across diverse platforms from different vendors, integration of disparate sub-systems, and the existence of compatibility among sub-systems to work in conjunction without conflict. Possible solutions to handle heterogeneity is to consider interoperability and integration of systems or subsystems and to promote flexibility and include abstractions to facilitate integration among existing applications and libraries. The systems that have prescriptive requirements such as military-critical and safety-critical systems must consider all of these aspects while enforcing appropriate quantum-resistant algorithms upon careful identification of the system requirements (such as performance contracting).

d) Bridging The Gap: Integrating HBS with Well-known and Tested Cryptographic Libraries: Integrating HBS with well-known and tested cryptographic libraries plays an ergonomic role to ensure the wide availability of HBS in security infrastructures and serves the goal of absolute security shared by all stakeholders. Though in the case of HBS, proof-of-concept implementations exist such as [33, 67] which mark a necessary step towards their widespread usage. On a related note, such stand-alone implementations are unable to facilitate both technical interfacing and strategic decisions such as parameter selection. In [12], the authors suggested avoiding case-by-case implementation of cryptographic primitives as it is inopportune for organizations to develop their own specific ad hoc implementations and recommended the usage of commonly used software cryptographic libraries (such as Open SSL) particularly because of their ability to include abstractions to facilitate system integration and combination.

In the following, we discuss the social challenges faced by HBS in IoT networks.

a) Ethical and Moral Consequences: The access to large-scale quantum computers by the government institutions and other research funding organizations can be analyzed from ethical perspectives. For example, if access to quantum computers is limited to a few government agencies, they may dominate or dictate other nations (also referred to as the Big Brother Problem). Also, considering the risk that only a few big companies or corporate laboratories are able to afford quantum computers due to massive investment, the entrenched giant companies may use the efficiency gains to out-compete their competitors and thus lead to monopolies or oligopolies [68]. Even worse, the enterprises may use it with criminal intent such as industrial espionage for competitive advantage, mass-surveillance, and other undesirables. Furthermore, evildoers can harvest high-value data (such as medical data or sensitive government data) now and break it later by using quantum computers. The best way to make the impact of quantum computers positive is to enable their wide accessibility to people to run programs on them through the cloud. A toy version of such an idea with a 5-qubit computer through the cloud is provided by IBM’s Quantum Experience [69]. Similarly, to access quantum computing ecosystem platforms should be provided to enable academic researchers who are focused on theoretical work and tech-industry experts who are familiar with real-world performance needs and security demands to collaborate and share their experiences.

b) Skepticism in Quantum Computing: On one hand, there is an on-going race to build universal quantum computers along with a huge amount of scholarly literature and awareness about the potential societal impact on the breaking down of current-grade cryptography. On the other hand, the physical realization of quantum computers has been a hard slog that eventually raises serious doubts by quantum skeptics. The skeptics argued the possibility to build a scalable quantum computer due to various factors (such as noise, constraints on state preparation, unreliability, virtuous cycle, manufacturing errors, etc.) though they do agree that theoretically quantum computation does offer an exponential advantage of classical computation [70]. Gil Kalai, one of the most prominent quantum skeptics also argue against quantum computers due to several underlying facts related to noise in physical systems and quantum error correction [71].

According to the analysis given by [72], quantum computing needs to create a virtuous cycle, similar to that of the semiconductor industry, in order to generate a commercial demand by attaining sufficient economic impact and to fund the development of increasingly useful quantum computers as a major milestone. The same quandary goes for IoT devices, for instance, how ultra resource-constrained devices are going to adopt compute-intensive schemes, how to upgrade or replace IoT devices to carry out quantum-secure algorithms, etc. Also, from the software perspective, software developers must have enough knowledge of quantum theory to write code for the machines as quantum algorithms require a completely different way of thinking about problem-solving. In a net shell, keeping in view a rudimentary stage of evolution of quantum computers (in terms of hardware and software), most of the scientists are of the view to wait and see as a lot of work is needed to build post-quantum systems that are widely deployable while at the same time inspiring confidence.

c) Environmental Aspects: The computational and processing time required by the signing algorithm highly impacts the energy consumption by resource-constrained IoT devices which could ultimately make a somewhat noticeable environmental impact as the number of devices connected to the Internet is exponentially growing. To curtail such an impact on the environment, efficient signature algorithms should be used so to conserve energy which is beneficial for both scientific interests and environment interests [73]. Another environmental aspect is the upsurge in e-waste caused due to new hardware (such as crypto processors) as the existing devices or embedded components may not be able to efficiently go hand in hand with the quantum-safe algorithms. Moving to quantum-resistant crypto primitives which involve more computationally-intensive tasks may affect the performance of the current systems and even render some devices or components obsolete.

While we are still preparing for quantum-safe algorithms, but at the same moment, we have to protect the information that is already vulnerable; therefore, the overarching question is that, which defensive strategies should be adopted by the government to avoid significant geopolitical and diplomatic ramifications and corporate organizations to mitigate potential liabilities? In the following, we outline a few prudent measures and laying groundwork that must be adopted by the organizations to plan and prepare a quantum-secure IoT infrastructure.

• •

  Firstly, identify and document information assets (including business value, access control, data sharing arrangement, handling at end-of-life, backup and recovery procedures) and the current cryptographic protections (such as lengthening or maximizing current public key sizes) to determine the organization’s vulnerability to external and internal threats. Then the next step is to document the threat models and threat actors as follows:

  • –

    The threat models encompass critical infrastructure deployments and high inter-connectivity and inter-dependencies among devices, subsystems, and external third-party systems. The models must also recognize the requirement of lifetime systems that stretch over decades while others may refresh annually or more frequently.

  • –

    Identify threat actors and estimate their timeline to access and exploit quantum technology.

• •

  Secondly, a continuous evaluation based on an estimation of the lifecycle and field deployment conditions for such threat models is required as new technologies and attack vectors emerge.

• •

  Thirdly, investigate the impact of quantum technologies and conduct a Quantum Risk Assessment (QRA) on the underlying systems. In this regard, any cyber risk assessment must be periodically updated to account for emerging threats and to take advantage of improved security solutions as quantum technologies are not mature yet and are still rapidly evolving.

• •

  Fourthly, build crypto agility into systems to ensure an upgrade path and the ability to conduct remote upgrades in a secure, timely and pro-active manner.

• •

  Fifthly,

  • –

    from the hardware perspective, build devices and systems with long term security in mind, for instance, hardware-based key generation for adequate security of cryptographic operations throughout the lifetime of the device in the field. Another long-term solution could be to rely on quantum cryptographic methods to reduce hypothetical risk to business processes until quantum computing hardware becomes commoditized into solutions.

  • –

    from the software perspective, if possible, finding other PQC algorithms that can be used as drop-in replacements to make the transition less disruptive,

  • –

    software-as-a-service or third-party platform providers can also be commissioned for further assistance,

  • –

    perform the cost estimation of new or upgraded hardware and software systems. This may also involve equipping the organization personnel with practical quantum skills or even accessing a platform to learn world-class expertise and technology to advance the field of quantum computing.

• •

  Finally, after identifying and prioritizing the activities required to shift the organization’s technology to a quantum-safe state, keep track of governance infrastructure and migration plans that are required to respond to changes into systems in order to address immediate concerns while permitting the federation of new quantum technologies.

Thus, now and in the future, strategic thinking and long-term planning in terms of short-term remedies and small-scale fixes to repercussions of vulnerable information must be adopted for protecting sensitive information at banks and government databases until quantum-safe schemes will become fully available with pragmatic solutions and current infrastructures are rendered void.