The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
1answer
39 views

ZK Proof for SIS

Let $A x = 0 \bmod q$ with $\Vert x \Vert < \beta$ be 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 an ...
2
votes
1answer
74 views

Gaussian distribution in lattices

In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
0
votes
1answer
28 views

Decomposing an ideal in intersections

Let $R$ be an ring, and let $(a),(b)$ be the ideals generated by $a,b\in R^\times$ respectively. Let $c=a\cdot b$ and $(c)$ the ideal generated by $c$. I am supposing that, given $c$, it is ...
5
votes
0answers
62 views

Distinguish two ciphers in Ring-LWE?

I am fairly new to this topic. so my question is: if I have $A=e_0a+e_1$ and $B=e_2a+e_3$ where $a$ is the agreed public parameter, $e_i \leftarrow \chi$ (drawn from the error distribution). if the ...
5
votes
0answers
46 views

Quantum complexity of LWE

As per my understanding LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al. If there is any algorithm that ...
5
votes
0answers
281 views

Given a 'good' basis for a lattice, how can we solve the CVP?

I'm doing a little bit of reading about lattices. I read that if we can find a 'short' basis for our given lattice, we can solve CVP and SVP very efficiently. However, the paper didn't describe an ...
4
votes
0answers
75 views

Would LWE problem be still secure if error were like this $e=2e_1$?

In the Learning with error problem, if the error term $e$ from equation $b=<a,s>/q+e$ were of this kind $e=2e_1$, where $e_1$ is chosen according to the probability distribution for the LWE ...
4
votes
0answers
67 views

Why SIVP Is Worst Case Problem?

I just started to study lattice cryptography. I'm now studying worst-case to average-case reduction for SIS. In previous question, "worst means any and average means random". And I wonder why ...
3
votes
0answers
38 views

In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$

In the NTRU cryptosystem, it is suggested to take $N$ prime. I want to understand why. In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (...
3
votes
0answers
22 views

Construct new SIS solutions from given ones

Assume we have a lattice SIS problem $A x = 0$, with $\Vert x \Vert < \beta$ and we are given $k$ solutions $x_1, \dots, x_k$ by, say an oracle. Is it then hard or easy to construct from there a ...
3
votes
0answers
86 views

Lattice attacks against Multilinear Maps [CLT13]

I am currently studying an article on a construction of Multilinear maps. There are some attacks on the scheme presented by the authors and I got stuck at the one in section 5.1. I will try to ...
3
votes
0answers
95 views

Worst case to average case in Ring LWE

I am currently trying to understand this Ring LWE article and I have a question. I don't understand how to apply Lemma 5.11 in order to get the worst case to average case reduction in Lemma 5.12, as ...
3
votes
0answers
97 views

How to recover $e$ from $f_A(e) = Ae \mod q$ when knowing trapdoor

I have a silly question, but I don't know a solution, so I need to question. Assume, with a algorithm $TrapGen(1^\lambda)$, it generates $A\in\mathbb{Z}_q^{n\times m}$ with a basis $B \in\mathbb{Z}_q^...
2
votes
0answers
50 views

Is the ring learning with errors problem still hard if the errors are drawn from some subspace?

Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear ...
1
vote
0answers
24 views

Proof that two signatures are done with the same short bases

My question is regarding lattice based signatures. Each lattice can have multiple short (secret) bases. Is it possible to proof in zero knowledge that two signatures on a fixed lattice have been ...
1
vote
0answers
33 views

Faster discrete Gaussian sampling

Our goal is find a faster discrete Gaussian sampling to solve $"SVP"$ problem in lattice: A lattice is discrete subgroup of $R^n$ such that define as below: let $\{b_1,\cdots ,b_n\}$ be a basis in $...
1
vote
0answers
237 views

The Inhomogeneous Short Integer Solution (ISIS) problem with a clue

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 ...
0
votes
0answers
40 views

ISIS as a one-way function

The usual formulation of the ISIS problem is the following: Given uniform $A$ and $u$, find a short $e$ such that $Ae = u \bmod q$. A different definition (call it ISIS-OWF) is to let $f_A(e) = Ae \...
0
votes
0answers
43 views

Choise enother scheme to basises of lattice cryptosystem

In the lattice cryptosystem to find a good or bad basis we apply "hadamard Ratio". But in high dimension computing of this ratio is hard. dose any other scheme exist to solve this problem?
0
votes
0answers
35 views

NTRUSign Hashing

I have some trouble understanding the inner workings of NTRUSign. So what I have understood so far is, that when Alice wants to sign a message she does the following steps Convert Alice's message ...
0
votes
0answers
65 views

special class of lattices in lattice based cryptography

A special case of lattices in lattice cryptography is that of q-ary lattices. A q-ary lattice L is defined as that in which any vector which consists of multiples of some scalar q is in ...