Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Advanced Network Technologies and Applications (APAN)

Design and Evaluation of Iteratively Improved Rejection Sampling Lattice Signatures for DNSSEC

Sindhu Kumari, Anand Raje, Indrajit Banerjee

Published Aug 1, 2026• 0 citations
Publisher

Abstract

The Domain Name System (DNS) is an important component of the Internet, but existing security measures, such as Domain Name System Security Extensions (DNSSEC) using Rivest–Shamir–Adleman (RSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), are susceptible to quantum attacks enabled by Shor’s algorithm. To mitigate this, we present a quantum-resistant Domain Name System (DNS) infrastructure using lattice-based digital signatures, which is one of a leading approach for Post-Quantum cryptography (PQC). Our design uses an iterative improvement approach, beginning with a baseline rejection sampling Lattice-Based signature scheme. Subsequent designs introduce performance and resilience enhancements: Fiat–Shamir transformation with double rejection sampling, the use of centered binomial distribution to generate noise, Number Theoretic Transform (NTT)-based polynomial multiplication for efficient computation, and SHAKE-256 hash function for complete security alignment with NIST guidelines. The final version introduces a vector–matrix design, through which scalability and performance tuning can be achieved for use in DNS applications. Experimental results show consistent decrease in signing and verification latency and more effective signature compactness in comparison to employing the initial implementation. The combination of Number Theoretic Transform (NTT) multiplication and SHAKE-256 achieves efficiency without loss of security, and the vector-matrix format facilitates large-scale Domain Name System (DNS) operation. This paper shows the viability of engineering and optimizing existing lattice-based post-quantum signature schemes for the Domain Name System Security Extensions (DNSSEC) use case through an implementation-level analysis.

DOI
10.1109/apan70967.2026.11709662

Related papers

Quantum-Resistant Domain Name System: A Comprehensive System-Level Study

Juyoul Lee, Sanzida Hoque, Abdullah Aydeger +1 more

The Domain Name System (DNS) plays a foundational role in Internet infrastructure, yet its core protocols remain vulnerable to compromise by quantum adversaries. As cryptographically relevant quantum computers become a realistic threat, ensuring DNS confidentiality, authenticity, and integrity in the post-quantum era is imperative. In this paper, we present a comprehensive system-level study of post-quantum DNS security across three widely deployed mechanisms: DNSSEC, DNS-over-TLS (DoT), and DNS-over-HTTPS (DoH). We propose Post-Quantum Cryptographic (PQC)-DNS, a unified framework for benchmarking DNS security under legacy, post-quantum, and hybrid cryptographic configurations. Our implementation leverages the Open Quantum Safe (OQS) libraries and integrates lattice- and hash-based primitives into BIND9 and TLS 1.3 stacks. We formalize performance and threat models and analyze the impact of post-quantum key encapsulation and digital signatures on end-to-end DNS resolution. Experimental results on a containerized testbed reveal that lattice-based primitives such as Module-Lattice-Based Key-Encapsulation Mechanism (MLKEM) and Falcon offer practical latency and resource profiles, while hash-based schemes like SPHINCS+ significantly increase message sizes and processing overhead. We also examine security implications including downgrade risks, fragmentation vulnerabilities, and susceptibility to denial-of-service amplification. Our findings inform practical guidance for deploying quantum-resilient DNS and contribute to the broader effort of securing core Internet protocols for the post-quantum future.

arXiv:2506.19943•Jun 24, 2025•0 citations

A New Lattice-Based Post-Quantum Digital Signature from Compact Rejection Sampling

Pingyuan Zhang, Limin Wang

