We propose a variant version of ring learning with errors (R-LWE) assumption. Under the modified slightly assumption which is reducible to the worst-case problems on ideal lattice, we present a construction of digital signatures. So the scheme is provably secure based on the hardness of lattice problems (such as approximating the length of the shortest vector within a fixed poly(n) factor). Compared with some existing typical lattice-based signature schemes, the construction enjoys many advantages, including simple and efficient key generation algorithm, signing algorithm and verification algorithm to improve the efficiency of the scheme as well as to reduce the overhead. The sizes of the secret and public keys and the signature are almost linear O(n log n) (up to poly-logarithmic factors) in the dimension n of the lattice.We propose a variant version of ring learning with errors (R-LWE) assumption. Under the modified slightly assumption which is reducible to the worst-case problems on ideal lattice, we present a construction of digital signatures. So the scheme is provably secure based on the hardness of lattice problems (such as approximating the length of the shortest vector within a fixed poly(n) factor). Compared with some existing typical lattice-based signature schemes, the construction enjoys many advantages, including simple and efficient key generation algorithm, signing algorithm and verification algorithm to improve the efficiency of the scheme as well as to reduce the overhead. The sizes of the secret and public keys and the signature are almost linear O(n log n) (up to poly-logarithmic factors) in the dimension n of the lattice.

IEEE International Conference on Network Infrastructure and Digital Content (IC-NIDC)Sep 1, 20128 citations

Lattice signatures using NTRU on the hardness of worst‐case ideal lattice problems

Dipayan Das, Vishal Saraswat, Kajla Basu

Recently, lattice signatures based on the Fiat‐Shamir framework have seen a lot of improvements which are efficient in practice. The security of these signature schemes depends mainly on the hardness of solving short integer solutions (SIS) and/or learning with errors problem in the random oracle model. The authors propose an alternative lattice‐based signature scheme on the Fiat‐Shamir framework over the ring . The key generation in the signature scheme is based on the combination of NTRU and Ring SIS like key generation. Both the signature and the verification are done efficiently by doing polynomial convolutions in the ring . The proposed signature scheme is provably secure based on the hardness of the Ring SIS problem in the random oracle model. The scheme is also efficient up to constant factors as the highly practical schemes which have provable secure instantiation.Recently, lattice signatures based on the Fiat‐Shamir framework have seen a lot of improvements which are efficient in practice. The security of these signature schemes depends mainly on the hardness of solving short integer solutions (SIS) and/or learning with errors problem in the random oracle model. The authors propose an alternative lattice‐based signature scheme on the Fiat‐Shamir framework over the ring . The key generation in the signature scheme is based on the combination of NTRU and Ring SIS like key generation. Both the signature and the verification are done efficiently by doing polynomial convolutions in the ring . The proposed signature scheme is provably secure based on the hardness of the Ring SIS problem in the random oracle model. The scheme is also efficient up to constant factors as the highly practical schemes which have provable secure instantiation.

IET Information SecurityJun 2, 20205 citations

Short Lattice-Based One-out-of-Many Proofs and Applications to Ring Signatures

Muhammed F. Esgin, Ron Steinfeld, Amin Sakzad +2 more

Lecture notes in computer scienceJan 1, 201972 citations

LaSDVS : A Post-Quantum Secure Compact Strong-Designated Verifier Signature

S. Poddar, Sweta Mishra, Tapaswini Mohanty +2 more

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 $\mathcal{O}(n\log q)$ , compared to $\mathcal{O}(n^2)$ 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.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 $\mathcal{O}(n\log q)$, compared to $\mathcal{O}(n^2)$ 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.

arXiv:2504.16571Apr 23, 20250 citations

Improved lattice-based ring signature schemes from basis delegation

Wen Gao, Yupu Hu, Baocang Wang +1 more

中国邮电高校学报：英文版Jun 1, 20164 citations

\mathcal{O}(n\log q)

, compared to

\mathcal{O}(n^2)

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.