Fact-checked by Grok 2 weeks ago

Short integer solution problem

The Short Integer Solution (SIS) problem is an average-case computational lattice problem central to post-quantum cryptography, defined as follows: given a uniformly random matrix A \in \mathbb{Z}_q^{n \times m} and parameters n, m, q, \beta > 0 with m = \Omega(n \log n) and q polynomial in n, find a non-zero integer vector x \in \mathbb{Z}^m such that \|x\| \leq \beta and A x \equiv 0 \pmod{q}. Introduced by Miklós Ajtai in 1996 as part of constructing the first provably secure lattice-based one-way function, the SIS problem demonstrates average-case hardness equivalent to the worst-case hardness of approximating the shortest independent vectors problem (SIVP) in the \ell_2-norm to within a factor of \tilde{O}(n).^[1] This equivalence underpins the security of numerous cryptographic primitives, including collision-resistant hash functions, digital signatures, identification schemes, and public-key encryption systems resistant to quantum attacks.^[1] Variants of SIS, such as the inhomogeneous SIS (where A x \equiv e \pmod{q} for a fixed short e \neq 0) and ring-SIS over ideal lattices for efficiency, extend its applicability while preserving hardness assumptions based on lattice problems like the shortest vector problem (SVP). The problem's parameters are chosen such that solving SIS is computationally infeasible for large n (e.g., n \geq 256) under current algorithms, with the best known attacks relying on lattice reduction techniques like BKZ that scale exponentially in dimension.^[1] Ongoing research focuses on optimizing SIS instances for practical deployments in standards like those from NIST's post-quantum cryptography standardization process.

Lattice Fundamentals

Lattices

In Euclidean space \mathbb{R}^n, a lattice \Lambda is defined as the discrete subgroup generated by integer linear combinations of m linearly independent basis vectors \mathbf{b}_1, \dots, \mathbf{b}_m \in \mathbb{R}^n, formally \Lambda = \left\{ \sum_{i=1}^m z_i \mathbf{b}_i \;\middle|\; z_i \in \mathbb{Z} \right\}, where the basis is represented by the matrix B = [\mathbf{b}_1, \dots, \mathbf{b}_m]. This structure ensures \Lambda is closed under addition and inversion, containing the origin and forming a discrete set.^[2] Lattices are classified by rank, the number of basis vectors m, relative to the ambient dimension n; a full-rank lattice has m = n, spanning \mathbb{R}^n with finite covolume |\det B|, while a non-full-rank lattice has m < n and lies in a lower-dimensional subspace. A canonical example of a full-rank lattice is the integer lattice \mathbb{Z}^n, generated by the standard basis vectors \mathbf{e}_i = (0, \dots, 1, \dots, 0) for i = 1, \dots, n. Geometrically, lattice points represent a regular array of discrete locations within the continuous \mathbb{R}^n, analogous to a crystal structure. The fundamental parallelepiped P for a basis B is the set \left\{ \sum_{i=1}^m \alpha_i \mathbf{b}_i \;\middle|\; 0 \leq \alpha_i < 1 \right\}, which tiles \mathbb{R}^n without overlap and has volume equal to the determinant |\det B|. The Voronoi cell V(\mathbf{0}) of the origin (and translates thereof) is the region \{ \mathbf{x} \in \mathbb{R}^n \mid \| \mathbf{x} \| \leq \| \mathbf{x} - \mathbf{v} \| \;\forall\; \mathbf{v} \in \Lambda \setminus \{\mathbf{0}\} \}, defining the "territory" closest to each lattice point and partitioning the space. Lattices are constructed by specifying a basis matrix B, with the choice of basis affecting computational properties despite generating the same \Lambda. To assess basis quality—particularly orthogonality and vector lengths—Gram-Schmidt orthogonalization is applied, yielding an orthogonal basis \mathbf{b}_i^* = \mathbf{b}_i - \sum_{j=1}^{i-1} \mu_{i,j} \mathbf{b}_j^* where \mu_{i,j} = \langle \mathbf{b}_i, \mathbf{b}_j^* \rangle / \|\mathbf{b}_j^*\|^2, allowing evaluation of successive minima and reduction potential. The systematic study of lattices originated with Hermann Minkowski's 1896 monograph Geometrie der Zahlen, which introduced geometric methods to analyze integer points and their distributions, laying the foundation for the geometry of numbers. Certain structured subclasses, such as ideal lattices, impose additional algebraic constraints on the basis vectors.

