Cross-organizational authentication often requires credentials from several authorities. We construct a lattice-based protocol with independently issued capabilities bound to a periodic pseudonym authenticated by a trusted user registry and aggregated locally into one proof. Setup requires no system-wide lattice master trapdoor or cross-authority joint lattice secret. Repartitioning a fixed witness among authorities preserves the aggregate relation and proof dimensions. We prove fixed-witness selective unforgeability of the ideal protocol under honest issuance, authentication-signature security, normal-form module learning with errors (Module-LWE), and homogeneous module short-integer solution (Module-SIS). The proof uses classical random oracles, a programmable extendable-output function (XOF), an integer norm certificate, and a reference sampler with quantified error. A C++17 research prototype was evaluated in 23 configurations. Its 78,522-byte token becomes smaller than the per-attribute Module-Lattice-Based Digital Signature Algorithm (ML-DSA)-44 reference at 33 attributes and is 49.51% smaller at 64 attributes. With 64 attributes and 64 authorities, online signing and prepared verification took 56.038 and 8.729 ms, respectively. Complete local cold signing took 370.050 ms, and public matrices for 64 capabilities occupied 29.75 mebibytes (MiB). Aggregation reduces repeated token communication for larger witnesses, at the cost of preparation, public-state storage, and higher measured computation than the ML-DSA references.
Cross-organizational authentication often requires credentials from several authorities. We construct a lattice-based protocol with independently issued capabilities bound to a periodic pseudonym authenticated by a trusted user registry and aggregated locally into one proof. Setup requires no system-wide lattice master trapdoor or cross-authority joint lattice secret. Repartitioning a fixed witness among authorities preserves the aggregate relation and proof dimensions. We prove fixed-witness selective unforgeability of the ideal protocol under honest issuance, authentication-signature security, normal-form module learning with errors (Module-LWE), and homogeneous module short-integer solution (Module-SIS). The proof uses classical random oracles, a programmable extendable-output function (XOF), an integer norm certificate, and a reference sampler with quantified error. A C++17 research prototype was evaluated in 23 configurations. Its 78,522-byte token becomes smaller than the per-attribute Module-Lattice-Based Digital Signature Algorithm (ML-DSA)-44 reference at 33 attributes and is 49.51% smaller at 64 attributes. With 64 attributes and 64 authorities, online signing and prepared verification took 56.038 and 8.729 ms, respectively. Complete local cold signing took 370.050 ms, and public matrices for 64 capabilities occupied 29.75 mebibytes (MiB). Aggregation reduces repeated token communication for larger witnesses, at the cost of preparation, public-state storage, and higher measured computation than the ML-DSA references.
With the standardization of post-quantum signature schemes such as Dilithium and Falcon, lattice-based ring signatures have become a promising tool for anonymous authentication and privacy-preserving encryption in big data environments. Specifically, the DualRing-LB scheme (CRYPTO’ 21), despite its short signatures and elegant structure, suffers from the large public key size, which dominates its communication cost and hinders scalability. There are two methods to reduce the public key size: the first is a compression technique, and the second is the bimodal distribution. The former discards the lower bits of the public key while the latter utilizes a smaller modulus. However, the unforgeability proof of DualRing-LB is incompatible with these methods because they lead to a rapid increase in the norm bound of the module short integer solution (or MSIS) problem, thereby significantly reducing security. In this paper, we follow the original security method of DualRing-LB and apply the trapdoor sampling technique to derive a tighter upper bound of MSIS problem, yielding a fixed security level independent of the ring size. The new proof result enables the use of both the compression technique and the bimodal distribution to enhance the communication efficiency of lattice-based DualRing schemes. Based on this result, we propose three practical lattice-based instantiations that reduce the public key size by 56%, 67%, 50%, compared to DualRing-LB, respectively, and achieve overall size reductions of at least 52%, 56%, 38%, respectively, across different ring sizes. Our results can contribute to lightweight, privacy-preserving cryptographic mechanisms for secure data sharing and authentication in large-scale distributed systems.
Anonymous authentication schemes such as group signatures and anonymous credentials are important privacy-protecting tools in electronic communications. The only currently known scheme based on assumptions that resist quantum attacks is the group signature scheme by Gordon et al. (ASIACRYPT 2010). We present a generalization of group signatures called anonymous attribute tokens where users are issued attribute-containing credentials that they can use to anonymously sign messages and generate tokens revealing only a subset of their attributes. We present two lattice-based constructions of this new primitive, one with and one without opening capabilities for the group manager. The latter construction directly yields as a special case the first lattice-based group signature scheme offering full anonymity (in the random-oracle model), as opposed to the practically less relevant notion of chosen-plaintext anonymity offered by the scheme of Gordon et al. We also extend our scheme to protect users from framing attacks by the group manager, where the latter creates tokens or signatures in the name of honest users. Our constructions involve new lattice-based tools for aggregating signatures and verifiable CCA2-secure encryption.
Due to limited computational and storage capabilities, wireless medical sensor networks (WMSN) encounter considerable overhead in processing the storage and verification of numerous signatures. Multi-signatures allow a group of signers to produce a single, compact signature on the same message, significantly reducing storage requirements and communication bandwidth in WMSN. However, conventional multi-signature schemes are not quantum resistant, as their security assumptions will be compromised with the quick advancement in quantum computing. Alternatively, lattice-based cryptography is widely considered capable of withstanding quantum computing attacks. In this article, we introduce a quantum-resistant and non-interactive identity-based multi-signature scheme from lattices with public key aggregation (IBMS-pka). By leveraging the small integer solution (SIS) assumption, our scheme is proven secure within the random oracle model. Besides, our scheme enables users to choose their system identities (e.g., physical IP address or email address) as public keys compared to PKI-based schemes, and avoids the extra communication costs in contrast to interactive schemes. Meanwhile, our scheme outperforms other related works according to our experiments. Specifically, the multi-signature generation has a slightly higher efficiency compared to other related schemes, while the multi-signature verification has a larger enhancement. Moreover, the performance improvement becomes more evident as the number of signers grows.
Permissioned blockchains authenticate transactions, votes and quorum certificates with computationally secure signatures, and post-quantum replacements inflate consensus traffic by orders of magnitude. Information-theoretic alternatives have required a trusted authority, quantum channels, per-signature interaction, or single-use keys with bounded transfer. We present SILMARILS-MV, a multi-verifier unconditionally secure signature in which a signature is the vector α=Ae(m) and each verifier holds a secret functional ci=ΓTλ(xi) derived from virtual anchors Γ that nobody learns. Against unbounded adversaries corrupting up to ω verifiers and any signers, and observing every decision, an honest verifier accepts a forged or invalid signature with probability at most Q/q+1/(q−1), a bound that is tight in its leading term. The scheme is strongly unforgeable, non-repudiable, transferable across unboundedly many hops, and linearly aggregatable. Keys are issued by the validators through perfectly secure MPC for t<n/3, without broadcast. To scale, we let the committee itself sign: in threshold notarization, finality certificates have constant size 32(ω+1) bytes and per-validator issuance cost no longer depends on n. Arbiter-verified keys give clients 32-byte signatures, robust redistribution supports membership changes and share refresh, and verifiers can be enrolled retroactively. A certificate verifies in 2.4 microseconds. In an analytic normal-case model at 1000 validators, threshold notarization needs 71 KiB of authentication traffic per validator per block, 22x less than ML-DSA-44 for admitted verifiers. In a Rust HotStuff prototype with 100 validators, SILMARILS-MV commits 2.8x more transactions per second than ML-DSA-44 with 67x less cryptographic CPU, and Monte-Carlo attacks match the bounds.
Digital signatures authorize transactions, commands and other requests. Quantum attacks threaten widely used signature schemes, while their post-quantum replacements can be costly to verify inside proofs of execution. Signatureless authorization binds knowledge of an authority secret to a canonical request through a freshly randomized proof capsule. The public statement consists of a request identifier and a 32-byte authority commitment. Application rules enforce context, policy and freshness. The interface supports standalone requests and recursive proof composition. The construction combines a masked degree-ten authority reduction over GF(2^128), embedded in GF(2^256), with a bank-and-companion code proof. Source restoration gives expected polynomial-time public-coin extraction. An adaptive witness-free simulator and a same-experiment source extractor establish a quantum chosen-request authorization reduction in the stated address-compatible random-completion model. The public authority circuit and its address input slice are fixed. One permutation supplies the native transcript and commitments. Finite orbit-profile and resource conditions are explicit. The reduction quantifies simulation and extraction losses alongside authority-preimage hardness and canonical intent binding. For S <= T and T <= 2^24 charged native calls, the combined simulation and extraction loss is below 2^-67, including the uniform-slice setup failure. Parano1d supplies a blockchain implementation and recursive verifier. Canonical capsules are bounded by 92,696 bytes. On four CPU threads, median proving takes 0.81 to 0.89 seconds and verification takes approximately 25.6 milliseconds for two request fixtures. The accompanying reproducibility archive contains the manuscript sources, exact arithmetic and finite operator checks, simulation tests, recorded measurements, Rust reproduction programs and authenticated production source files. Its README provides the reproduction commands. Contact: dev@parano1d.orgLicense information: The paper and accompanying written documentation are licensed under Creative Commons Attribution 4.0 International (CC BY 4.0). Original software in the reproducibility artifact is licensed under the Apache License, Version 2.0. Third-party dependencies retain their respective licenses.
Cryptography underpins the security of modern digital infrastructure, from cloud services to health data. However, many widely deployed systems will become vulnerable after the advent of scalable quantum computing. Although quantum-safe cryptographic primitives have been developed, such as lattice-based digital signature algorithms (DSAs) and key encapsulation mechanisms (KEMs), their unique structural and performance characteristics make them unsuitable for existing protocols. In this work, we introduce a quantum-safe single-shot protocol for machine-to-machine authentication and authorization that is specifically designed to leverage the strengths of lattice-based DSAs and KEMs. Operating entirely over insecure channels, this protocol enables the forward-secure establishment of tokens in constrained environments. By demonstrating how new quantum-safe cryptographic primitives can be incorporated into secure systems, this study lays the groundwork for scalable, resilient, and future-proof identity infrastructures in a quantum-enabled world.