Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new postquantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution.MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm.At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speedup of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.
Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new postquantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution.MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm.At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speedup of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.
The advent of quantum computers poses a direct threat to the security of traditional digital signature schemes, which are based on the Rivest–Shamir–Adleman (RSA) and Elliptic Curve Cryptography (ECC) cryptosystems. Shor's algorithm allows solving the Discrete Logarithm Problem (DLP) in polynomial time, whereas Grover's algorithm significantly reduces the effort required for brute-force attacks on symmetric hash functions and ciphers. Although many post-quantum solutions have been proposed, such as lattice-based schemes (e.g., CRYSTALS-Dilithium, Falcon) or hash-based schemes (e.g., SPHINCS+), they still have some limitations to overcome, such as large public keys, bulky signatures, high computational costs, and difficulties in integrating into existing Public Key Infrastructures (PKIs). In this paper, we propose a new type of hard problem, defined over a finite prime field, in which the generator is kept secret to prevent any direct Shor attack and is only subject to a limited influence from Grover. Based on this newly proposed hard problem, we construct a post-quantum digital signature scheme that is both Shor-resistant and Grover-resistant, secure against classical attacks, and fully compatible with current PKI infrastructures. Compared with existing post-quantum digital signature schemes, our solution significantly optimizes the size of public keys and signatures while increasing the speed of signing and verification. The newly proposed hard problem cannot be solved by known classical or quantum algorithms, thus ensuring long-term security. Performance evaluation results show that the scheme provides an optimal balance between performance and security, opening up a cost-effective implementation path for the post-quantum cryptography era.
The rise of quantum computing threatens to break many of the cryptographic systems that secure today’s digital world. In response, researchers are developing new tools designed to remain secure in a post-quantum future. Most of the promising candidates for post-quantum digital signatures rely on security assumptions based on lattices or properties of hash functions. Another promising approach transforms secure multi-party computation protocols into zero-knowledge proofs, which are then turned into digital signatures. This technique, known as multi-party computation in-the-head (MPCitH), offers strong security properties and flexibility for distributed applications. This thesis investigates whether MPCitH digital signatures can be efficiently adapted for use by two cooperating parties to jointly produce a signature. Here we show how to construct two-party signatures based on syndrome decoding in-the-head (SDitH) signatures. We propose a provably secure scheme that achieves the smallest known communication overhead among two-party MPCitH signatures, while resulting in a signature size approximately double that of a single-prover variant. This result provides a new data point in the design space of multi-party MPCitH signatures and post-quantum digital signatures in general.
Public key cryptography plays a pivotal role in maintaining digital security and privacy, with its foundations built on the hardness of certain mathematical problems. However, the emergence of quantum computing threatens the security of current cryptographic systems, making the adoption of post-quantum cryptography (PQC) an urgent necessity. Digital signature schemes are essential components in secure communications, providing authentication, non-repudiation, and data integrity. This paper examines the state of post-quantum digital signature schemes across various cryptographic approaches, including lattice-based, code-based, multivariate polynomial-based, hash-based, symmetric-key-based, and isogeny-based systems, alongside advancements in Multi-Party Computation in the Head (MPC-in-the-head) schemes. The paper then explores application-specific signatures such as blind, undeniable, threshold, chameleon, aggregate, and ring signatures, explaining their main use cases and the existing post-quantum cryptographic classifications that support these constructions individually. Software implementations of selected prominent PQC digital signature schemes were carried out, and their performance was systematically analysed using metrics such as bandwidth consumption, latency, and computational efficiency. These results provide key observations regarding the suitability of different schemes for both resource-constrained and high-performance environments. Subsequently, a detailed literature review of implementations on embedded and hardware platforms is presented, focusing on ARM-based devices and FPGA accelerators to evaluate deployment feasibility beyond general-purpose processors. Based on the software and implementation-level findings, a comparative analysis across software, embedded, and hardware platforms is conducted to highlight architectural influences on performance, scalability, and practicality. Furthermore the cryptanalytic attacks on post-quantum digital signature schemes across various PQC classifications are examined in this paper, taking into account both classical and quantum adversarial models. To evaluate realistic security constraints, implementation-oriented vulnerabilities such as side-channel and fault-based attacks are also examined. In addition, the applicability of post-quantum digital signature schemes within TLS, IoT, and related practical deployment scenarios is analysed. The study also discusses possible directions for further investigation, focusing on the requirement for effective and expandable PQC systems that can satisfy changing cybersecurity requirements. In order to protect sensitive data in the digital era, this study emphasizes the need for implementing quantum-secure systems by fusing theoretical understandings with real-world applications.
With the advancement of quantum computing, conventional digital signature algorithms such as RSA and El-Gamal are increasingly vulnerable to quantum attacks. This presents a significant challenge for ensuring the security and integrity of electronic signatures. As a result, there is a need to develop post-quantum signature algorithms that can withstand attacks from quantum computers while maintaining computational efficiency. This study proposes a novel modification of the Merkle post-quantum signature scheme, integrating an optimized version of Lamport’s one-time signature algorithm. The core contribution of this work is the design and implementation of a new algorithm that significantly reduces signature verification time without compromising cryptographic strength. A software implementation of the modified scheme was developed using Python and the PyQt 6 library, allowing for practical testing and analysis. The performance of the modified algorithm was compared against the standard Lamport algorithm using execution time measurements and statistical analysis. The experimental results demonstrate that the modified algorithm significantly improves signature verification speed, reducing the time required by up to 44.81% compared to the standard algorithm. The study presents a more efficient post-quantum Merkle signature scheme with a modified Lamport algorithm that enhances signature verification speed while maintaining strong cryptographic security. The results suggest that the proposed scheme is particularly well-suited for environments where fast authentication of multiple digital signatures is required. Experimental results confirm the advantage of the proposed approach, offering a more efficient solution for secure, high-speed digital authentication in post-quantum environments
In order to meet the challenges brought by quantum computing, research on post-quantum cryptography has been carried out comprehensively. Among them, the most influential one is the post-quantum cryptography algorithm standardization project initiated by NIST. In July 2022, NIST announced that the Dilithium, Falcon, and SPHINCS+ algorithms were selected as candidate schemes for the standardization of post-quantum cryptographic digital signatures. The OQS project team is committed to promoting the transition of existing security protocols to standardized post-quantum algorithms and is currently the mainstream open-source post-quantum project. This paper improves the post-quantum hybrid digital signature scheme used by the OQS project team. Firstly, the hybrid digital signature scheme used in this project is studied, and it is found that there are security risks. Subsequently, an enhanced scheme is constructed and implemented using the hybrid algorithm combiner proposed by Nina Bindel et al., solving the security issues. The unforgeability and 2 -non-separability of the enhanced scheme are verified through formal analysis, and forward compatibility is achieved. The enhanced scheme shows obvious advantages in key generation efficiency and signature verification efficiency. Under some algorithms, the speed of signature verification of the improved scheme is 60 % of the original scheme. Meanwhile, the enhanced scheme also demonstrates stability in terms of time and storage overhead. Finally, the TLS1.3 protocol PSK mechanism is implemented using the enhanced scheme. This is the first implementation of post-quantum algorithm security protection in the PSK mechanism of the TLS protocol. This scheme can resist man-in-the-middle attacks while meeting the requirements of forward compatibility.
Recently, NIST released the quantum cryptography standard, which includes three new encryption algorithms capable of effectively resisting attacks from quantum computers. Experts predict that quantum computers with the ability to break current encryption methods may emerge within the next decade. In particular, the advent of Shor’s algorithm [1] has rendered public-key encryption systems based on factoring and discrete logarithm problems vulnerable. Therefore, the release of the PQC (Post-Quantum Cryptography) standard is especially timely and significant. NIST encourages system administrators to begin integrating these standards into their systems immediately to ensure future security.Among these three new encryption algorithms, SLH-DSA (derived from SPHINCS+ [2]) is a stateless hash-based digital signature scheme. This innovative scheme is designed to provide robust security while maintaining efficiency. In the SLH-DSA signature scheme, the One-Time Signature (OTS) serves as its fundamental building block. This means that improving the OTS directly enhances the overall performance of the SLH-DSA scheme.Hash-based signature schemes are generally constructed using OTS schemes. The underlying OTS scheme plays a crucial role in determining the key size and signature size of hash-based signature schemes. We propose a novel signature scheme that allows partial key reuse while maintaining a minimum quantum security level of 128 bits. Compared to the popular Winternitz OTS scheme [3] [4] [5], our proposed signature scheme demonstrates superior performance in terms of key and signature sizes for the same number of signatures, while still preserving post-quantum security.