Digital signatures based on the compact knapsack problem are attractive post-quantum candidates: they rely solely on integer arithmetic, require no algebraic ring structure, and rest on a hardness assumption distinct from the Module-LWE/Module-SIS problems that underlie the recently standardized ML-DSA (FIPS 204). The three-move identification scheme of Rizos and Draziotis (2023) and its Fiat–Shamir signature establish completeness, special soundness, special honest-verifier zero-knowledge, and EUF-CMA security in the random-oracle model. Its concrete parameters, however, were selected by hand, yielding a comparatively large signature (≈ 31.9 KB); the authors explicitly leave smarter parameter selection as future work. We close this gap. First, we provide an independent, fully reproducible re-implementation of the scheme's lattice attacks (the closest-vector and divide-and-conquer attacks) and of its signature-size accounting, validated against the original tables; our re-implementation reproduces the published success rates to within experimental noise. Second, we cast parameter selection as a constrained optimization problem and design an adaptive bit-allocation optimizer that minimizes signature size subject to soundness, completeness, commitment-unpredictability, key-entropy, and an empirical lattice-attack hardness gate. The optimizer exposes two honest sources of slack in the base parameters—an over-provisioned nonce space and an under-tightened secret space. The resulting configuration S = S1/4,1/3, S′ = S′1/8,1/8 shrinks the signature by 19.6% (to 25.6 KB) at identical security: equal soundness (2⁻⁸⁰), equal commitment-unpredictability (2⁻²⁴), equal completeness error (2.15 × 10⁻⁶), empirically equal closest-vector-attack hardness (50.0%), and equal-or-better divide-and-conquer hardness. All code, seeds, and numerical results are released for reproducibility.
Digital signatures based on the compact knapsack problem are attractive post-quantum candidates: they rely solely on integer arithmetic, require no algebraic ring structure, and rest on a hardness assumption distinct from the Module-LWE/Module-SIS problems that underlie the recently standardized ML-DSA (FIPS 204). The three-move identification scheme of Rizos and Draziotis (2023) and its Fiat–Shamir signature establish completeness, special soundness, special honest-verifier zero-knowledge, and EUF-CMA security in the random-oracle model. Its concrete parameters, however, were selected by hand, yielding a comparatively large signature (≈ 31.9 KB); the authors explicitly leave smarter parameter selection as future work. We close this gap. First, we provide an independent, fully reproducible re-implementation of the scheme's lattice attacks (the closest-vector and divide-and-conquer attacks) and of its signature-size accounting, validated against the original tables; our re-implementation reproduces the published success rates to within experimental noise. Second, we cast parameter selection as a constrained optimization problem and design an adaptive bit-allocation optimizer that minimizes signature size subject to soundness, completeness, commitment-unpredictability, key-entropy, and an empirical lattice-attack hardness gate. The optimizer exposes two honest sources of slack in the base parameters—an over-provisioned nonce space and an under-tightened secret space. The resulting configuration S = S1/4,1/3, S′ = S′1/8,1/8 shrinks the signature by 19.6% (to 25.6 KB) at identical security: equal soundness (2⁻⁸⁰), equal commitment-unpredictability (2⁻²⁴), equal completeness error (2.15 × 10⁻⁶), empirically equal closest-vector-attack hardness (50.0%), and equal-or-better divide-and-conquer hardness. All code, seeds, and numerical results are released for reproducibility.
Digital signatures are fundamental cryptographic primitives that ensure the authenticity and integrity of digital communication. However, in scenarios involving sensitive interactions -- such as e-voting or e-cash -- there is a growing need for more controlled signing mechanisms. Strong-Designated Verifier Signature (SDVS) offers such control by allowing the signer to specify and restrict the verifier of a signature. The existing state-of-the-art SDVS are mostly based on number-theoretic hardness assumptions. Thus, they are not secure against quantum attacks. Moreover, Post-Quantum Cryptography (PQC)-based SDVS are inefficient and have large key and signature sizes. In this work, we address these challenges and propose an efficient post-quantum SDVS (namely, LaSDVS) based on ideal lattices under the hardness assumptions of the Ring-SIS and Ring-LWE problems. LaSDVS achieves advanced security properties including strong unforgeability under chosen-message attacks, non-transferability, non-delegatability, and signer anonymity. By employing the algebraic structure of rings and the gadget trapdoor mechanism of Micciancio et al., we design LaSDVS to minimize computational overhead and significantly reduce key and signature sizes. Notably, our scheme achieves a compact signature size of O(nlogq), compared to O(n2) size, where n is the security parameter, in the existing state-of-the-art PQC designs. To the best of our knowledge, LaSDVS offers the \textit{smallest private key and signature size} among the existing PQC-based SDVS schemes.
Applying the Fiat-Shamir transform on identification schemes is one of the main ways of constructing signature schemes. While the classical security of this transformation is well understood, it is only very recently that generic results for the quantum case have been proposed [DFMS19,LZ19]. These results are asymptotic and therefore can't be used to derive the concrete security of these signature schemes without a significant loss in parameters. In this paper, we show that if we start from a commit-and-open identification scheme, where the prover first commits to several strings and then as a second message opens a subset of them depending on the verifier's message, then there is a tight quantum reduction for the the Fiat-Shamir transform to special soundness notions. Our work applies to most 3 round schemes of this form and can be used immediately to derive quantum concrete security of signature schemes. We apply our techniques to several identification schemes that lead to signature schemes such as Stern's identification scheme based on coding problems, the [KTX08] identification scheme based on lattice problems, the [SSH11] identification schemes based on multivariate problems, closely related to the NIST candidate MQDSS, and the PICNIC scheme based on multiparty computing problems, which is also a NIST candidate.
Background: The imminent threat posed by cryptographically relevant quantum computers to classical public-key infrastructure specifically RSA and Elliptic-Curve Cryptography (ECC), whose security rests on the conjectured computational intractability of integer factorisation and the discrete logarithm problem respectively has propelled lattice-based cryptography to the centre of global post-quantum standardisation efforts. On 13 August 2024, the United States National Institute of Standards and Technology (NIST) published three landmark Federal Information Processing Standards (FIPS): FIPS 203 (ML-KEM, derived from CRYSTALS-Kyber), FIPS 204 (ML-DSA, derived from CRYSTALS-Dilithium), and FIPS 205 (SLH-DSA, derived from SPHINCS+), with FIPS 206 (FN-DSA, derived from FALCON) in advanced draft. The first three of these standards rest on algebraic structures intimately connected to classical number theory: polynomial rings over integer quotients, cyclotomic fields, and the algebraic geometry of ideal lattices in rings of integers of number fields. Objectives: This article provides: (1) a rigorous mathematical exposition of the lattice problems underpinning NIST’s post-quantum standards, specifically the Learning With Errors (LWE), Ring-LWE (RLWE), Module-LWE (MLWE), Short Integer Solution (SIS), and NTRU problems, and their connections to algebraic number theory; (2) a comparative performance analysis of NIST-standardised lattice-based algorithms against classical RSA and ECC benchmarks; (3) a security analysis examining known classical and quantum attacks on each hard problem; (4) a comparative evaluation of the four NIST-selected algorithms across key size, signature size, and computational benchmarks; and (5) a strategic assessment of the migration challenges facing deployed cryptographic infrastructure. Methods: The study synthesises peer-reviewed literature, NIST official standards documentation (FIPS 203, 204, 205, and draft FIPS 206), and independently published performance benchmarks published between June 2024 and June 2026. Mathematical security analysis is grounded in the worst-case to average-case reductions established by Regev (2005) for LWE and by Lyubashevsky, Peikert, and Regev (2013) [11, 18] for Ring-LWE. Performance data are drawn from Garani (2024) [8], the ARM Cortex-M0+ benchmarking study of Ratnayaka and Fischer (2026) [4], and the cross-platform evaluation by Alzahrani et al. (2025) [2]. Results: NIST’s three August 2024 standards establish a comprehensive lattice-based post-quantum portfolio. ML-KEM-768 produces a 1,184-byte public key and 1,088-byte ciphertext, achieving IND-CCA2 security under the MLWE assumption at NIST Level 3 (AES-192 equivalent). ML-DSA-65 produces 1,952-byte public keys and 3,309-byte signatures under the Module-LWE and Module-SIS assumptions at Level 3. FN-DSA-512 (FALCON, draft FIPS 206) produces 897-byte public keys and 666-byte signatures under the NTRU assumption, offering the most compact lattice-based signatures. Performance benchmarks on an Intel Core i7-12700K (3.6 GHz) confirm that ML-KEM key generation is orders of magnitude faster than RSA-3072 key generation. The algebraic structure of cyclotomic polynomial rings ∑₂ⁿ = Z[x]/(x^n + 1) is central to the efficiency of all three lattice-based NIST standards. Conclusion: Lattice-based cryptography, grounded in the algebraic number theory of ideal lattices over cyclotomic fields, provides the most comprehensive and mathematically well-founded response to the quantum computational threat. The August 2024 NIST standardisation of ML-KEM, ML-DSA, and SLH-DSA represents a landmark in cryptographic history, and the imminent finalisation of FN-DSA will complete the post-quantum toolbox. Organisations should prioritise immediate migration planning, leveraging hybrid classical-quantum schemes during transition, with full transition to NIST post-quantum standards recommended by 2030 per NSA and CISA guidance.
Digital signatures are indispensable for security on the Internet, because they guarantee authenticity, integrity, and non-repudiation, of namely e-mails, software updates, and in the Transport Layer Security (TLS) protocol which is used for secure data transfer, for example. Most signature schemes that are currently in use such as the RSA signature scheme, are considered secure as long as the integer factorization problem or the discrete logarithm (DL) problem are computationally hard. At present, no algorithms have yet been found to solve these problems on conventional computers in polynomial time. However, in 1997, Shor published a polynomial-time algorithm that uses quantum computation to solve the integer factorization and the DL problem. In particular, this means that RSA signatures are considered broken as soon as large-scale quantum computers exist. Due to significant advances in the area of quantum computing, it is reasonable to assume that within 20 years, quantum computers that are able to break the RSA scheme, could exist. In order to maintain authenticity, integrity, and non-repudiation of data, cryptographic schemes that cannot be broken by quantum attacks are required. In addition, these so-called post-quantum secure schemes should be sufficiently efficient to be suitable for all established applications. Furthermore, solutions enabling a timely and secure transition from classical to post-quantum schemes are needed. This thesis contributes to the above-mentioned transition. In this thesis, we present the two lattice-based digital signature schemes TESLA and qTESLA, whereby lattice-based cryptography is one of five approaches to construct post-quantum secure schemes. Furthermore, we prove that our signature schemes are secure as long as the so-called Learning With Errors (LWE) problem is computationally hard to solve. It is presumed that even quantum computers cannot solve the LWE problem in polynomial time. The security of our schemes is proven using security reductions. Since our reductions are tight and explicit, efficient instantiations are possible that provably guarantee a selected security level, as long as the corresponding LWE instance provides a certain hardness level. Since both our reductions (as proven in the quantum random oracle model) and instantiations, take into account quantum attackers, TESLA and qTESLA are considered post-quantum secure. Concurrently, the run-times for generating and verifying signatures of qTESLA are similar (or faster) than those of the RSA scheme. However, key and signature sizes of RSA are smaller than those of qTESLA. In order to protect both the theoretical signature schemes and their implementations against attacks, we analyze possible vulnerabilities against implementation attacks. In particular, cache-side-channel attacks resulting from observing the cache behavior and fault attacks, which recover secret information by actively disrupting the execution of an algorithm are focused. We present effective countermeasures for each implementation attack we found. Our analyses and countermeasures also influence the design and implementation of qTESLA. Although our schemes are considered (post-quantum) secure according to state-of-the-art LWE attacks, cryptanalysis of lattice-based schemes is still a relatively new field of research in comparison to RSA schemes. Hence, there is a lack of confidence in the concrete instantiations and their promised security levels. However, due to developments within the field of quantum computers, a transition to post-quantum secure solutions seems to be more urgently required than ever. To solve this dilemma, we present an approach to combine two schemes, e.g., qTESLA and the RSA signature scheme, so that the combination is secure as long as one of the two combined schemes is secure. We present several of such combiners to construct hybrid signature schemes and hybrid key encapsulation mechanisms to ensure both authenticity and confidentiality in our Public-Key Infrastructure (PKI). Lastly, we also demonstrate how to apply the resulting hybrid schemes in standards such as X.509 or TLS. To summarize, this work presents post-quantum secure candidates which can, using our hybrid schemes, add post-quantum security to the current classical security in our PKI.
The study of digital signatures with tight reductions has attracted considerable attention over the past two decades, as such schemes inherit essentially the same quantitative hardness as the underlying computational problem. In the context of lattice-based cryptography, the GPV approach (Gentry, Peikert, and Vaikuntanathan, STOC ’08) admits a simple tight reduction from the SIS problem, but relies on preimage sampling via trapdoors, which often leads to complex and brittle implementations. By contrast, tight proofs for trapdoor-free constructions, following the Fiat–Shamir paradigm, necessarily rely on decisional assumptions, most notably the decisional LWE assumption. From the perspective of concrete security, however, reliance on a search assumption is preferable, as known search-to-decision reductions for LWE provide only weak quantitative guarantees. \ind This paper presents the first efficient lattice-based signature scheme with a tight reduction to a search assumption (namely, the hardness of the search LWE problem) that does not require any trapdoor in the scheme itself (but merely uses, instead, a trapdoor in the proof). Our construction follows the Fiat-Shamir paradigm and can be viewed as a lattice analogue of Chevallier–Mames signatures (CRYPTO ’05). Establishing security in the lattice setting, however, requires overcoming significant technical obstacles: in particular, our proof develops several new techniques to cope with the inherently weak soundness guarantees of lattice-based interactive proofs.
We present a structured security and performance analysis of modern post-quantum latticebased constructions, emphasizing module lattices and their core hardness assumptions: ModuleLearning With Errors (Module-LWE) and Module Short Integer Solution (Module-SIS). Weoutline the reductionist security story from worst-case lattice problems to average-case ModuleLWE, describe the role of Gaussian measures and smoothing, and provide a reproducible experimental workflow for estimating attack costs using standard lattice estimators. We also discuss the gap between asymptotic hardness and concrete parameter selection, and we provide plots that summarize scaling trends for reviewer-facing evaluation