Lattice Properties

The shortest vector problem (SVP) is a fundamental optimization problem on lattices, defined as finding a nonzero lattice vector of minimal Euclidean norm. Formally, for a lattice \Lambda \subset \mathbb{R}^n, the length of the shortest nonzero vector is \lambda_1(\Lambda) = \min_{\mathbf{x} \in \Lambda \setminus \{\mathbf{0}\}} \|\mathbf{x}\|, and SVP seeks a vector achieving this minimum.^[3] SVP is known to be NP-hard under randomized reductions, establishing its computational intractability even for approximation factors within almost polynomial bounds.^[4] Closely related is the closest vector problem (CVP), which generalizes SVP to inhomogeneous settings by seeking the lattice vector nearest to a given target point \mathbf{t} \in \mathbb{R}^n. In CVP, the goal is to find \mathbf{x} \in \Lambda minimizing \|\mathbf{x} - \mathbf{t}\|, with the minimal distance denoted \text{dist}(\mathbf{t}, \Lambda).^[5] CVP is at least as hard as SVP, as SVP instances can be reduced to CVP by setting \mathbf{t} = \mathbf{0}, and both problems underpin the hardness assumptions in lattice-based cryptography.^[5] Key algebraic properties of lattices include the determinant, which measures the volume of the fundamental parallelepiped spanned by a basis \mathbf{B}, given by \det(\Lambda) = |\det(\mathbf{B})|.^[6] This invariant quantifies lattice density and appears in bounds on vector lengths. Minkowski's first theorem states that for a lattice \Lambda and a convex, centrally symmetric body K \subset \mathbb{R}^n with \mathrm{vol}(K) > 2^n \det(\Lambda), K contains a nonzero lattice point.^[7] Minkowski's second theorem provides bounds on the successive minima, defined as the smallest \lambda_k > 0 (for k = 1, \dots, n) such that \lambda_k K contains k linearly independent points of \Lambda. In particular, \prod_{i=1}^n \lambda_i \leq 2^n \det(\Lambda) / \mathrm{vol}(K). To approximate solutions to SVP and CVP, basis reduction algorithms transform a given basis into one with shorter, more orthogonal vectors. The Lenstra–Lenstra–Lovász (LLL) algorithm achieves this in polynomial time by iteratively applying Gram-Schmidt orthogonalization and size/orthogonality reduction steps. A basis is \delta-LLL-reduced (for \delta \in (1/4, 1)) if it satisfies size reduction (|\mu_{i,j}| \leq 1/2 for j < i) and the Lovász condition (\|b_i^*\|^2 \geq \delta \|\tilde{b}_{i+1}\|^2, where \tilde{b}_{i+1} is the component of b_{i+1} orthogonal to b_1^*, \dots, b_i^*), yielding an SVP approximation factor of $2^{n/2}.^[8] The original LLL runs in time O(n^{12} (\log B)^3), where n is the dimension and B the maximum coefficient bit length, though optimized variants achieve O(n^3 \log B) under fast arithmetic assumptions.^[8]^[9] The dual lattice \Lambda^* = \{\mathbf{y} \in \mathbb{R}^n \mid \langle \mathbf{y}, \mathbf{x} \rangle \in \mathbb{Z} \ \forall \mathbf{x} \in \Lambda\} plays a pivotal role in analytic tools for lattices, satisfying \det(\Lambda^*) = 1 / \det(\Lambda) and (\Lambda^*)^* = \Lambda.^[10] In Fourier analysis, the dual facilitates the Poisson summation formula, which equates the sum of a function over \Lambda to its Fourier transform summed over \Lambda^*, enabling proofs of density bounds and smoothing properties essential for average-case hardness reductions.^[11]

