Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
544
questions
4
votes
0
answers
239
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 ...
- 243
9
votes
1
answer
150
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 ...
- 193
1
vote
1
answer
105
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 ...
- 215
11
votes
1
answer
3k
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 ...
- 111
7
votes
1
answer
806
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 ...
- 73
2
votes
1
answer
302
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 ...
- 4,763
8
votes
3
answers
2k
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 ...
- 312
4
votes
1
answer
279
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 ...
- 681
1
vote
2
answers
545
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 ...
- 889
1
vote
1
answer
236
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?
- 889
2
votes
1
answer
635
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?
- 889
9
votes
1
answer
1k
views
Gaussian distribution in lattices
In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
- 889
3
votes
1
answer
776
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 $...
- 141
2
votes
2
answers
446
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 ...
- 141
3
votes
1
answer
1k
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,323
11
votes
0
answers
661
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 the ...
- 477
7
votes
1
answer
343
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 ...
- 646
4
votes
2
answers
463
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 ...
- 131
6
votes
2
answers
1k
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 ...
- 663
10
votes
1
answer
1k
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, ...
- 889
4
votes
1
answer
213
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 ...
- 889
2
votes
2
answers
292
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,837
4
votes
0
answers
254
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 ...
- 41
0
votes
1
answer
693
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+-...
- 23
3
votes
1
answer
450
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 ...
- 162
4
votes
2
answers
584
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 ...
- 315
5
votes
1
answer
714
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 ...
- 45.7k
2
votes
1
answer
4k
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 (...
- 129
6
votes
1
answer
742
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 ...
- 85
4
votes
0
answers
149
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^...
- 205
5
votes
2
answers
690
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 $\...
- 976
1
vote
1
answer
318
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 ...
- 4,942
3
votes
1
answer
400
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 ...
- 4,942
3
votes
0
answers
1k
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 ...
- 4,942
3
votes
1
answer
744
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 $\...
- 133
15
votes
0
answers
1k
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,626
4
votes
2
answers
1k
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 ...
- 273
3
votes
0
answers
471
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 ...
- 603
3
votes
1
answer
724
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 ...
- 31
0
votes
1
answer
220
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 ...
- 1,428
7
votes
1
answer
2k
views
Help in understanding exactly how lattices are used as one-way functions for hashing
In my long-distance cryptography course, an assignment covers lattice-based cryptography. It is hard, and I am lost. There is no one to help me.
Thus far, I have understood that:
Lattices are a ...
- 73
12
votes
2
answers
4k
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 ...
- 951
1
vote
1
answer
912
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 ...
- 4,626
19
votes
1
answer
5k
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 ...
- 38.5k