Abstract Falcon is a compact and efficient post-quantum signature scheme based on the NTRU lattice, but it follows the conventional public-key setting and does not directly support identity-to-key binding or signer traceability. In this paper, we propose IBFS, a PKG-managed and authenticated identity-binding signature framework over Falcon. In IBFS, a trusted Private Key Generator (PKG) derives Falcon-compatible NTRU signing keys for registered users and maintains an authenticated binding between user identities and public keys. Unlike pure identity-based signatures, verification uses the signer’s identity together with an authenticated public key validated against a PKG-managed repository. This framework targets managed deployments with a trusted registration backend, including IoT and edge systems. The device-side evaluation concerns signature verification on an Android smartphone in a server-assisted setting; it does not establish operation of the complete framework on tightly constrained IoT devices. The construction retains the efficiency advantages of Falcon-style signing, including compact short-vector signatures and FFT-accelerated arithmetic, and further introduces a deterministic, PKG-resolvable identity tag that enables resolution of verified signatures to registered identities. We establish correctness and identity-resolution consistency under authentic repository bindings, without claiming non-frameability against the PKG. On the security side, we make the trust boundaries of the managed setting explicit, including key escrow, insider compromise, malicious tracing, and repository integrity. We then give a security argument in the classical Random Oracle Model that reduces the unforgeability of the signing layer, with a concrete advantage bound, to the decisional NTRU and inhomogeneous NTRU short-preimage (NTRU-ISIS) assumptions, together with the PRF security of the key-derivation function. The analysis is restricted to classical adversaries and does not constitute a Quantum Random Oracle Model proof. We therefore position IBFS as a classical-ROM construction whose security relies on these NTRU-based assumptions and on the authenticity of the PKG-managed binding repository.
Abstract Falcon is a compact and efficient post-quantum signature scheme based on the NTRU lattice, but it follows the conventional public-key setting and does not directly support identity-to-key binding or signer traceability. In this paper, we propose IBFS, a PKG-managed and authenticated identity-binding signature framework over Falcon. In IBFS, a trusted Private Key Generator (PKG) derives Falcon-compatible NTRU signing keys for registered users and maintains an authenticated binding between user identities and public keys. Unlike pure identity-based signatures, verification uses the signer’s identity together with an authenticated public key validated against a PKG-managed repository. This framework targets managed deployments with a trusted registration backend, including IoT and edge systems. The device-side evaluation concerns signature verification on an Android smartphone in a server-assisted setting; it does not establish operation of the complete framework on tightly constrained IoT devices. The construction retains the efficiency advantages of Falcon-style signing, including compact short-vector signatures and FFT-accelerated arithmetic, and further introduces a deterministic, PKG-resolvable identity tag that enables resolution of verified signatures to registered identities. We establish correctness and identity-resolution consistency under authentic repository bindings, without claiming non-frameability against the PKG. On the security side, we make the trust boundaries of the managed setting explicit, including key escrow, insider compromise, malicious tracing, and repository integrity. We then give a security argument in the classical Random Oracle Model that reduces the unforgeability of the signing layer, with a concrete advantage bound, to the decisional NTRU and inhomogeneous NTRU short-preimage (NTRU-ISIS) assumptions, together with the PRF security of the key-derivation function. The analysis is restricted to classical adversaries and does not constitute a Quantum Random Oracle Model proof. We therefore position IBFS as a classical-ROM construction whose security relies on these NTRU-based assumptions and on the authenticity of the PKG-managed binding repository.
We introduce NTRU-VRF, the first verifiable random function (VRF) constructed directly from the NTRU lattice hardness assumption, and instantiated concretely using the NIST-standardized Falcon-512 (FN-DSA) signature scheme. A VRF is a pseudorandom function that produces a publicly verifiable proof of correctness for each output. All currently deployed VRFs (IETF RFC 9381, Algorand, Ethereum) rely on elliptic-curve assumptions broken by Shor's algorithm. Prior post-quantum VRF constructions either require only a few-time security guarantee (Esgin et al., ePrint 2020/1222), rely on symmetric primitives that lack a worst-case lattice hardness reduction (Buser et al., ePrint 2021/302), or are based on Module-LWE/Module-SIS rather than NTRU. No prior work constructs a many-time, lattice-based VRF from NTRU hardness with a formal security proof. Our construction exploits a fundamental and previously unformalized property of Falcon's deterministic signing mode: for any fixed public key and input, there exists exactly one valid short-norm signature. This unique-signature property is the key structural feature that transforms a lattice signature into a VRF. We prove three theorems: Uniqueness: For any input, the NTRU-VRF output is unique. This follows directly from the unique-short-coset-vector property of the NTRU lattice. Pseudorandomness: If the Short Integer Solution (SIS) problem on NTRU lattices is hard and the hash function is modelled as a random oracle, then the VRF output is computationally indistinguishable from a uniformly random value. Provability: The Falcon signature is an efficient, publicly verifiable proof, checkable by any party holding the public key. As a concrete application, we define PQ-Sortition, a post-quantum proof-of-stake leader-election protocol that replaces ECVRF-based sortition with our NTRU-VRF construction. We provide the entropy-chain design, stake-weighted win condition, adaptive liveness mechanism, equivocation slashing, and a formal security analysis of the resulting consensus protocol. Instantiated with Falcon-512, NTRU-VRF achieves a VRF output of 32 bytes, a proof size of <= 666 bytes, evaluation time of ~0.8 ms, and verification time of ~0.1 ms on standard hardware—significantly outperforming all existing post-quantum VRF constructions and making it the first many-time, compact, lattice-based VRF suitable for high-throughput blockchain consensus.
Conventional public-key cryptographic systems are increasingly threatened by advances in quantum computing, accelerating the need for robust post-quantum cryptographic solutions. Among these, Falcon, a compact lattice-based digital signature scheme, has emerged as a leading candidate in the NIST post-quantum standardization process due to its efficiency and theoretical security grounded in hard lattice problems. This work introduces Falcon-M, a modified version of the Falcon algorithm that significantly reduces implementation complexity. It does so by replacing Falcon’s intricate trapdoor-based key-generation mechanism with a simplified approach that utilizes randomized polynomial Gaussian sampling and fast Fourier transform (FFT) operations. Falcon-M incorporates SHA-512 hashing and discrete Gaussian sampling to preserve cryptographic soundness and statistical randomness while maintaining the core structure of Falcon’s signing and verification processes. We formally specify the Falcon-M algorithm, provide an updated pseudocode, and offer a comparative analysis with the original Falcon in terms of algorithmic complexity, security assumptions, and implementation overhead. Additionally, we present formal lemmas and theorems to ensure correctness and define theoretical bounds on forgery resistance. Although Falcon-M does not rely on a formal cryptographic trapdoor, we demonstrate that it achieves strong practical security based on assumptions related to the Short Integer Solution (SIS) problem. Falcon-M is thus well-suited for lightweight post-quantum applications, particularly in resource-constrained environments, such as embedded systems and Internet-of-Things (IoT) platforms.
Based on the Hadamard operator and Bell states, an identity-based public-key quantum signature scheme is proposed. In our scheme, the signer’s identity is used as her public key. Her private keys are generated by the trusted private key generator (PKG). Given a quantum signature, the verifier can verify the validity of the quantum signature by the signer’s identity information without any public-key certificate. So, our quantum signature has the advantages of the identity-based signature system. On the other hand, in our scheme, it need not use the long-term quantum memory. The verifier need not perform any quantum swap test or state comparison algorithm. What is more, our quantum signature is secure against PKG’s forgery attack. And the disputation of losing quantum signature can be arbitrated by PKG. Therefore, our scheme is relatively more practical and efficient than the similar schemes.
Although the current lattice-based ring signcryption scheme resists quantum attacks,it has large key storage and high encryption/decryption time.The linkable lattice ring signcryption scheme not only can protect signer anonymity,but also can determine whether two signatures are generated by the same signer.Thus,based on the compact Gaussian sampling algorithm and rejection sampling technique,the identity-based linkable ring signcryption scheme is constructed on the NTRU lattice.Firstly,the system master key is generated using the trapdoor generation algorithm on the NTRU lattice.Then private keys of ring members are obtained based on the compact Gaussian sampling algorithm.Finally,the user signature is generated using rejection sampling,and the key encapsulation mechanism encrypts the signature.Security proof in the random oracle model (ROM) that DRLWE and NTRU small integer solutions are difficult to solve ensures confidentiality,unforgeability,unconditional anonymity,and linkability.Performance analysis shows that compared to the lattice-based ring signcryption and linkable ring signature schemes on NTRU,the proposed scheme has a smaller public key and lower encryption/decryption cost,greatly improving efficiency.
Although most existing linkable ring signature schemes on lattice can effectively resist quantum attacks, they still have the disadvantages of excessive time and storage overhead. This paper constructs an identity-based linkable ring signature (LRS) scheme over NTRU lattice by employing the technologies of trapdoor generation and rejection sampling. The security of this scheme relies on the small integer solution (SIS) problem on NTRU lattice. We prove that this scheme has unconditional anonymity, unforgeability, and linkability under the random oracle model (ROM). Through the performance analysis, this scheme has a shorter size of public/private keys, and when the number of ring members is small (such as N ≤ 8 ), this scheme has a shorter signature size compared with other existing latest lattice-based LRS schemes. The computational efficiency of signature has also been further improved since it only involves multiplication in the polynomial ring and modular operations of small integers. Finally, we implemented our scheme and other similar schemes, and it is shown that the time for the signature generation and verification of this scheme decreases roughly by 44.951% and 33.503%, respectively.
Blind signature allows a user to get a signature of a signer on an arbitrary message, and the verifier can convince that the signature is indeed signed by the signer without leaking any information about the message. This property is necessary when the user’s privacy needs protection, such as a bank bill, a trade secret, etc. As an alternative of public key infrastructure, the identity-based system can simplify the key management procedures in certificate-based public key systems. Inspired by the requirement of identity-based blind signature in the post quantum world, we research on identity-based blind signature based on hard lattice problems under the random Oracle model. We propose a construction built upon the blind signature by Rückert, and it is proved to be one-more unforgeable against selective identity and chosen message attacks (sID-CMA) and unconditionally blind. The proposed scheme has 2 moves, and its security can be reduced to the small integer solution (SIS) problem.