Structured Lattices

Ideal Lattices

Ideal lattices arise as the image of ideals in the ring of integers of an algebraic number field under the canonical embedding into Euclidean space. Specifically, for an ideal I in the ring of integers \mathcal{O}_K of a number field K of degree n, the ideal lattice \Lambda(I) is defined as \sigma(I), where \sigma: K \to \mathbb{R}^n is the canonical embedding that maps elements of K to vectors in \mathbb{R}^{r_1} \times \mathbb{C}^{2r_2} \cong \mathbb{R}^n, with r_1 real embeddings and $2r_2 coordinates from complex conjugate pairs.^[12] This structure endows the lattice with multiplicative properties inherited from the ring operations in \mathcal{O}_K, making it a full-rank sublattice closed under addition and ring multiplication.^[13] Ideals in \mathcal{O}_K are represented as free \mathbb{Z}-modules of rank n, providing a compact basis for the lattice that facilitates efficient computations. In cryptographic contexts, such as those involving cyclotomic fields, this representation allows ideal lattices to be embedded in \mathbb{R}^{\phi(m)}, where \phi is Euler's totient function and m defines the cyclotomic extension, reducing the effective dimension compared to unstructured lattices while preserving full rank.^[13] The module structure over \mathcal{O}_K ensures that lattice points can be manipulated using ring arithmetic, which is particularly advantageous for applications requiring repeated multiplications.^[12] The primary advantage of ideal lattices in cryptography lies in their multiplication-friendly algebraic structure, which enables fast polynomial arithmetic via the Number Theoretic Transform (NTT), achieving O(n \log n) time for multiplications that would be slower in general lattices. This efficiency stems from the ring's cyclotomic nature in many schemes, allowing operations in dimension \phi(n) rather than the full extension degree, thus optimizing storage and computation for protocols like homomorphic encryption.^[13] Additionally, ideal lattices exhibit stronger worst-case to average-case hardness reductions, with connection factors as low as O(\sqrt{\log n}), enhancing their suitability for secure constructions.^[12] A key example is principal ideal lattices, where I = (f) for some f \in \mathcal{O}_K, generated by multiplication of f across the ring; these are computationally simpler but can be extended to non-principal ideals, which require multiple generators and introduce additional complexity for security.^[12] Non-principal ideals, common in class number greater than one fields, further leverage the algebraic intricacies of number fields to bolster cryptographic assumptions.^[13] Ideal lattices also connect to coding theory through their interpretation as cosets in the quotient ring \mathcal{O}_K / I, where the quotient forms an abelian group or ring whose elements correspond to lattice coset representatives, analogous to codewords in ideal codes over finite rings.^[13] This perspective has inspired hash functions and error-correcting mechanisms in lattice-based systems.^[14]

Cyclic Lattices

Cyclic lattices represent a computationally efficient subclass of ideal lattices, defined as full-rank ideals in the polynomial ring \mathbb{Z}/(f(x)), where f(x) is a monic polynomial of degree n, embedded into \mathbb{C}^n via the canonical embedding that maps a polynomial p(x) = \sum_{i=0}^{n-1} p_i x^i to the vector (p(\zeta_0), \dots, p(\zeta_{n-1})), with \zeta_j denoting the roots of f(x).^[15] This embedding preserves the ring structure, allowing elements of the lattice to correspond directly to ring elements, which facilitates efficient arithmetic operations in cryptographic protocols.^[6] A key property of cyclic lattices is their rotation invariance, where multiplication by x in the polynomial ring induces a cyclic shift in the canonical embedding coordinates, enabling fast polynomial multiplication through convolution that can be accelerated using the Fast Fourier Transform (FFT) or Number Theoretic Transform (NTT) for suitable choices of f(x) and modulus.^[15] This symmetry simplifies computations, as operations like sampling and multiplication reduce to vector shifts and efficient transforms, making cyclic lattices particularly suitable for ring-based cryptographic primitives.^[16] A prominent example involves power-of-two cyclotomic polynomials, specifically \Phi_{2^k}(x) = x^{2^{k-1}} + 1, which yield cyclic lattices of dimension n = 2^{k-1}; these are favored in practice due to their support for NTT-based multiplication over moduli congruent to 1 modulo $2n, ensuring low-cost implementations in schemes like Kyber. Trapdoor generation for cyclic lattices typically employs Gaussian sampling techniques to produce short bases, adapting methods from general lattices to the ideal setting by sampling short vectors in the ring and extending via the rotation invariance to form a basis for the full ideal lattice. Security of these trapdoors relies on the hardness of the Ring Shortest Vector Problem (Ring-SVP), where finding short vectors in the ideal lattice is as difficult as in general lattices under appropriate reductions. Despite their efficiency, cyclic lattices face limitations from their algebraic structure, particularly for small n, where attacks leveraging Coppersmith's method for finding small roots of low-degree modular polynomials can exploit the polynomial representation to recover short secrets more effectively than generic lattice reduction.^[17]

