Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
544
questions
4
votes
1
answer
116
views
Relation between k-th shortest vector of a lattice and (n-k+1)-th shortest of its dual
Let $\Lambda$ be an $n$-dimensional lattice and $\Lambda^*$ be its dual lattice.
For any $k \in \{1, 2, ..., n\}$, let $\lambda_k(\Lambda)$ be the $k$-th successive minima of $\Lambda$ (analogously ...
4
votes
0
answers
112
views
How does error distribution affect security in lattices?
It's easy to see that the crucial part of any lattice scheme is the added error. And different schemes seem to use different error distributions, some use Gaussian some use centered Binomial. Though, ...
user4936
2
votes
2
answers
1k
views
A good book on lattices [closed]
I have recently started studying lattices. The book that I am following is "Complexity of lattice problem by Shafi Goldwasser and Daniele micciancio" but it is too much inclined towards computational ...
- 394
2
votes
0
answers
219
views
Hardness of $SIS$ and its reduction to an NP-complete problem
Short Integer Solution ($ SIS_\gamma^{(q,n,m,\beta)}$): Given a matrix $A\in Z_{q}^{n×m}$, find $x \in Z^m $, such that $Ax=0\mod q$ and $||x|| \le \beta$
Is $SIS\in NP$ ?
If $SIS \in NP$, then it ...
- 889
3
votes
1
answer
338
views
Minkowski's theorem in lattice-based cryptography
I am studying basic lattice-based cryptography. In the course given by O. Regev, on page number 7, there is Claim 1 and Corollary 2 (Minkowski's First Theorem), both of which are difficult for me to ...
- 187
4
votes
1
answer
236
views
Lattice-based cryptography prone to side channel attack?
Is lattice-based cryptography still prone to side channel attacks? What are some mitigation strategies, if any?
- 41
0
votes
2
answers
1k
views
Lattice-based cryptosystems for blockchain/ledger?
Are there lattice-based cryptosystems based i.e., SIS (Short Integer Solutions) and LWE (Learning with Errors) blockchain solutions for a post quantum world?
Has the Unique Shortest Vector Problem (...
- 17
5
votes
0
answers
615
views
Lattices with hidden short vectors and an algorithm for a special case of the SVP
For the purpose of testing algorithms for lattice basis reduction or finding short vectors, it would be useful to have examples of lattices where short vectors are hidden, that is, a nontrivial ...
- 51
12
votes
0
answers
677
views
Potential Flaws With Lattice Based Cryptography?
From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
- 549
7
votes
1
answer
3k
views
What is the difference between Module-LWE and Ring-LWE?
Recently, the CRYSTALS lattice-based cryptographic suite has been published, which is based on "module lattices". What is Module-LWE? How is it different from Ring-LWE?
- 436
3
votes
1
answer
129
views
Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices?
In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with ...
- 33
3
votes
1
answer
315
views
Parameters for ring-LWE
I see on eprint that there are many papers suggesting ways to compute parameters for LWE. How can those be used to compute parameters for ring-LWE (assuming that known algorithms solving LWE are the ...
- 270
0
votes
1
answer
771
views
One doubt on an NP hard problem
It seems that Shortest Vector Problem in a lattice is NP hard. Then how Ajtai-Kumar-Sivakumar (AKS) algorithm solves it? I mean, what is the witness?
- 219
11
votes
0
answers
97
views
Decision R-LWE parameters for spherical error with worst-case hardness
In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
- 111
-2
votes
1
answer
889
views
Advantages of Lattice-based cryptography over elliptic curve cryptography
The two main advantages of lattice-based cryptography are
resistance against quantum attacks
Cryptosystems constructed using lattice are worst-case hardness.
Are there are other advantages of ...
- 889
5
votes
0
answers
453
views
ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc
While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
- 678
3
votes
0
answers
343
views
Short integer solution lattice problem with q=2
For large values of $q$, we know that there are worst-case lattice problems which reduce to the average-case short integer solution (SIS) problem. Does this means that for $q=2$, the SIS problem is ...
- 999
0
votes
0
answers
108
views
How is the security of a plaintext of Ring-LWE without an error term?
I think until public key $\mathsf{pk}=(b=-[as + e]_q,a) $ is broken, Ring-LWE is secure where $a$ is uniformaly random polynomial, $e$ is an error sampled from gaussian distribution with std=$\sigma$ ...
- 1,595
2
votes
0
answers
379
views
What is the intuition behind discrete gaussian distribution for error sampling for lattice based crypto?
I'm still not sure why it has highest entropy (higher than uniform distribution).
What is the intuition of it?
- 1,595
1
vote
1
answer
899
views
What is the intuition of canonical-embedding in homomorphic encryption based on RingLWE?
In the cryptosystem based on Ring-LWE, the noise amount is measured by canonical-embedding norm.
What is the intuition behind canonical-embedding?
- 1,595
12
votes
5
answers
2k
views
Why is lattice-based cryptography believed to be hard against quantum computer?
Why is lattice-based cryptography believed to be hard against quantum computer?
Learning With Errors(LWE) problem (reduction to SVP) is just one example.
Can you provide some intuition of the ...
- 1,595
4
votes
2
answers
530
views
Why does Learning With Errors require a bunch of samples?
Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity.
LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE ...
- 1,595
2
votes
0
answers
438
views
Questions Regarding Basics of Lattice-Based Cryptography
I had some questions regarding the basics of lattice-based cryptography I was hoping someone could answer:
What are the advantages of using a parallelepiped vs a grid?
Does a parallelepiped grant us ...
- 55
4
votes
1
answer
545
views
Dilithium signature scheme and timing attacks – Does the running time actually depend on the secret key?
The paper “CRYSTALS – Dilithium: Digital Signatures from Module Lattices” (by Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé) introduces a digital ...
- 4,763
2
votes
1
answer
135
views
Found a mistake in a proof about when GGH will decrypt incorrectly
The proof is here on page 66, lemma 20. I found the same mistake in other sources also.
It claims that GGH decryption will fail only if $\lceil R^{-1}e\rfloor \not =0$. Here $R$ is the "good" private ...
1
vote
0
answers
452
views
truncated linear congruential generator
I'm trying to reverse a truncated linear congruential generator with all parameters ( modulus $M,$ multiplier $a$, addend $b$ and the seed $x_0$) hidden.
I have read Scott Contini's article On ...
- 11
3
votes
1
answer
266
views
R-LWE instantiation with non-power of 2 polynomial
In almost all RLWE papers, the polynomials are chosen from a ring $\mathbb{Z}[x]/f(x)$ where $f(x)$ is a polynomial of the form $f(x)=x^{2^n}+1$. That leaves us the choice of polynomials like $x^{256}+...
- 1,265
9
votes
1
answer
1k
views
Lattice Crypto worst case to average case
I am currently reading the ETSI white paper Quantum Safe Cryptography and Security
On page 24 one finds the following statement:
Lattice problems also benefit from something called worst-case to ...
user27950
3
votes
0
answers
62
views
show how LWE errors can have a greater impact on result
Hi weve been given the following question in one of our classes but have not been taught anything about it and is worded strangely. It is to show how the LWE problem works by showing how small errors ...
- 51
4
votes
2
answers
421
views
How to determine the concrete security of lattice cryptosystems?
I am currently reading about lattice cryptography and am interested in the cryptosystems based on the LWE problem. I understand the reductions from lattice problems to dLWE. Then we base our belief in ...
- 41
6
votes
1
answer
228
views
Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-QuantumWorld
In this paper (Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World), author describe password authenticated key exchange scheme on page 9 and 10 (see Fig. 1 on ...
- 187
1
vote
0
answers
48
views
Effect of small secret attacks on non homomorphic encryption schemes
The new paper by Albrecht describes a new attack on "unusually" small secrets that are used in homomorphic encryption schemes.
In the paper the talk about binary secrets or LWE Normal form i.e $\...
- 1,265
2
votes
0
answers
220
views
Security analysis of LWE with unequal error and secret distribution
Analysis of security of recent LWE based Key-exchange schemes, the error and secret vector is always chosen from the same Gaussian distribution. What will be the impact on the security if $\sigma_s\...
- 1,265
1
vote
2
answers
76
views
Lower Bound on the Probability an LWE Matrix is Primitive
For positive integers $q, n, m>n$, how do we derive the lower bound $Pr[A\cdot \mathbb Z_q^m = \mathbb Z_q^n] \geq 1 - \frac{1}{q^{m-n}}$ for a uniformly random matrix $A \in \mathbb Z_q^{n \times ...
- 11
3
votes
1
answer
286
views
Pseudorandomness of ring learning with errors
My question is in Ring Learning with Errors, let $a(x)\in \mathbb{Z}_q(x)/(X^n+1)$ where $n$ is a power of $2$, be a random polynomial, $s(x),e(x)\in \mathbb{Z}_q(x)/(X^n+1)$ are the secret and error ...
- 1,265
9
votes
1
answer
570
views
Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm
By a “Diffe-Hellman-like” algorithm, I mean one that has the same API as Curve25519, etc (disregarding trivial differences such as the size of parameters): a function
$$F: (P_\text{other}, S_\text{...
- 4,763
4
votes
1
answer
272
views
Is there any reduction from Short Integer Solution to $\textrm{SIVP}_\gamma$
Short Integer Solution (SIS) is proved to be hard by reducing $\textrm{SIVP}_\gamma$ to SIS, i.e., if we solve SIS, then we can solve $\textrm{SIVP}_\gamma$.
Is there any way to reduce an instance of ...
- 889
3
votes
1
answer
255
views
Security estimation of LWE using "On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL"
I recently found this paper eprint which estimates security of LWE instantiations using an improved Dual attack.
However, I got confused looking at their example in this site.
For example, in the case ...
- 1,265
2
votes
1
answer
210
views
Why does lattice KEX not require sampling with high precision?
I was reading the NewHope paper, and I see that they are using Binomial distribution and not a discrete Gaussian distribution as was used by BCNS. I also remember hearing somewhere that lattice key ...
- 809
3
votes
1
answer
422
views
Why are vectors approximately orthogonal after Gaussian lattice reduction?
In "An Introduction to Mathematical Cryptography"'s section on lattice reduction algorithms, the authors describe Gaussian lattice reduction and claim:
[...] the angle $\theta$ between $v_1$...
- 31
5
votes
1
answer
331
views
How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem?
In Lindner & Peikert paper, the authors propose that to set the cryptosystem's parameters, one should choose $q$ to be large enough to allow for a Gaussian parameter $s \geq 8$.
My question is, ...
- 999
5
votes
2
answers
333
views
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem
In this paper (A simple provably secure key exchange by Ding et al.) At page number 8, the author gives correctness of the technique as follows
then SK A = SKB with overwhelming probability i.e. if ...
- 187
2
votes
1
answer
166
views
Are quantum preimage attacks on hash-based random oracles serious for lattice signatures?
For most of the lattice-based signature schemes in the hash-based random oracle model (like BLISS), quantum preimage attacks (e.g., Grover's alg) against the random oracle component of the signature ...
- 999
8
votes
1
answer
280
views
LWE: error and float operations
Background
I'm trying to make sense of the error in implementations of LWE and R-LWE. In LWE and R-LWE error is added to vectors in lattices to make it computationally infeasible to recover any ...
- 214
7
votes
1
answer
904
views
Relation between decisional SIS and leftover hash lemma in lattices
The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\...
- 999
4
votes
1
answer
138
views
What is the significance of the value $1/2$ within the first property of a LLL-reduced basis?
In this lecture the lecturer notes that the projection of the vector $b_2$ onto the vector $b_1$ will always result in a vector that lies between $-b_1/2$ and $b_1/2$. Why is this statement true?
I ...
- 41
4
votes
0
answers
282
views
Complexity: Taylor series and security proofs [closed]
Taylor Series
For some functions entered into Wolfram, a Taylor series expansion is represented in Big-O notation. E.g. $\sin x, x = \frac \pi4$ produces:
$\frac {1} {\sqrt[]{2}} +\frac{x-\frac{\pi}...
- 214
9
votes
2
answers
569
views
Peikert's framework for attacks on R-LWE: What "reduction modulo q" means?
I am reading Peikert's paper [Pei16] about secure instantiating of R-LWE problem. In section 3.1, The author gives a new attack framework by using "reduction modulo an ideal divisor $\mathfrak{q}$ of ...
- 999
13
votes
3
answers
1k
views
Why are only lattice problems used in cryptography?
There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?
- 229
2
votes
1
answer
237
views
Gaussian distribution over ideal lattices
I am reading Lyubashevsky's paper [LPR10] about ideal lattices and R-LWE problem and I did not understand the following part:
"Using the canonical embedding also allows us to think of the ...
- 999