Is the variant of LWE-based encryption scheme secure?

Question

Suppose that there exists a SIS instance generator $Gen_{SIS}(n,m-1,q)\to(A\in\mathbb{Z}^{n\times m}_q,s\in\{0,1\}^{m-1})$, where $(s,1)$ is the short integer solution for the SIS instance $A$, s.t. $A\cdot (s,1)=0$, and $s$ is sampled from an uniform distribution $\mathcal{D}_{\alpha}:=\{0,1\}^{m-1}$, $A$ is a random matrix.

With such generator, the construction of public key encryption scheme is as follow.

• $Setup(n,m,q,\mathcal{D}_{\alpha})\to (pk,sk):$
  • Perform $Gen_{SIS}(n,m-1,q)\to(A\in\mathbb{Z}^{n\times m}_q,s\in\{0,1\}^{m-1})$;
  • Let the public key $pk=A$ and the secret key $sk=(s,1)$.
• $Encrypt(pk,x\in\{0,1\},\mathcal{D}_{\beta})\to ct$:
  • Sample a noise vector $e\in\mathbb{Z}^{m-1}_q$ from the discrete Gauss distribution $\mathcal{D}_{\beta}$;
  • Randomly pick a vector $r\gets\mathbb{Z}^n_q$, and generate the ciphertext: $ \begin{equation} ct=(r\cdot pk) +(e,x\cdot q/2) \end{equation} $.
• $Decrypt(sk,ct)\to x$:
  • Compute $x'=<ct,sk>$;
  • If $x'$ is closer to $q/2$, return 1; else if $x'$ is closer to 0, return 0.

Correctness. Due to $pk\cdot sk=0$, then $<ct,sk>=<r\cdot pk,sk>+<(e,x\cdot q/2),sk>=<e,s>+x\cdot q/2$. If $|<e,s>|\leq m\cdot\alpha\cdot\beta=\mathsf{B}$, $\mathsf{B}$ is a reasonable bound, e.g., $B=q/4$, then the correctness holds.

The above scheme seems CPA-secure if the LWE problem holds. However, I cannot determine that given the matrix $A$, whether there is a probabilistic polynomial algorithm that can find the solution $s$?

In other words, the problem can be presented as: given a matrix $A\in\mathbb{Z}^{n\times m}_q$, find a non-zero integer vector $s\in\mathbb{Z}^{m-1}$ of norm $\|s\|_\infty\leq\alpha=1$ such that $A\cdot (s,1)=0$.

Answer 1

Responding to the concern in the comments

Due to the last entry of $\vec s$ is fixed to 1, I cannot confirm that if the SIS problem can cover it.

First, note that any permutation matrix $P$ satisfies $P^t P = I$, e.g. is orthogonal. So, for any permutation matrix $P$, we can write

$$A\cdot (\vec s,1) = A(P^tP)(\vec s, 1) = (AP^t)\cdot (P(\vec s,1))$$

In words, it doesn't matter that the last entry of $\vec s$ is fixed to 1. We can easily reduce to the case where any entry of $\vec s$ is 1 (by picking $P$ appropriately). This might still seem restrictive. For a vector $\vec s$, define $\mathsf{gcd}(\vec s) = \mathsf{gcd}(\vec s_1,\vec s_2,\dots, \vec s_n)$. Note that $\vec s = \frac{\mathsf{gcd}(\vec s)}{\mathsf{gcd}(\vec s)}\vec s$. Moreover, the vector $\frac{1}{\mathsf{gcd}(\vec s)}\vec s$ will have (at least) one coordinate equal to 1 unless all coordinates of $\vec s$ are divisible by some $p>1$ simultaneously. For any reasonable probabililty distribution, it should be easy to show that this does not happen, except with negligible probability.

This is all to say that your situation isn't really that special, and should be able to be shown to be equivalent to SIS, except for perhaps some negligible error probability.

That all being said, what you want (the ability to compute a "planted SIS" instance efficiently) can be done. Unfortunately to you, it is essentially the same thing as LWE. See for example Section 1.2. So there isn't really "SIS-based encryption" along the lines that you want that is meaningfully different from LWE-based encryption.

Answer 2

I don't think that this will work in the strict LWE setting.

For $\mathbf s$ to exist for a random matrix $A$, we would expect $2^{m-1}/q^n\gtrsim 1$ and so $m\gtrsim(\log q)n/\log 2$. There will then be a transition from almost certainly no solutions to a livelihood of many solutions $\mathbf s$. Any of these solutions would suffice to decrypt your system. Because $A$ is random, whatever method you propose to recover a secret value $\mathbf s$ could in turn be used by the adversary to recover an equally good decryptions key.

Something close to LWE that might work would be to $m-1$ columns of $A$ (call this $n\times (m-1)$ matrix $A'$) at random, then choose $\mathbf s$ and then choose the final column of $A$ to be $-A'\mathbf s$. This would guarantee your SIS solutions, but we should note that $A$ is no longer a random matrix and so no longer counts as a strict instance of LWE. In particular $(\mathbf s,1)$ is a structural short vector in the dual lattice. Depending on parameterisation, this may allow $\mathbf s$ to be recoverable for small $m$.