The SIS Problem

Standard SIS

The standard Short Integer Solution (SIS) problem is an average-case computational problem over integer lattices, serving as a foundational primitive in lattice-based cryptography due to its believed hardness and efficiency in cryptographic constructions.^[18] In the search version of the SIS problem, given a prime modulus q, lattice dimension n, number of variables m \geq n \log q, norm bound \beta > 0, and a uniformly random matrix A \in \mathbb{Z}_q^{n \times m}, the task is to find a nonzero vector x \in \mathbb{Z}^m such that A x \equiv 0 \pmod{q} and \|x\| \leq \beta.^[18] This formulation was introduced in the context of lattice-based signatures by Micciancio and Regev in 2009, building on earlier work by Ajtai.^[18] Typical parameter choices for cryptographic security include q \approx 2^{32}, \beta = O(\sqrt{n}), and m = O(n \log n), ensuring average-case hardness equivalent to worst-case approximation of the Shortest Independent Vectors Problem (SIVP) to within a factor of \tilde{O}(n).^[19] The uniform random sampling of A is crucial, as it enables reductions from worst-case lattice problems to the average-case SIS, preserving hardness under Gaussian measures in the Micciancio-Regev framework.^[19] The hardness of SIS follows from average-case to worst-case reductions from approximate SVP and Closest Vector Problem (CVP), including techniques like Kannan's embedding to connect search and decision variants under quantum reductions.^[19] These reductions demonstrate that solving SIS on average is at least as hard as solving approximate SVP or CVP in the worst case for the \ell_2 norm, with polynomial approximation factors.^[19]

Ring-SIS

The Ring-SIS problem is a structured variant of the standard Short Integer Solution (SIS) problem, defined over the ring of integers modulo q in a polynomial ring, leveraging the algebraic structure of ideal lattices to enable more efficient cryptographic constructions. Specifically, let R_q = \mathbb{Z}_q / (f(x)) where f(x) is typically a cyclotomic polynomial of degree n, and let the dot product be defined via coefficient-wise convolution in the ring. The search Ring-SIS_{n,m,\beta} problem, for positive integers n, m and bound \beta, is to find a nonzero \mathbf{x} \in R_q^m such that \|\mathbf{x}\| \leq \beta and \mathbf{a} \cdot \mathbf{x} = \mathbf{0} in R_q, given a uniform \mathbf{a} \in R_q^m. Typical parameters for Ring-SIS in practical schemes include n = 256 or $512 as the degree of the cyclotomic polynomial, m = O(n) samples, \beta = O(\sqrt{n}) as the norm bound, and q chosen as an NTT-friendly prime or power-of-two (e.g., q \approx 2^{13} to $2^{23}) to support fast polynomial multiplication via the Number Theoretic Transform.^[20] The hardness of Ring-SIS is established via quantum worst-case to average-case reductions from approximate Shortest Vector Problem (SVP) on ideal lattices, where the norm \|\mathbf{x}\|_2 is measured in the canonical embedding \sigma_i: R \to \mathbb{C} for i = 1, \dots, n, defined as \|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n |\sigma_i(\mathbf{x})|^2}. Early reductions for cyclic variants appeared in 2006, with full ideal lattice hardness for Ring-SIS formalized in 2010 assuming polynomial-time quantum hardness of ideal-SVP to approximation factor \tilde{O}(n^{1/2}). Compared to standard SIS, Ring-SIS enables significantly smaller key and ciphertext sizes through ring compression—reducing dimension from O(n^2) to O(n \log n)—while maintaining comparable security levels, making it suitable for resource-constrained applications. However, the algebraic structure introduces vulnerabilities to ring-specific attacks, such as those exploiting automorphisms or factorizations of the polynomial modulus, which can weaken security relative to unstructured SIS instances. A key variant is the inhomogeneous Ring-ISIS problem, where the equation becomes \mathbf{a} \cdot \mathbf{x} = \mathbf{u} \neq \mathbf{0} for a given target \mathbf{u} \in R_q, which finds applications in collision-resistant hash functions like SWIFFT and in lattice-based ring signatures.