Rejection samplings are the essential building blocks to design lattice-based digital signatures under the Fiat–Shamir paradigm. Up to now most of them have been built by Gaussian samplings or uniform samplings. Gaussian-based rejection sampling signatures such as the BLISS scheme have very short signature sizes but are vulnerable to timing attacks, whereas the uniform-based rejection sampling signatures such as ML-DSA are allowed to be simply implemented but have larger signature sizes. This work intends to use a new probability distribution, rather than Gaussian or uniform distributions, to build the rejection sampling in Fiat–Shamir signatures, and aims to achieve short signature sizes while avoiding the cost of Gaussian sampling. To this end, we choose centered binomial distribution as a replacement, and build a new and compact rejection sampling that has the properties of both high-precision sampling and semi-uniform operation. As an application, we combine this rejection sampling with Lyubashevsky’s signature scheme, then propose the first lattice-based Fiat–Shamir signature scheme from centered binomial distribution. The proposed scheme not only avoids Gaussian sampling, but also is very efficient in terms of the signature sizes.

Computers•Aug 19, 2026•0 citations

Evaluating Post-Quantum Cryptography in DNSSEC Signing for Top-Level Domain Operators

Caspar Schutijser, Ralph Koning, Elmer Lastdrager +1 more

Like all other digital systems, the Domain Name System (DNS) needs to remain secure, even when future quantum computers are built. This means that DNS operators need to understand the implications of replacing the currently deployed cryptographic algorithms of the DNS Security Extensions (DNSSEC) with post-quantum cryptography (PQC) ones, which are vastly different. We therefore empirically analyze the signing performance of promising PQC algorithms MAYO-2 and Falcon-512 from a DNS operator point of view, in terms of zone file size, signing time, and validation time, and compare them to currently deployed algorithms RSA-1280 and ECDSA-P256. In our experiments, we use a PQC-enhanced DNSSEC signer, the zone files of three country code Top-Level Domains (ccTLDs) of different sizes, and two different CPU models to measure the effects of CPU optimizations. We find that the DNSSEC signing performance of MAYO-2 is better than RSA-1280, while Falcon-512 performs similarly. The validation performance of MAYO-2 is better than ECDSA-P256 and comparable to RSA-1280, whereas Falcon-512 is 0.3 times slower than ECDSA-P256. These results suggest that DNSSEC signing with MAYO-2 and Falcon-512 is feasible for TLD operators. However, Falcon-512 generates larger signature size and MAYO-2 has larger public keys. These drawbacks should be studied further to assess their operational impact on the validation side, for example by studying the behavior of DNS resolvers with PQC algorithms.

Network Traffic Measurement and Analysis Conference (TMA)•Jun 10, 2025•4 citations

Retrofitting post-quantum cryptography in internet protocols: a case study of DNSSEC

Moritz Müller, Jins de Jong, Maran P. P. van Heesch +2 more

Quantum computing is threatening current cryptography, especially the asymmetric algorithms used in many Internet protocols. More secure algorithms, colloquially referred to as Post-Quantum Cryptography (PQC), are under active development. These new algorithms differ significantly from current ones. They can have larger signatures or keys, and often require more computational power. This means we cannot just replace existing algorithms by PQC alternatives, but need to evaluate if they meet the requirements of the Internet protocols that rely on them. In this paper we provide a case study, analyzing the impact of PQC on the Domain Name System (DNS) and its Security Extensions (DNSSEC). In its main role, DNS translates human-readable domain names to IP addresses and DNSSEC guarantees message integrity and authenticity. DNSSEC is particularly challenging to transition to PQC, since DNSSEC and its underlying transport protocols require small signatures and keys and efficient validation. We evaluate current candidate PQC signature algorithms in the third round of the NIST competition on their suitability for use in DNSSEC. We show that three algorithms, partially, meet DNSSEC's requirements but also show where and how we would still need to adapt DNSSEC. Thus, our research lays the foundation for making DNSSEC, and protocols with similar constraints ready for PQC.

ACM SIGCOMM Computer Communication Review•Oct 26, 2020•32 citations

CURRENT PARADIGMS FOR CONSTRUCTION OF LATTICE-BASED DIGITAL SIGNATURE SCHEMES

QApp, Леевик Антон Георгиевич, Ekaterina Sergeevna Malygina +4 more

