International Association
for Cryptologic Research

We have conducted a field study on post-quantum DNSSEC [1], involving RIPE ATLAS measurements with around 10,000 probes. Using implementations of post quantum signing schemes (Falcon, Dilithium, SPHINCS+, XMSS) in both BIND and PowerDNS, DNS response success and failure rates depending on the signing scheme and other parameters were investigated. In addition to the above algorithms, we present new results on a novel class of DNSSEC signatures, using Merkle trees for optimizing signature sizes. Besides measurement results, we also provide context on our implementation approach. We find that depending on circumstances, a significant fraction of clients choke. Failure rates are mainly a function of response packet size, which is mediated by parameters such as DNSSEC configuration (KSK/ZSK vs. CSK, NSEC vs. NSEC3, or compact DoE) and DO bit presence, with some variation depending on transport. This is qualitatively in line with the "educated guess", but adds quantitative detail. We also find surprising results, such as that a number of resolvers claim to have validated PQC signatures, even though it is implausible for resolvers to support these algorithms. Between now and RWC 2025 we will be evaluating all of the above algorithms in the context of a large enterprise’s DNS environment, which will further enhance our understanding of the implications of transitioning to quantum safe algorithms. Implementation included adding both signing and validation support to PowerDNS recursor and BIND resolver. Both functions can be tested using a do-it-yourself frontend [2], which the public can use to work and familiarize themselves with our testbed. We hope that this study helps inform future PQC engineering developments not just in the context of DNS but also other UDP based protocols [1]: https://nlnet.nl/project/PQ-DNSSEC-Testbench/ [2]: https://pq-dnssec.dedyn.io/

This paper presents a code-based signature scheme based on the well-known syndrome decoding (SD) problem. The scheme builds upon a recent line of research which uses the Multi-Party-Computation-in-the-Head (MPCitH) approach to construct efficient zero-knowledge proofs, such as Syndrome Decoding in the Head (SDitH), and builds signature schemes from them using the Fiat-Shamir transform. At the heart of our proposal is a new approach, Hypercube-MPCitH, to amplify the soundness of any MPC protocol that uses additive secret sharing. An MPCitH protocol with N parties can be repeated D times using parallel composition to reach the same soundness as a protocol run with N^D parties. However, the former comes with D times higher communication costs, often mainly contributed by the usage of D `auxiliary' states (which in general have a significantly bigger impact on size than random states). Instead of that, we begin by generating N^D shares, arranged into a D-dimensional hypercube of side N containing only one `auxiliary' state. We derive from this hypercube D sharings of size N which are used to run D instances of an N party MPC protocol. Hypercube-MPCitH leads to a protocol with 1/N^D soundness error, requiring N^D offline computation, but with only N*D online computation, and only one `auxiliary'. As the (potentially offline) share generation phase is generally inexpensive, this leads to trade-offs that are superior to just using parallel composition. Our novel method of share generation and aggregation not only improves certain MPCitH protocols in general but also shows in concrete improvements of signature schemes. Specifically, we apply it to the work of Feneuil, Joux, and Rivain (CRYPTO'22) on code-based signatures, and obtain a new signature scheme that achieves a 8.1x improvement in global runtime and a 30x improvement in online runtime for their shortest signatures size (8,481 Bytes). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6,784 Bytes for 26 ms offline and 5,689 Bytes for 320 ms offline. For NIST security level 1, online signature cost is around 3 million cycles (<1 ms on commodity processors), regardless of signature size.