Module-SIS

The Module Short Integer Solution (Module-SIS) problem extends the Ring-SIS problem to modules of rank d > 1 over the polynomial ring R_q = \mathbb{Z}_q / (x^n + 1), facilitating scalable and efficient lattice-based cryptographic designs by leveraging structured algebraic dependencies across multiple ring elements.^[21] Formally, in the Module-SIS problem, given a matrix A \in R_q^{d \times m} sampled uniformly at random and parameters q, n, d, m, and \beta, the objective is to find a nonzero x \in R_q^m (equivalently, coefficients in \mathbb{Z}^{m n}) such that \|x\| \leq \beta and A x = 0 in R_q^d.^[21] This formulation bridges unstructured SIS instances with their ring variants, preserving average-case hardness while enabling compact representations. Parameters for Module-SIS are selected to ensure cryptographic security levels comparable to AES-128 or higher, with typical values including module rank d = 2 to $8, polynomial degree n = 256, and number of samples m \approx d n \log_2 q / \log_2 \beta, which balances the norm bound \beta against the modulus q (often a prime around $2^{12} to $2^{23}) for efficient computation without compromising hardness. The computational hardness of Module-SIS follows from quantum polynomial-time reductions to worst-case approximation problems like Module Shortest Vector Problem (Module-SVP) or Module Shortest Independent Vectors Problem (Module-SIVP) in ideal lattices of rank d, as well as from the Module Learning With Errors (Module-LWE) problem, under conditions where q \geq \beta \sqrt{d n} \cdot \omega(\log (d n)) and m, \log q = \mathrm{poly}(d n).^[21] This structure yields efficiency gains through parallelizable operations on the d-dimensional module components, reducing key and ciphertext sizes compared to unstructured lattices while supporting fast Number Theoretic Transform (NTT)-based arithmetic, as demonstrated in the NIST post-quantum cryptography standard CRYSTALS-Kyber (originally proposed in 2017 by Bos, Ducas, Kiltz, Lepoint, Lyubashevsky, Schanck, Schwabe, Seiler, and Stehlé; finalized as FIPS 203 in August 2024).^[22] Despite these advantages, the module framework introduces challenges such as an expanded attack surface from the interplay of algebraic ring properties and lattice geometry, enabling hybrid attacks that integrate classical lattice reduction (e.g., BKZ) with algebraic techniques to exploit low-rank dependencies or sparse structures.

Applications and Hardness

Cryptographic Uses

