The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
36 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
1answer
77 views

Problem with LLL reduction on truncated LCG schemes

I am struggling to apply Freize et al. paper to break a truncated LCG. A truncated LCG is a pseudo random generator that outputs the $n$ leading bits $y_i$ of $x_i$, where $(x_i)$ is such that $x_{...
5
votes
0answers
65 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 ...
3
votes
1answer
41 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 ...
4
votes
3answers
155 views

What is a purpose of reducing lattice basis?

This may be too broad question but it is not. I have been studying lattices for few months now, more specifically I studied: lattice problems ($SVP$, $CVP$ and etc.) lattice cryptography in post ...
3
votes
0answers
40 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 (...
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 ...
1
vote
1answer
37 views

ZK proof that two short solutions are equal

Let $A_1$ and $A_2$ two $m \times n$ matrices defining SIS problems. Does there exist a zero knowledge proof that two short solutions are the same, i.e. $$y_1 = A_1 x $$ $$y_2= A_2 x $$ $$ \Vert x \...
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 ...
8
votes
2answers
69 views

Cardinality of the group of units in a cyclotomic ring?

In the NTRU key generation, one samples a polynomial from $K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1)$ and tests if it is invertible. What are the chances of this to happen? In other words: Let $q$ be a ...
2
votes
1answer
76 views

Gaussian distribution in lattices

In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
1
vote
0answers
25 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 ...
2
votes
1answer
49 views

Find an example of a lattice such that LLL algorithm can't find the shortest vector of the lattice, satisfying

I want to find an example of a basis of a lattice of dimension $n$ such that LLL algorithm can't find the shortest vector of the lattice, and such that the shortest vector of this lattice, say $b=...
3
votes
1answer
76 views

proof of correctness Ring-LWE cryptosystem

I've been studying Ring-LWE based crytposystems such as the one in this paper, but I can't seem to find/come up with a proof of correctness for this particular scheme. The encryption goes as follows: ...
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
1answer
73 views

What is the most efficient attack on NTRU?

So, I got how finding the private key is equivalent to resolving the SVP. I also understood that the LLL algorithm can only be used in small dimensions. Now, I wonder what is the most efficient attack ...
2
votes
0answers
51 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 ...
9
votes
1answer
77 views

Collisions in the cyclotomic knapsack function

I've been working my way through the paper “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices” by Peikert and Rosen, and I've come across something that doesn't seem ...
1
vote
1answer
23 views

Use $e$ in GGH as shared secret?

I was wondering if we could construct a symmetric encryption scheme by assuming that the secret key itself in GGH is public and the shared "key" is the error vector $e$. To encrypt we would take the ...
7
votes
1answer
414 views

Is the “New Hope” Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?

In the paper, "Post Quantum Key Exhange - A New Hope," the authors present a lattice-based key exchange based on the work of Chris Peikert. In this "New Hope" key exchange the authors try to gain ...
3
votes
2answers
162 views

How to find the value of a vector modulo a basis in lattice-based cryptography

In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance: $\psi \leftarrow \psi' \mod B$ Taken from page 69 of ...
6
votes
1answer
127 views

Find collision in Ajtai's hash function using short vector

Background What is Ajtai's hash function? Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given ...
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 \...
3
votes
1answer
65 views

Practical lattice based signatures and key exchange with strong security reduction

I am looking for practical lattice-based signatures and key exchange with strong security reductions. Specifically: Provable security under the relevant standard assumptions. Fast in software while ...
1
vote
1answer
46 views

Use of orthogonal vectors in lattice-based cryptography

In lattice-based cryptography, given the basis of the lattice we compute the orthogonal vectors using Gram-Schmidt Orthogonalization process. What is the use of orthogonal vectors in lattices?
2
votes
1answer
56 views

finding the basis of a kernel in a lattice

Given a parity check matrix $A$ we define the $q$-ary lattice $$\Lambda(A) = \{x \in \mathbb Z^m\;:\;Ax\equiv0\pmod q\}$$ How to find the basis of the lattice and how to find its hermite normal form?
4
votes
2answers
330 views

Using Lattice-based cryptography for TLS\SSL

Given the general benefits of Lattice-based cryptography, such as: Post quantum Security Security from worst case scenario Efficiency What could the outlook of shifting from RSA \ ECC-based ...
1
vote
2answers
55 views

Gaussian function in lattices

Probability density function of gaussian distribution is $$ 1/{\sqrt{2 \pi} \sigma} \times {e^{{(x-c)^2/ 2{\sigma}^2 }}} $$ in lattices we assume $$ \sigma =s/\sqrt{2 \pi} $$so the gaussian ...
1
vote
1answer
255 views

How can a lattice attack be applied to ECDSA signatures?

The aim is to check if it is possible to break the ECDSA cryptosystem under the following criteria. Suppose that each ECDSA signature is generated by using the GLV method for point multiplication (...
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 $...
2
votes
1answer
219 views

Lattice based attack on RSA

Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I ...
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?
2
votes
1answer
112 views

Is secure lattice based cryptography in future?

Lattice cryptography is a post quantum cryptography that work on two NP-hard problem in below: Find shortest nonzero vector from origin and Find minimum distance of a arbitrary point out of lattice ...
4
votes
2answers
848 views

What does “Worst-case hardness” mean in lattice-based cryptography?

In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below: Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with ...
4
votes
0answers
68 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
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 ...
0
votes
0answers
36 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 ...
4
votes
2answers
125 views

How to compare performances of lattice-based and pairing-based IBE schemes

I try to compare the performances (cost of Enc, Dec, ... size of keys, ciphertexts, ...) of IBE schemes using lattices (LWE hardness assumption) or pairing (Diffie-Hellman hardness assumption). I've ...
0
votes
0answers
66 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 ...
4
votes
1answer
165 views

Use of q-ary lattices in developing cryptosystems

Why q-ary lattices are used to most cryptosystems rather than lattices. In most of the papers q-ary lattices are used. Is there any advantage? and Given $$B=(v_1,v_2,v_3,.....v_n)$$ is the basis, ...
4
votes
1answer
56 views

apprSVP in lattices

The approximate Shortest Vector Problem (apprSVP) is a problem where, given the basis and the approximation factor $\gamma$ (a function of the dimension $n$), one must find a vector $v$ belonging to ...
2
votes
2answers
99 views

What kind of operations are involved in NTRU?

I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm? When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where ...
4
votes
1answer
163 views

How to generate new LWE samples

Assume we are given a small fixed number of LWE samples with secret $s$ and error $e$, where the error distribution is taken so that the LWE problem is hard. My question: How can one further ...
3
votes
0answers
96 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 ...
2
votes
1answer
151 views

Ring-LWE elliptic gaussian distribution

I am currently trying to understand this Ring-LWE article: http://www.cims.nyu.edu/~regev/papers/ideal-lwe.pdf and I have a question. Firstly, it is mentioned in the paper that we can view the ...
0
votes
1answer
132 views

What is the meaning for a vector mod a matrix in a lattice?

I'm reading about the lattice recently.In the paper, it gives a method of a vector mod a matrix: ⃗c mod B as ⃗c−⌊⃗c×B^(−1)⌉×B = [⃗c×B^(−1)]×B. I know that a integer A mod the other integer B is A+-...
3
votes
2answers
149 views

What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
2
votes
1answer
273 views

What is a “lattice” in cryptography?

There are some questions here concerning lattice-based cryptography and this kind of cryptography seems to be especially useful if quantum computers are assumed to exist. When reading such questions ...
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^...
1
vote
0answers
240 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 ...