# Questions tagged [lattice-crypto]

Lattice-cryptography is the study and use of lattice problems applied to cryptography.

373 questions
Filter by
Sorted by
Tagged with
57 views

### Why $q$ in LWE must be polynomial in $n$

I am wondering why the modulus $q$ in the LWE problem has to be polynomial in $n$. Another question is whether one can take it to be an arbitrary integer instead of a prime number.
26 views

38 views

### q-ary lattices - proof of dual upto scale

Two lattices are defined as following: \begin{align} \Lambda_q^{\bot}{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: A\mathbf{x} = \mathbf{0}\text{ mod }q\} \\ \Lambda_q{(A)} & = \{\mathbf{x} \in \...
158 views

### Schnorr RSA factoring (round 2)

Introduction Earlier this year Claus Peter Schnorr claimed to have "broken RSA". The original paper was discussed in Does Schnorr's 2021 factoring method show that the RSA cryptosystem is ...
99 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 ...
46 views

### Is my proof about uniqueness of ring-LWE secret correct?

Suppose that $n$ is a power of two, $q=3\pmod 8$, prime and $R=\mathbb{Z}[X]/(X^n+1)$. Denote $\Vert\cdot\Vert$ as the infinity norm in $R_q=R/qR$ on the coefficients of elements in $R_q$. The ...
108 views

### Lattice in Sage: Generate matrix A from a basis S such that AS = 0 (mod q)

In Sage, there is a function: gen_lattice() that can generate a basis $$S \in \mathbb{Z}^{m \times m}_q$$ of a lattice $$\Lambda^\bot_q(A)$$, where $$A \in \mathbb{Z}^{n \times m}_q$$ is a random. ...
83 views

76 views

### A function $H(x)$ is given. If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function?

I came up with this question while I was reading this paper: Pilaram, Hossein, and Taraneh Eghlidos. "An efficient lattice based multi-stage secret sharing scheme." IEEE Transactions on ...
Assume there are three parties say A, B, C. A commits to a message $m$ say $c(m)$ and sends tuple $(m,c(m))$ to B. B has to prove to C that he possesses commitment $c(m)$. There is no interaction ...