With the advent of quantum computing, research into post-quantum cryptography has gained significant attention. This is a novel branch of cryptography that utilizes algorithms and protocols designed to withstand attacks from quantum computers. Lattice theory represents a promising area within post-quantum cryptographic research. Two early examples of lattice-based cryptosystems are the GGH and NTRU schemes. These schemes are based on the challenge of finding the closest vector in a lattice and differ primarily in the type of lattice used. The NTRUSign protocol was developed by combining the strengths of both schemes. In 2008, another approach to lattice signatures was introduced by a group of authors. It is based on the hash-and-sign paradigm, in which a signature for a message is generated using a trapdoor. A year later, V. Lyubashevsky proposed another method for constructing lattice-based signatures that utilizes the Fiat — Shamir transform. However, due to the nature of the underlying lattice structure, the algorithm for signature generation produces a correct signature only with a certain probability. This is due to the use of a rejection sampling for security purposes. This paper presents an overview of existing lattice-based signature construction approaches and cryptographic schemes that are based on these approaches. A comparative analysis was conducted on these schemes, identifying the advantages and disadvantages of each method. Based on the results, optimal conditions for the application of each approach have been determined.

PRIKLADNAYa DISKRETNAYa MATEMATIKA•Jan 1, 2025•0 citations

Rejection Sampling Revisit: How to Choose Parameters in Lattice-Based Signature

Zhongxiang Zheng, Anyu Wang, Lingyue Qin

Rejection sampling technology is a core tool in the design of lattice-based signatures with ‘Fiat–Shamir with Aborts’ structure, and it is related to signing efficiency and signature, size as well as security. In the rejection sampling theorem proposed by Lyubashevsky, the masking vector of rejection sampling is chosen from discrete Gaussian distribution. However, in practical designs, the masking vector is more likely to be chosen from bounded uniform distribution due to better efficiency and simpler implementation. Besides, as one of the third-round candidate signatures in the NIST postquantum cryptography standardization process, the 3rd round version of CRYSTALS-Dilithium has proposed a new method to decrease the rejection probability in order to achieve better efficiency and smaller signature size by decreasing the number of nonzero coefficients of the challenge polynomial according to the security levels. However, it is seen that small entropies in this new method may lead to higher risk of forgery attack compared with former schemes proposed in its 2nd version. Thus, in this paper, we first analyze the complexity of forgery attack for small entropies and then introduce a new method to decrease the rejection probability without loss of security including the security against forgery attack. This method is achieved by introducing a new rejection sampling theorem with tighter bound by utilizing Rényi divergence where masking vector follows uniform distribution. By observing large gaps between the security claim and actual security bound in CRYSTALS-Dilithium, we propose two series of adapted parameters for CRYSTALS-Dilithium. The first set can improve the efficiency of the signing process in CRYSTALS-Dilithium by factors of 61.7 % and 41.7 % , according to the security levels, and ensure the security against known attacks, including forgery attack. And, the second set can reduce the signature size by a factor of 14.09 % with small improvements in efficiency at the same security level.

