Approximate SIS: Difference between revisions

Latest revision as of 14:12, 25 July 2025

Approximate Short Integer Solution (SIS) is an assumption introduced in 2019 by Chen, Genise, and Mukherjee.^[1] It relaxes the conditions of SIS on the target vector by allowing a range of target vectors close to $𝟎$ .

Formal Definition

Approximate SIS_n,m,q,α,β

Let matrix $𝐀 \in ℤ_{q}^{n \times m}$ be chosen uniformly at random. An adversary is asked to find a short non-zero vector $𝐬 \in ℤ^{m}$ satisfying $𝐀 \cdot 𝐬 = 𝐭 mod q \land 0 < ‖ 𝐬 ‖ \leq β \land ‖ 𝐭 ‖ \leq α$ .

Approximate SIS intuitively states that it is hard to find a short preimage of $𝐀$ of a ball of target vectors surrounding $𝟎$ . Therefore, Approximate SIS can be seen as a specific multi-instance of ISIS, where the target vectors form a ball around $𝟎$ .

Versions of Approximate SIS

Chen, Genise, and Mukherjee introduce Approximate Inhomogeneous SIS and Approximate Normal Form ISIS in their paper and provide reductions to ISIS.^[1] We omit the definitions and reductions as they are combinations of versions of SIS and reduction techniques described in the linked article.

Hardness of Approximate SIS

Approximate SIS is at least as hard as normal form SIS. Any normal form SIS instance $[\begin{matrix} 𝐈_{n} & \bar{𝐀} \end{matrix}]$ provides an approximate SIS instance $\bar{𝐀}$ . Any solution $(𝐬, 𝐭) \in ℤ^{m - n} \times ℤ_{q}^{n}$ to the approximate SIS instance is a solution to the normal form SIS instance $[\begin{matrix} - 𝐭 \\ 𝐬 \end{matrix}] \in ℤ^{m}$ of norm at most $α + β$ .

Chen et al. provide further reductions for the inhomogeneous version and its normal form from standard assumptions such as ISIS as well as LWE.^[1]

Constructions based on Approximate SIS

Approximate SIS was introduced in the context of approximate trapdoors. To reduce the dimensions of the gadget matrix $𝐆 = 𝐈_{n} \otimes 𝐠^{T}$ introduced by Micciancio and Peikert in 2012, the gadget vector $𝐠^{T} = [\begin{matrix} 1 & 2 & 4 & \dots & 2^{⌈ \log (q) ⌉} \end{matrix}]$ can be pruned by its smaller entries. This removes the possibility to generate a preimage of all exact targets, but still allows preimage sampling for vectors close to the target vector. Thus, almost any construction based on SIS can be adapted using Approximate SIS and using an approximate trapdoor is a common technique to optimise the efficiency of existing constructions.

Related Assumptions

Short Integer Solution

References

↑ ^1.0 ^1.1 ^1.2 Chen, Yilei, Nicholas Genise, and Pratyay Mukherjee. Approximate trapdoors for lattices and smaller hash-and-sign signatures. International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer International Publishing, 2019.

[:0-1] 1.0 ^1.1 ^1.2 Chen, Yilei, Nicholas Genise, and Pratyay Mukherjee. Approximate trapdoors for lattices and smaller hash-and-sign signatures. International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer International Publishing, 2019.

[1]

@@ Line 3: / Line 3: @@
 == Formal Definition ==
-=== Approximate SIS<sub>n,m,q,α,β</sub> <code>STANDARD</code> ===
+=== Approximate SIS<sub>n,m,q,α,β</sub> ===
 Let matrix <math>\mathbf{A} \in \mathbb{Z}_q^{n \times m}</math> be chosen uniformly at random. An adversary is asked to find a short non-zero vector <math>\mathbf{s} \in \mathbb{Z}^m</math> satisfying <math>\mathbf{A} \cdot \mathbf{s} = \mathbf{t} \bmod q \land 0 < \lVert \mathbf{s} \rVert \leq \beta \land \lVert \mathbf{t} \rVert \leq \alpha</math>.
