The tag has no usage guidance.

learn more… | top users | synonyms

11
votes
1answer
2k views

What are the benefits of lattice based cryptography?

Previously we visited the benefits of elliptic curves for cryptography. Lattice based cryptography is starting to become quite popular in academia. The primary benefit of lattice based crypto is the ...
9
votes
1answer
76 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 ...
7
votes
1answer
253 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 ...
6
votes
1answer
117 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 ...
5
votes
1answer
66 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 ...
5
votes
0answers
270 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
2answers
165 views

Randomness re-use in LWE encryption scheme

Let me describe the scheme first, it is the scheme proposed by O. Regev when he introduced the LWE assumption. $sk = \textbf{s} \in \mathbf{Z}_q^n$ $pk = \textbf{A}\textbf{s}+\textbf{e}$ where $\...
4
votes
2answers
771 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
2answers
119 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 ...
4
votes
1answer
147 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
54 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 ...
4
votes
2answers
323 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 ...
4
votes
1answer
154 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 ...
4
votes
0answers
40 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 ...
4
votes
0answers
62 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
2answers
147 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 ...
3
votes
1answer
393 views

Help in understanding exactly how lattices used as one way functions for hashing

I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers ...
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 ...
3
votes
1answer
50 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 ...
3
votes
1answer
65 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: ...
3
votes
2answers
134 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

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 ...
3
votes
0answers
84 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
92 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
95 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
1answer
270 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 ...
2
votes
1answer
141 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 ...
2
votes
1answer
215 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 ...
2
votes
1answer
39 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=...
2
votes
1answer
49 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?
2
votes
1answer
170 views

Gap problem for Learning With Errors

Informally, a "Gap problem" arises when solving the computational (or search) version using an oracle for the decisional version. This definition of Gap Problem was introduced by Okamoto and ...
2
votes
1answer
143 views

Trapdoors for lattices

I refer to an article https://eprint.iacr.org/2011/501. I focus on (a bit modified) Algorithm 1 which runs as follows (in my understanding): For given $n, m\in \mathbb N$, $q=2^k$ and a distribution $\...
2
votes
1answer
106 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 ...
2
votes
2answers
95 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 ...
2
votes
1answer
265 views

Illustrate NTRU using lattices

I studied some papers related to NTRU. All these papers describe NTRU as a lattice based cryptosystem but I could not find any paper which illustrates NTRU algorithm from lattice point of view. It ...
2
votes
0answers
39 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 ...
2
votes
0answers
187 views

Understanding Lattice based cryptosystem [closed]

I have heard that there is one paradigm of Public key cryptosystem, called Lattice based crytography. Further, its security claims are such that it will not be affected even if the quantum computers ...
1
vote
1answer
246 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
1answer
101 views

Arithmetic modulo 1

In the context of lattice-based cryptography, in particular the Learning With Errors (LWE) problem, I see some definitions given in terms of equations modulo 1 (see for example, Appendix A of this ...
1
vote
1answer
44 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?
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 ...
1
vote
2answers
54 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
0answers
23 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
1answer
67 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
32 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
221 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
1answer
288 views

Resources for basics of lattice crypto [closed]

I'm looking to fill in the gaps of my knowledge of lattices. Can anyone point me towards papers or books that introduce lattice crypto assuming a fairly solid math background? Mods: Feel free to ...
0
votes
1answer
149 views

What are alternatives to number theory based crypto? [closed]

Quantum crypto,lattice based crypto, Neurocryptography and cellular automata based cryptography are alternatives to number theory based crypto. I need to know what are the other hard problems like ...
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?