The Short Integer Solution (SIS) problem and its variants, such as Ring-SIS and Module-SIS, serve as foundational hardness assumptions for numerous post-quantum cryptographic protocols, enabling efficient constructions resistant to quantum attacks. These problems allow for the design of primitives like signatures, encryption schemes, and zero-knowledge proofs by leveraging the difficulty of finding short vectors satisfying linear equations modulo a prime q. Practical implementations prioritize parameter choices that balance security, key sizes, and computational efficiency, often drawing on structured lattices to reduce overhead. In digital signatures, Module-SIS underpins schemes like CRYSTALS-Dilithium, a NIST-standardized post-quantum signature algorithm specified as ML-DSA in FIPS 204 (published August 2024). Dilithium employs Module-SIS in its Fiat-Shamir-with-aborts paradigm to generate signatures that prove knowledge of a short secret vector without revealing it, achieving IND-CCA security under the random oracle model. The protocol samples short vectors for key generation and signing, rejecting invalid attempts to ensure tight security reductions, with public key sizes around 1.3–2.5 KB and signature sizes of 2.4–4.8 KB depending on the security level.^[23]^[24] For encryption, NTRU-like schemes utilize Ring-SIS to facilitate key generation via trapdoors based on short bases of ideal lattices, allowing decryption of ciphertexts encrypted with public keys derived from polynomial rings. These constructions, such as variants of NTRUEncrypt, rely on the hardness of finding short solutions in cyclotomic rings to ensure semantic security, with trapdoor samplers enabling efficient short vector recovery for decryption. Modern analyses confirm their equivalence to worst-case problems over ideal lattices, supporting security levels comparable to AES-128. Representative implementations achieve key sizes under 1 KB and ciphertext expansion below 2x plaintext length.^[25] SIS-based zero-knowledge proofs enable efficient demonstrations of knowledge of short vectors satisfying SIS instances, with adaptations of Bulletproofs providing succinct arguments over module lattices. These protocols use recursive folding techniques on sigma-protocols derived from Ring-SIS or Module-SIS to compress proofs to logarithmic sizes, suitable for applications like verifiable computation. For instance, lattice Bulletproofs variants prove short vector relations in O(log n) communication rounds, achieving constant-size proofs for range checks or equality tests while maintaining extractability.^[26] The Fiat-Shamir heuristic transforms decision SIS instances into identification schemes and hash functions by hashing non-interactive proofs, yielding collision-resistant functions from the average-case hardness of SIS. This approach, applied in lattice settings, converts interactive proofs of short solution knowledge into non-interactive ones, supporting secure identification with negligible soundness error. Seminal constructions demonstrate that such hashes are one-way under SIS, enabling compact commitments and signatures. Parameter recommendations for Module-SIS in Dilithium align with NIST security levels 1–5, using dimension n=256 and modulus q=8380417 across variants, providing approximately 128-bit post-quantum security for level 2 (ML-DSA-44) with module rank k=4. These choices ensure resistance against lattice reduction attacks up to 2^128 operations, with higher levels (e.g., k=8 for level 5) scaling to 256-bit security while maintaining practical performance.^[24]^[27]

Reduction to Lattice Problems

