# Questions tagged [lattice-crypto]

Lattice-cryptography is the study and use of lattice problems applied to cryptography.

544 questions
Filter by
Sorted by
Tagged with
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 ...
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, ... 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 ...
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 ...
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 ...
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?
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 (...
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 ...
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 ...
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?
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 ...
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 ...
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?
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 ...
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 ...
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,  and , for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
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 ...
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$ ...
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 vote
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?
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 ...
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 ...
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 ...
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 ...
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
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 ...
266 views

220 views

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 ...
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{...
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 ...
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 ...
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 ...
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$...
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, ...
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 ...
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 ...
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 ...
904 views

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 ...