# Questions tagged [sis]

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

35 questions
Filter by
Sorted by
Tagged with
1 vote
35 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 ...
97 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 ...
1 vote
39 views

325 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 ...
1 vote
48 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 ...
117 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 ...
1 vote
126 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 ...
577 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 ...
316 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 ...
691 views

1 vote
67 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 ...
123 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}_{...
292 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, ...
289 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$. ...
2k views

219 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 ...
343 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 ...
272 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 ...
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\... 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}\}...
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 ... 