The hardness of the Short Integer Solution (SIS) problem is fundamentally tied to the difficulty of solving well-studied lattice problems in the worst case, such as the Shortest Vector Problem (SVP) and the Shortest Independent Vectors Problem (SIVP). Micciancio and Regev established a classical reduction showing that the average-case SIS_{q,n,m,\beta} problem is computationally at least as hard as approximating SVP to within a factor of \gamma = O(\sqrt{n}) in the worst case over arbitrary lattices, for parameters q = poly(n), \beta = O(\sqrt{n}), and m = O(n \log q).^[28] This reduction transforms arbitrary worst-case lattice instances into random SIS instances using Gaussian measures, preserving the approximation factors and enabling the use of SIS in cryptographic constructions assuming the conjectured intractability of these lattice problems. The search version of SIS, which requires explicitly finding a short nonzero integer vector x satisfying A x \equiv 0 \pmod{q} for a random matrix A \in \mathbb{Z}_q^{n \times m}, is equivalent in hardness to the decision version, which asks to distinguish SIS samples (A, 0) from (A, u) where u is uniformly random in \mathbb{Z}_q^n. This equivalence is proven via a series of hybrid arguments that incrementally modify the target vector while maintaining indistinguishability, thereby reducing the search problem to the decision problem without significant loss in hardness.^[29] In the quantum setting, the hardness of SIS follows from extensions of Regev's quantum reduction framework originally developed for the Learning With Errors (LWE) problem, linking average-case SIS to worst-case quantum hardness of lattice problems like SVP. These reductions operate over q-ary lattices, defined for a vector u \in \mathbb{Z}_q^n as the coset \Lambda_q^u = { x \in \mathbb{Z}^m \mid A x \equiv u \pmod{q} }, where solving SIS corresponds to finding short vectors in such cosets.^[29] A key quantum reduction from SIS to LWE, as detailed by Stehlé, Steinfeld, Tanaka, and Xagawa, further confirms that quantum algorithms breaking SIS would imply efficient quantum solvers for LWE, reinforcing the quantum security of SIS-based schemes. The leftover hash lemma plays a crucial role in establishing the pseudorandomness properties of SIS samples, which underpins the security of pseudorandom functions (PRFs) constructed from SIS. Specifically, for a random A \in \mathbb{Z}_q^{n \times m} and short x \in \mathbb{Z}^m with \beta-small norm, the lemma shows that the pair (A, A x) is statistically close to the uniform distribution over \mathbb{Z}_q^{n \times m} \times \mathbb{Z}_q^n, provided the min-entropy of the source exceeds the output length by a logarithmic factor in the security parameter; this enables efficient SIS-based PRFs with provable security under the decisional SIS assumption. Following NIST's 2024 standardization of lattice-based post-quantum algorithms like Dilithium (which relies on SIS for signatures), these parameters provide concrete quantum security exceeding 128 bits against Grover-accelerated attacks.^[30]

References

