Skip to main content

Questions tagged [sis]

For questions involving/related to the Short Integer Solutions(SIS) problem.

Filter by
Sorted by
Tagged with
0 votes
1 answer
54 views

Questions about SIS hard problem

The definition of $\mathrm{SIS}_{q,n,m,\beta}$ problem is as below. Let $A\in\mathbb{Z}_q^{n\times m}$ be an $n\times m$ matrix with entries in $\mathbb{Z}_q$ that consists of $m$ uniformly random ...
X.H. Yue's user avatar
  • 392
1 vote
0 answers
45 views

Recovering dilithium secret keys implies solving MSIS

I'm currently looking at different ways to break Dilithium and found this post: What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme? ...
limeeattack's user avatar
0 votes
2 answers
51 views

Instantiation of norm bound in SIS

Recall Short Integer Solution: $\textbf{SIS}_{n, q, \beta, m}$: Given $\textbf{A} \in \mathbb{Z}^{n\times m}_q$, $\vec{b} \in \mathbb{Z}^{n}$, find $\vec{z} \in \mathbb{Z}^{m}$ of norm $||z|| \le \...
user avatar
1 vote
1 answer
80 views

Do you know any library for implementing lattice-based schemes? [closed]

Good afternoon! I'm trying to write a code for a lattice based scheme (based on the SIS problem). I'm looking for a library that may help me in this task without taking care of the implementation of ...
Herbrant's user avatar
1 vote
0 answers
46 views

[About parameters effect LWE and SIS to be computation or perfect secure]

Hello I am new to lattice cryptography I am reading the paper More Efficient Commitments from Structured Lattice Assumptions They define bound B in page 3 Then In figure 1 in page 9 Can ...
js wang's user avatar
  • 327
2 votes
1 answer
112 views

Question about the description from ring SIS to SIS in the survey paper: A Decade of Lattice Cryptography

I am currently reading "A Decade of Lattice Cryptography" At page 30, section 4.3.2, it descrip left multiplication by any fixed ring element a It mention something about curcilant matrix ...
js wang's user avatar
  • 327
1 vote
1 answer
51 views

Collision ISIS Problem

I'm trying to understand the inhomogeneous SIS problem and I'm came across to a scenario that I don't know how to evaluate. Let $A,B \in \mathbb{Z}_q^{n\times m}$ be two random matrixes and $u,v \in \...
Carlos Ribeiro's user avatar
1 vote
0 answers
86 views

Literature on (concrete) hardness of Short Integer Solution (SIS)

I am interested in what the state of the art results on the hardness of the Short Integer Solution (SIS) instances are. The one I am the most familiar with (and the most discussed) is to use lattice ...
Gareth Ma's user avatar
  • 350
1 vote
0 answers
47 views

Tensor and power bases for SIS?

What is there to say about using a power basis or a tensor basis or some combination of them for the RSIS problem in lattice cryptography? Restricting to dimension 3 for illustration, usually the ...
Joseph Johnston's user avatar
3 votes
1 answer
235 views

ISIS problem in the case of $m=n$

The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $q$, a matrix $A\in \mathbb{Z}^{n\times m}_q$, a vector $b\in \mathbb{Z}^{n}_q$, and a real $\beta$, find an ...
Don Freecs's user avatar
2 votes
0 answers
70 views

High density SIS and Low density SIS

I am searching for the exact definition of High density SIS and Low density SIS, but there is something unclear about it. SIS problem is to find $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}...
Lee Seungwoo's user avatar
2 votes
1 answer
401 views

What is the effect of solving short integer solution problem in Dilithium or any other post quantum signature scheme?

I am trying to understand the post quantum based signature scheme Dilithium. I know what the hard problems are in the scheme, but I am having trouble in understanding the utilization of short integer ...
Muhammad Awais's user avatar
1 vote
0 answers
49 views

non-prime modulus for Ring-SIS

Consider the Ring-SIS problem for $R_q=\mathbb{Z}_q[x]/(x^n+1)$ when $n$ is power of $2$ and $q=1 \mod 2n$. Does the modulus $q$ need to be prime? if yes, it seems that it is mainly because of the way ...
A.Solei's user avatar
  • 405
3 votes
0 answers
148 views

polynomial time reduction from SIS to decisional-LWE?

Is the claim "If there is an efficient algorithm that solves SIS, then there is an efficient algorithm that solves decisional LWE" is sufficient? or, Is the claim above is equivalent to the ...
DP2040's user avatar
  • 73
1 vote
1 answer
147 views

Frobenius inner product polynomial rings

I'm trying to implement the zero-knowledge proof presented in this paper. The proof has a rejection step (page 14), which can be computed as follows: Where B and Z are in $R^{m \times n}$ for some ...
Per Mertesacker's user avatar
2 votes
1 answer
787 views

SIS vs LWE Problem

The Ajtai one way function is defined by $$f_A(x)= Ax \; mod\; q $$ where the x $\in \{0,1\}^m$ and A $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ is one way function ( Ajtai 96) While the Regev One way ...
Crypto_researcher's user avatar
3 votes
1 answer
363 views