-Approximate SIS intuitively states that it is hard to find a short preimage of <math>\mathbf{A}</math> of a ball of target vectors surrounding <math>\mathbf{0}</math>. Therefore, Approximate SIS can be seen as a specific multi-instance of [[Short Integer Solution#ISISn,m,q,β - Inhomogeneous SIS EQUIVALENT|ISIS]], where the target vectors form a ball around <math>\mathbf{0}</math>.
+Approximate SIS intuitively states that it is hard to find a short preimage of <math>\mathbf{A}</math> of a ball of target vectors surrounding <math>\mathbf{0}</math>. Therefore, Approximate SIS can be seen as a specific multi-instance of [[Short Integer Solution#Inhomogeneous SISn,m,q,β|ISIS]], where the target vectors form a ball around <math>\mathbf{0}</math>.
 === Versions of Approximate SIS ===
-Chen, Genise, and Mukherjee introduce Approximate Inhomogeneous SIS and Approximate Normal Form ISIS in their paper and provide reductions to [[Short Integer Solution#ISISn,m,q,β - Inhomogeneous SIS EQUIVALENT|ISIS]].<ref name=":0" /> We omit the definitions and reductions as they are combinations of [[Short Integer Solution#Versions of SIS|versions of SIS]] and reduction techniques described in the linked article.
+Chen, Genise, and Mukherjee introduce Approximate Inhomogeneous SIS and Approximate Normal Form ISIS in their paper and provide reductions to [[Short Integer Solution#Inhomogeneous SISn,m,q,β|ISIS]].<ref name=":0" /> We omit the definitions and reductions as they are combinations of [[Short Integer Solution#Versions of SIS|versions of SIS]] and reduction techniques described in the linked article.
-== On the Hardness of Approximate SIS ==
+== Hardness of Approximate SIS ==
-Approximate SIS is at least as hard as [[Short Integer Solution#NFSISn,m,q,β - Normal Form SIS EQUIVALENT|normal form SIS]]. Any normal form SIS instance <math>\begin{bmatrix} \mathbf{I}_n &\bar{\mathbf{A}} \end{bmatrix}</math> provides an approximate SIS instance <math>\bar{\mathbf{A}}</math>. Any solution <math>(\mathbf{s}, \mathbf{t}) \in \mathbb{Z}^{m-n} \times \mathbb{Z}_q^n</math> to the approximate SIS instance is a solution to the normal form SIS instance <math>\begin{bmatrix} -\mathbf{t} \\ \mathbf{s} \end{bmatrix} \in \mathbb{Z}^m</math> of norm at most <math>\alpha + \beta</math>.
+Approximate SIS is at least as hard as [[Short Integer Solution#Normal Form SISn,m,q,β|normal form SIS]]. Any normal form SIS instance <math>\begin{bmatrix} \mathbf{I}_n &\bar{\mathbf{A}} \end{bmatrix}</math> provides an approximate SIS instance <math>\bar{\mathbf{A}}</math>. Any solution <math>(\mathbf{s}, \mathbf{t}) \in \mathbb{Z}^{m-n} \times \mathbb{Z}_q^n</math> to the approximate SIS instance is a solution to the normal form SIS instance <math>\begin{bmatrix} -\mathbf{t} \\ \mathbf{s} \end{bmatrix} \in \mathbb{Z}^m</math> of norm at most <math>\alpha + \beta</math>.
-Chen et al. provide further reductions for the inhomogeneous version and its normal form from standard assumptions such as [[Short Integer Solution#ISISn,m,q,β - Inhomogeneous SIS EQUIVALENT|ISIS]] as well as LWE.<ref name=":0" />
+Chen et al. provide further reductions for the inhomogeneous version and its normal form from standard assumptions such as [[Short Integer Solution#Inhomogeneous SISn,m,q,β|ISIS]] as well as LWE.<ref name=":0" />
 == Constructions based on Approximate SIS ==