Mathematical Problems in Engineering•Jun 7, 2021•5 citations
The Domain Name System (DNS) is an important component of the Internet, but existing security measures, such as Domain Name System Security Extensions (DNSSEC) using Rivest–Shamir–Adleman (RSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), are susceptible to quantum attacks enabled by Shor’s algorithm. To mitigate this, we present a quantum-resistant Domain Name System (DNS) infrastructure using lattice-based digital signatures, which is one of a leading approach for Post-Quantum cryptography (PQC). Our design uses an iterative improvement approach, beginning with a baseline rejection sampling Lattice-Based signature scheme. Subsequent designs introduce performance and resilience enhancements: Fiat–Shamir transformation with double rejection sampling, the use of centered binomial distribution to generate noise, Number Theoretic Transform (NTT)-based polynomial multiplication for efficient computation, and SHAKE-256 hash function for complete security alignment with NIST guidelines. The final version introduces a vector–matrix design, through which scalability and performance tuning can be achieved for use in DNS applications. Experimental results show consistent decrease in signing and verification latency and more effective signature compactness in comparison to employing the initial implementation. The combination of Number Theoretic Transform (NTT) multiplication and SHAKE-256 achieves efficiency without loss of security, and the vector-matrix format facilitates large-scale Domain Name System (DNS) operation. This paper shows the viability of engineering and optimizing existing lattice-based post-quantum signature schemes for the Domain Name System Security Extensions (DNSSEC) use case through an implementation-level analysis.
The Domain Name System (DNS) plays a foundational role in Internet infrastructure, yet its core protocols remain vulnerable to compromise by quantum adversaries. As cryptographically relevant quantum computers become a realistic threat, ensuring DNS confidentiality, authenticity, and integrity in the post-quantum era is imperative. In this paper, we present a comprehensive system-level study of post-quantum DNS security across three widely deployed mechanisms: DNSSEC, DNS-over-TLS (DoT), and DNS-over-HTTPS (DoH). We propose Post-Quantum Cryptographic (PQC)-DNS, a unified framework for benchmarking DNS security under legacy, post-quantum, and hybrid cryptographic configurations. Our implementation leverages the Open Quantum Safe (OQS) libraries and integrates lattice- and hash-based primitives into BIND9 and TLS 1.3 stacks. We formalize performance and threat models and analyze the impact of post-quantum key encapsulation and digital signatures on end-to-end DNS resolution. Experimental results on a containerized testbed reveal that lattice-based primitives such as Module-Lattice-Based Key-Encapsulation Mechanism (MLKEM) and Falcon offer practical latency and resource profiles, while hash-based schemes like SPHINCS+ significantly increase message sizes and processing overhead. We also examine security implications including downgrade risks, fragmentation vulnerabilities, and susceptibility to denial-of-service amplification. Our findings inform practical guidance for deploying quantum-resilient DNS and contribute to the broader effort of securing core Internet protocols for the post-quantum future.
Rejection samplings are the essential building blocks to design lattice-based digital signatures under the Fiat–Shamir paradigm. Up to now most of them have been built by Gaussian samplings or uniform samplings. Gaussian-based rejection sampling signatures such as the BLISS scheme have very short signature sizes but are vulnerable to timing attacks, whereas the uniform-based rejection sampling signatures such as ML-DSA are allowed to be simply implemented but have larger signature sizes. This work intends to use a new probability distribution, rather than Gaussian or uniform distributions, to build the rejection sampling in Fiat–Shamir signatures, and aims to achieve short signature sizes while avoiding the cost of Gaussian sampling. To this end, we choose centered binomial distribution as a replacement, and build a new and compact rejection sampling that has the properties of both high-precision sampling and semi-uniform operation. As an application, we combine this rejection sampling with Lyubashevsky’s signature scheme, then propose the first lattice-based Fiat–Shamir signature scheme from centered binomial distribution. The proposed scheme not only avoids Gaussian sampling, but also is very efficient in terms of the signature sizes.
Like all other digital systems, the Domain Name System (DNS) needs to remain secure, even when future quantum computers are built. This means that DNS operators need to understand the implications of replacing the currently deployed cryptographic algorithms of the DNS Security Extensions (DNSSEC) with post-quantum cryptography (PQC) ones, which are vastly different. We therefore empirically analyze the signing performance of promising PQC algorithms MAYO-2 and Falcon-512 from a DNS operator point of view, in terms of zone file size, signing time, and validation time, and compare them to currently deployed algorithms RSA-1280 and ECDSA-P256. In our experiments, we use a PQC-enhanced DNSSEC signer, the zone files of three country code Top-Level Domains (ccTLDs) of different sizes, and two different CPU models to measure the effects of CPU optimizations. We find that the DNSSEC signing performance of MAYO-2 is better than RSA-1280, while Falcon-512 performs similarly. The validation performance of MAYO-2 is better than ECDSA-P256 and comparable to RSA-1280, whereas Falcon-512 is 0.3 times slower than ECDSA-P256. These results suggest that DNSSEC signing with MAYO-2 and Falcon-512 is feasible for TLD operators. However, Falcon-512 generates larger signature size and MAYO-2 has larger public keys. These drawbacks should be studied further to assess their operational impact on the validation side, for example by studying the behavior of DNS resolvers with PQC algorithms.
Quantum computing is threatening current cryptography, especially the asymmetric algorithms used in many Internet protocols. More secure algorithms, colloquially referred to as Post-Quantum Cryptography (PQC), are under active development. These new algorithms differ significantly from current ones. They can have larger signatures or keys, and often require more computational power. This means we cannot just replace existing algorithms by PQC alternatives, but need to evaluate if they meet the requirements of the Internet protocols that rely on them. In this paper we provide a case study, analyzing the impact of PQC on the Domain Name System (DNS) and its Security Extensions (DNSSEC). In its main role, DNS translates human-readable domain names to IP addresses and DNSSEC guarantees message integrity and authenticity. DNSSEC is particularly challenging to transition to PQC, since DNSSEC and its underlying transport protocols require small signatures and keys and efficient validation. We evaluate current candidate PQC signature algorithms in the third round of the NIST competition on their suitability for use in DNSSEC. We show that three algorithms, partially, meet DNSSEC's requirements but also show where and how we would still need to adapt DNSSEC. Thus, our research lays the foundation for making DNSSEC, and protocols with similar constraints ready for PQC.
With the advent of quantum computing, research into post-quantum cryptography has gained significant attention. This is a novel branch of cryptography that utilizes algorithms and protocols designed to withstand attacks from quantum computers. Lattice theory represents a promising area within post-quantum cryptographic research. Two early examples of lattice-based cryptosystems are the GGH and NTRU schemes. These schemes are based on the challenge of finding the closest vector in a lattice and differ primarily in the type of lattice used. The NTRUSign protocol was developed by combining the strengths of both schemes. In 2008, another approach to lattice signatures was introduced by a group of authors. It is based on the hash-and-sign paradigm, in which a signature for a message is generated using a trapdoor. A year later, V. Lyubashevsky proposed another method for constructing lattice-based signatures that utilizes the Fiat — Shamir transform. However, due to the nature of the underlying lattice structure, the algorithm for signature generation produces a correct signature only with a certain probability. This is due to the use of a rejection sampling for security purposes. This paper presents an overview of existing lattice-based signature construction approaches and cryptographic schemes that are based on these approaches. A comparative analysis was conducted on these schemes, identifying the advantages and disadvantages of each method. Based on the results, optimal conditions for the application of each approach have been determined.
Rejection sampling technology is a core tool in the design of lattice-based signatures with ‘Fiat–Shamir with Aborts’ structure, and it is related to signing efficiency and signature, size as well as security. In the rejection sampling theorem proposed by Lyubashevsky, the masking vector of rejection sampling is chosen from discrete Gaussian distribution. However, in practical designs, the masking vector is more likely to be chosen from bounded uniform distribution due to better efficiency and simpler implementation. Besides, as one of the third-round candidate signatures in the NIST postquantum cryptography standardization process, the 3rd round version of CRYSTALS-Dilithium has proposed a new method to decrease the rejection probability in order to achieve better efficiency and smaller signature size by decreasing the number of nonzero coefficients of the challenge polynomial according to the security levels. However, it is seen that small entropies in this new method may lead to higher risk of forgery attack compared with former schemes proposed in its 2nd version. Thus, in this paper, we first analyze the complexity of forgery attack for small entropies and then introduce a new method to decrease the rejection probability without loss of security including the security against forgery attack. This method is achieved by introducing a new rejection sampling theorem with tighter bound by utilizing Rényi divergence where masking vector follows uniform distribution. By observing large gaps between the security claim and actual security bound in CRYSTALS-Dilithium, we propose two series of adapted parameters for CRYSTALS-Dilithium. The first set can improve the efficiency of the signing process in CRYSTALS-Dilithium by factors of 61.7 % and 41.7 % , according to the security levels, and ensure the security against known attacks, including forgery attack. And, the second set can reduce the signature size by a factor of 14.09 % with small improvements in efficiency at the same security level.