SIS without the modulus

Consider the following modification to the Short Integer Solution (SIS) problem: Let $n$ be an integer and $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$ be functions of $n$. Sample ...
AAA's user avatar
  • 141
3 votes
1 answer
871 views

The equivalence of SIS and ISIS(Inhomogeneous SIS)

I would like to know whether these two problems are equivalent or not, namely: $SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \...
crypton00b's user avatar
1 vote
1 answer
163 views

Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)

Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$. Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$. Here, $k \geq m>...
Zi-Yuan Liu's user avatar
1 vote
1 answer
74 views

Reduction of decison SIS

In Lyu12, Lemma 3.6 is as follows. Lemma 3.6 For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the $SIS_{q, n, m, d}$ decsion ...
Alex Ideal's user avatar
2 votes
1 answer
139 views

average-case SIS and average-case BDD

In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{...
Alex Ideal's user avatar
7 votes
1 answer
335 views

Is LPN not as important as LWE and SVP?

I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
fraiser's user avatar
  • 438
6 votes
1 answer
340 views

Parameters for high density SIS

I am considering the SIS problem of finding $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}_q^{n\times m}$, $Ax=0$ and $\lVert x\rVert < \beta$ for some $p$-norm and bound $\beta < q$. ...
Joseph Johnston's user avatar
5 votes
1 answer
2k views

When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \...
abdul rahman taleb's user avatar
3 votes
0 answers
128 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
abdul rahman taleb's user avatar
2 votes
1 answer
158 views

Why does the following SIS-based decision language not make sense?

I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not. I read in the question Relation between decisional SIS and ...
Bartolinio's user avatar
1 vote
0 answers
106 views

How does the polynomial module impact the security of ring/lattices-based SIS problem?

Consider the following SIS problem: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $(R_q)^{r \times n}$=$\left(\mathbb{Z}_q[X]/(X^N+1)\right)^{r \times n}$ and $q$ a ...
user67451's user avatar
2 votes
1 answer
207 views

Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ ...
user67451's user avatar
10 votes
2 answers
1k views

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications ...
Mark Schultz-Wu's user avatar
  • 13.5k
3 votes
1 answer
56 views

Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$

Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$ with high probability over ...
Daniel's user avatar
  • 3,972
3 votes
2 answers
385 views

How is the matrix A related to the lattice space L in SIS?

Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard ...
Stilton's user avatar
  • 93
3 votes
0 answers
107 views

Size of $q$ in reductions from lattice problems to R-SIS

The Short integer solution problem is parameterized by four values: $n$, the dimension of the vectors that must be added $m$, the number of samples (dimension of the solution) $\beta$, upper-bound ...
Hilder Vitor Lima Pereira's user avatar
6 votes
1 answer
808 views

Hardness of Short Interger Solution in Lattices

Short Integer Solution ($SIS_{n,m,q,\beta}$) is defined as: Given a matrix $A \in \mathbb{Z}_{q}^{n \times m}$, find a non-zero vector $x \in \mathbb{Z}^{m}$ such that $A \cdot x = 0\mod q$ and $||x|| ...
preethi's user avatar
  • 889
2 votes
0 answers
229 views

Hardness of $SIS$ and its reduction to an NP-complete problem

Short Integer Solution ($ SIS_\gamma^{(q,n,m,\beta)}$): Given a matrix $A\in Z_{q}^{n×m}$, find $x \in Z^m $, such that $Ax=0\mod q$ and $||x|| \le \beta$ Is $SIS\in NP$ ? If $SIS \in NP$, then it ...
preethi's user avatar
  • 889
3 votes
0 answers
348 views

Short integer solution lattice problem with q=2

For large values of $q$, we know that there are worst-case lattice problems which reduce to the average-case short integer solution (SIS) problem. Does this means that for $q=2$, the SIS problem is ...
Hamidreza's user avatar
  • 1,029
4 votes
1 answer
279 views

Is there any reduction from Short Integer Solution to $\textrm{SIVP}_\gamma$

Short Integer Solution (SIS) is proved to be hard by reducing $\textrm{SIVP}_\gamma$ to SIS, i.e., if we solve SIS, then we can solve $\textrm{SIVP}_\gamma$. Is there any way to reduce an instance of ...
preethi's user avatar
  • 889
8 votes
1 answer
988 views

Relation between decisional SIS and leftover hash lemma in lattices

The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\...
Hamidreza's user avatar
  • 1,029
6 votes
1 answer
1k views

How to estimate the hardness of SIS instances?

The Short Integer Solution (SIS) problem is to find, given a matrix $A \in \mathbb{F}_q^{n \times m}$ with uniformly random coefficients, a vector $\mathbf{x} \in \mathbb{Z}^m \backslash \{\mathbf{0}\}...
Alan's user avatar
  • 1,460
5 votes
2 answers
364 views

ZK Proof for SIS

Let $A x = 0 \bmod q$ with $\Vert x \Vert < \beta$ as part of a lattice SIS problem. Does there exist an efficient zero knowledge proof of knowledge for such a solution? My idea is to use it for ...
user avatar