In certain designs and applications of practical lattice-based cryptography, the use of a specialized variant of LWE problems, where the public matrix is sampled from a non-uniform distribution, is required to establish the security of the corresponding cryptographic schemes. Recently, the formal definition of LWE problems with semi-uniform seeds was introduced by the community, in which the hardness of Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds was proved through reduction approach similar to those employed in the hardness proofs of entropic LWE problems. However, known reduction introduces significant losses in the Gaussian error parameters and lattice dimensions. Moreover, additional non-standard assumptions are required to demonstrate the hardness of LWE problems with semi-uniform seeds over rings. In this paper, a tighter reduction is proposed for LWE problems with semi-uniform seeds by incorporating modified techniques from the hardness proofs of Hint-LWE problems. The proposed reduction is unaffected by the algebraic structure of the underlying problems and can be uniformly applied to Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds. The hardness of these LWE problems can be established based on standard LWE assumptions without the need for any additional non-standard assumption. Furthermore, the dimension of corresponding LWE problems remains unchanged, and the reduction introduces only minimal losses in Gaussian error parameters.
In certain designs and applications of practical lattice-based cryptography, the use of a specialized variant of LWE problems, where the public matrix is sampled from a non-uniform distribution, is required to establish the security of the corresponding cryptographic schemes. Recently, the formal definition of LWE problems with semi-uniform seeds was introduced by the community, in which the hardness of Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds was proved through reduction approach similar to those employed in the hardness proofs of entropic LWE problems. However, known reduction introduces significant losses in the Gaussian error parameters and lattice dimensions. Moreover, additional non-standard assumptions are required to demonstrate the hardness of LWE problems with semi-uniform seeds over rings. In this paper, a tighter reduction is proposed for LWE problems with semi-uniform seeds by incorporating modified techniques from the hardness proofs of Hint-LWE problems. The proposed reduction is unaffected by the algebraic structure of the underlying problems and can be uniformly applied to Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds. The hardness of these LWE problems can be established based on standard LWE assumptions without the need for any additional non-standard assumption. Furthermore, the dimension of corresponding LWE problems remains unchanged, and the reduction introduces only minimal losses in Gaussian error parameters.
Let (D,S,χ,m)-LWEn,q be the LWE problem in matrix form (A,y=As+emodq), where A,s,e are randomly chosen respectively from the seed distribution D over Zqm×n, secret distribution S over Zqn and noise distribution χm over Zm (or Rm), i.e., A←D,s←S,e←χm. For various secret-noise distributions (S,χ), the (D,S,χ,m)-LWEn,q problem is shown to be as hard as some standard worst-case lattice problems, but most of the known results require D to be the uniform distribution over Zqm×n. In this paper, we show that under the standard LWE assumption, the problem (D,S,χ,m)-LWEn,q can still be hard for some distribution D that is not (even computationally indistinguishable from) the uniform distribution over Zqm×n. Specifically, we show that if D is a semi-uniform distribution over Zqm×n (namely, D can be publicly derived from and has a “small difference” to the uniform distribution over Zqm×n), then for appropriate choices of (S,χ), the problem (D,S,χ,m)-LWEn,q is hard under the standard LWE assumption. Moreover, we also show that the semi-uniform MLWE problem is hard under the standard MLWE assumption. As a direct application, our results pave the way to prove the security of public-key encryptions with rounded public keys under the standard (M)LWE assumption.
Several works have characterized weak instances of the Ring-LWE problem by exploring vulnerabilities arising from the use of algebraic structures. Although these weak instances are not addressed by worst-case hardness theorems, enabling other ring instantiations enlarges the scope of possible applications and favors the diversification of security assumptions. In this work, we extend the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. By doing so, we allow the Ring-LWE problem to be used over maximal real subfields of cyclotomic number fields. We prove that Twisted Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the twist factor does not affect the asymptotic approximation factors in the worst-case to average-case reductions. Thus, Twisted Ring-LWE maintains the consolidated hardness guarantee of Ring-LWE and increases the existing scope of algebraic lattices that can be considered for cryptographic applications. Additionally, we expand on the results of Ducas and Durmus (Public-Key Cryptography, 2012) on spherical Gaussian distributions to the proposed class of lattices under certain restrictions. As a result, sampling from a spherical Gaussian distribution can be done directly in the respective number field while maintaining its format and standard deviation when seen in Zn via twisted embeddings.
The Module Learning With Errors ( M-LWE ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that M-LWE with uniform η -bounded secret for any 1≤η≪q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE , provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of M-LWE with large uniform secret and uniform η -bounded error is at least as hard as the standard M-LWE problem, if the number of samples m is close to the module rank d and with further restrictions on η . The latter result can be extended to provide the hardness of search M-LWE with uniform η -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.
The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.
The module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice‐based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed distribution (i.e., the distribution of matrix A ) to be the uniform distribution. In this paper, we show that under the Module‐N‐th degree Truncated polynomial Ring Units (NTRU) (MNTRU) assumption, the search MLWE problem can still be hard for some distributions that are not (even computationally indistinguishable from) the uniform distribution. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for appropriate settings of parameters, the search MLWE problem is hard under the MNTRU assumption. Moreover, we also show that under the appropriate settings of parameters, the search learning with errors over rings problem with semiuniform seeds can still be hard under the NTRU assumption due to our results for the search MLWE problem with semiuniform seeds being rank‐preserving.
Multisignatures enable multiple users to sign a message interactively. Many instantiations are proposed for multisignatures, however, most of them are quantum-insecure, because these are based on the integer factoring assumption or the discrete logarithm assumption. Although there exist some constructions based on the lattice problems, which are believed to be quantum-secure, their security reductions are loose. In this paper, we aim to improve the security reduction of lattice-based multisignature schemes concerning tightness. Our basic strategy is combining the multisignature scheme proposed by El Bansarkhani and Sturm with the lattice-based signature scheme by Abdalla, Fouque, Lyubashevsky, and Tibouchi which has a tight security reduction from the Ring-LWE (Ring Learning with Errors) assumption. Our result shows that proof techniques for standard signature schemes can be applied to multisignature schemes, then we can improve the polynomial loss factor concerning the Ring-LWE assumption. Our second result is to address the problem of security proofs of existing lattice-based multisignature schemes pointed out by Damgård, Orlandi, Takahashi, and Tibouchi. We employ a new cryptographic assumption called the Rejected-Ring-LWE assumption, to complete the security proof.