[1]
[PDF] The SIS Problem and Cryptographic Applications
... Short Integer Solution (SIS) Problem. 2 Average Case Hardness. 3 Efficiency and RingSIS. Small modulus. Ideal Lattices. 4 Cryptographic Applications. 1 ...
[2]
Point Lattice -- from Wolfram MathWorld
Formally, a lattice is a discrete subgroup of Euclidean space, assuming it contains the origin. That is, a lattice is closed under addition and inverses, and ...
[3]
[PDF] The Shortest Vector in a Lattice is Hard to Approximate to within ...
CVP is the inhomogeneous counterpart of SVP: given a lattice and a target point (not necessarily in the lattice), find the lattice point closest to the target.
[4]
The shortest vector problem in L2 is NP-hard for randomized ...
The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). Author: Miklós Ajtai.
[5]
[PDF] Closest Vector Problem - UCSD CSE
A g- approximation algorithm for CVP finds a lattice vector within distance at most g times the distance of the optimal solution. The best known polyno- mial ...
[6]
[PDF] Lattice-based Cryptography
Jul 22, 2008 · Shortest Vector Problem (SVP): Given a lattice basis B, find the shortest nonzero vector in L(B). • Closest Vector Problem (CVP): Given a ...
[7]
[PDF] Minkowski's theorem 1 Minimum Distance - UCSD CSE
Minkowski's theorem can also be generalized to provide a bound not just on λ1, but on the geometric mean of all successive minima. Theorem 12 For any ...
[8]
[PDF] Factoring Polynomials with Rational Coefficients
It follows that we must look for a “small” element in that lattice, and this is done by means of a basis reduction algorithm. It turns out that this enables us ...
[9]
An LLL Algorithm with Quadratic Complexity
The Lenstra–Lenstra–Lovász lattice basis reduction algorithm (called LLL or L 3 ) is a fundamental tool in computational number theory and theoretical ...
[10]
[PDF] Lecture 8 Dual Lattices
DEFINITION 1 For a full-rank lattice Λ we define its dual lattice (sometimes known as the reciprocal lattice) Λ∗ = {y ∈ Rn | ∀x ∈ Λ, hx, yi ∈ Z}. In general, ...
[11]
[PDF] Lecture 9 Fourier Transform
dimensional lattice Λ. The Fourier series of λZ-periodic functions was defined as a function on the dual lattice. 1 λ. Z. Moreover, in Lemma 9 we proved that ...
[12]
[PDF] Lattices that Admit Logarithmic Worst-Case to Average-Case ...
Apr 13, 2007 · When embedded in geometric space, an ideal yields an n-dimensional ideal lattice. This notion is quite natural and standard in algebraic number ...
[13]
[PDF] On Ideal Lattices and Learning with Errors Over Rings
Apr 24, 2012 · We also gain some confidence in the hardness of ideal lattices from the fact that they arise naturally in algebraic number theory, a deep ...
[14]
[PDF] Ideal Lattices - People | MIT CSAIL
Q: What are ideal lattices? A: They are lattices with some additional algebraic structure. Lattices are groups. Ideal Lattices are ideals.
[15]
[PDF] Generalized compact knapsacks, cyclic lattices, and efficient one ...
We remark that our definition of cyclic lattices is analogous to the definition of cyclic codes, one of the most useful and widely studied classes of codes in ...
[16]
On the Geometry of Cyclic Lattices | Discrete & Computational ...
Aug 6, 2014 · Cyclic lattices are sublattices of that are preserved under the rotational shift operator. Cyclic lattices were introduced by Micciancio ...
[17]
[PDF] Coppersmith's lattices and “focus groups”: an attack on small ...
Dec 16, 2020 · Abstract. We present a principled technique for reducing the lattice and ma- trix size in some applications of Coppersmith's lattice method ...
[18]
Lattice-based Cryptography - SpringerLink
In this chapter we describe some of the recent progress in lattice-based cryptography. Lattice-based cryptographic constructions hold a great promise for ...
[19]
[PDF] Worst-case to Average-case Reductions based on Gaussian ...
Dec 27, 2005 · The reduction from GapSVP is shown in Subsection 5.4. For technical reasons, in that reduction we need to consider a variant of the SIS problem,.
[20]
[PDF] CRYSTALS-Dilithium
Nov 30, 2017 · For all security levels, our scheme uses the same ring with q = 223 − 213 + 1 and n = 256. ... Ring-LWE, SIS, and Ring-SIS. The third.
[21]
Worst-Case to Average-Case Reductions for Module Lattices
Module-SIS and Module-LWE problems bridge SIS/LWE with Ring-SIS/Ring-LWE, and their worst-case to average-case reductions are sharp, unlike Ring-SIS/Ring-LWE.
[22]
[PDF] CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
One specificity of our LWE and SIS instances is that they are inherited from Module-LWE and Module-SIS instances. One may wonder whether the extra algebraic.
[23]
[PDF] Module-Lattice-Based Digital Signature Standard | FIPS 204
Aug 13, 2024 · [28] Avanzi R, Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, Schwabe P, Seiler G,. Stehlé D (2020) CRYSTALS-Kyber algorithm ...
[24]
[PDF] Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
Nowadays, NTRUEncrypt is generally considered as a reasonable alternative to the encryption schemes based on integer factorisation and discrete logarithm ...
[25]
[PDF] A Compressed Σ-Protocol Theory for Lattices
Mar 13, 2021 · These protocols are first compressed using a recursive “folding-technique” adapted from Bulletproofs, at the expense of logarithmic rounds.
[26]
[PDF] CRYSTALS-Dilithium
Feb 8, 2021 · The security of Dilithium is based on the hardness of LWE and SIS-type problems. lattice- based encryption schemes are based solely on the ...
[27]
Worst‐Case to Average‐Case Reductions Based on Gaussian ...
We show that finding small solutions to random modular linear equations is at least as hard as approximating several lattice problems in the worst case.
[28]
[PDF] The Learning with Errors Problem
The LWE problem has a 'dual' problem known as the SIS problem (which stands for Small Integer Solution). In the SIS problem, we are given a sequence of vectors ...
[29]
NIST Releases First 3 Finalized Post-Quantum Encryption Standards
Aug 13, 2024 · NIST has released a final set of encryption tools designed to withstand the attack of a quantum computer. These post-quantum encryption ...Missing: SIS | Show results with:SIS