As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [lattice-crypto]

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

495 questions
Filter by
Sorted by
Tagged with
169 views

### Famous ideal lattices

I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ... In more ...
• 415
598 views

### NewHope and NIST's Post-quantum standardization

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules. Is being a ring-based KEM ...
• 1,235
238 views

### Are all homomorphic encryption schemes based on latticed-based schemes?

PALISADE offers a pool of Homomorphic Encryption schemes and it is stated that "PALISADE is a general lattice cryptography library ...". My question is rather simple: are all homomorphic ...
• 685
347 views

### Lattice reduction question regarding the capability of LLL and BKZ

I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things. LLL algorithm runs in polynomial time, but isn't capable of ...
• 8,291
941 views

### MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
• 123
1 vote
55 views

• 1,005
518 views

### Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
• 381
1 vote
181 views

### What are the prerequisites for understanding Lattice based Cryptography, LWE or RLWE based on SVP?

I'm new to Quantum Resistant Cryptography, so, I thought of diving into Lattice based crypto, LWE and ring LWE. I realise that the hard problem involving them is the "shortest vector problem"...
• 978
94 views

• 103
57 views

119 views

### Why do we add error in the definition of LWE?

One of the various equivalent definitions of the LWE problem is the following: Let $n,q$ be integers ($q$ usually is a prime number), $\chi$ a discrete probability distribution over $\mathbb{Z}$ (...
• 712
103 views

### Why ideal lattices?

An ideal lattice is a lattice $\mathcal{L}(A)$ generated by a block matrix $A = \left[ A^{(1)} \mid \dots \mid A^{(m/n)} \right]$ whose blocks $A^{(i)}$ are constructed from a vector $a^{(i)}$ and a ...
• 712
69 views

### How to construct a set in which the elements in $\mathbb{Z}[x]/(x^n+1)$ and their differences are invertible and with coefficients in $\{-1,0,1\}$?

I know that in IACR - Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures it constructs such a challenge set: {$x^i$}. But the inverse of the difference of ...
• 777
1 vote
44 views

### Key-Privacy in Postquantum Public-key Encryption

is there any post-quantum public-key encryption that achieves "key-privacy" (IK-CPA, IK-CCA) as described in this paper? I saw one code-based public-key encryption construction, but I wonder if ...
• 403
73 views

### Hash chain based secret revealing using homorphic princples?

I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme. I don't need a full implementation but I am not sure if what I want ...
• 135
214 views

### How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?

The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
• 315
1 vote
43 views

### Forging a new secret key in RLWE

In a RLWE setting where you are given a secret key $s$ and an associated public key $pk = (p_0,p_1) = (-(p_1s+e),p_1)$, is it possible/easy to forge a new secret key $s'$ such that $p_0+p_1s'$ has a ...
1 vote
28 views

### Ring (or Ideal) version of Boyen's signature

Boyen's signature is a well-known post quantum digital signature scheme. It's a lattice based scheme that uses a trapdoor of the lattice $\Lambda^{\perp}(A)$ and it's security is based in the SIVP ...
• 113
1 vote
57 views

### Reduction of decison SIS

In Lyu12, Lemma 3.6 is as follows. Lemma 3.6 For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the $SIS_{q, n, m, d}$ decsion ...
• 321
71 views

### Canonical inclusion map in subfield attack on overstretched NTRU

I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf authors used "canonical inclusion map" to lift vector to full lattice. What does ...
• 123
1 vote
125 views

### Hard random lattices

The content I ask in this question is in the following picture in [GPV08][1]. I do not understand the proof of the first claim in $\bf Lemma$ 5.2. In the proof, which reprensents the uniform ...
• 321
132 views

### Random lattices

The content I ask in this question is in the following picture in GPV08. I do not understand the sentence computing the syndrome $\bf{Ae} \mod q$ for some $\bf{e} \in \mathbb{Z}^{m}$ is equivalent ...
• 321
1 vote
323 views

### Average case problem and worst case problem in lattice

In Regev's lecture there is "In contrast, virtually all other cryptographic constructions are based on some average-case assumptions. For example, in cryptographic constructions based on factoring, ...
• 321
140 views

### Hardware Gaussian random numbers for lattice-based cryptography

I have been recently reading about lattice-based cryptography. I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and ...
• 33
487 views

• 321
203 views

• 43
82 views

### How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto>

In lattice-based crypto, we always need to sample 'noise' from Gaussian distribution, but how to measure the bound the noise? For example, if the Gaussian distribution is D_{u,\sigma}, where u is the ...
• 343
115 views

### security parameter in lattice cryptography

In paper Lattice Signatures Without Trapdoors(Lyubashevsky2012), $n$ is the security parameter, why the authors set $n$ as 512 but not 80/100/112 to get 80-bit security/100-bit/112-bit security?
• 321
370 views

### Learning with rounding (LWR)

This may be a naive question: LWR assumption states that for ${A} \stackrel{$}{\leftarrow} \mathbb{Z}^{m \times n}_q, s \stackrel{$}{\leftarrow} \mathbb{Z}^n_q$, given $(A, \lfloor A\cdot s \rfloor_p$...
• 139
210 views

### Block size of BKZ algorithm and related security of CRYSTALS-Kyber

Security of lattice-based schemes in the NIST Posto-Quantum Project often relies on the complexity of dual attack. Complexity of this attack depends on the running time of lattice basis reduction ...
• 167
1 vote
162 views

### set of integers modulo an integer q in lattice

Some literature about lattices set $\mathbb{Z}_{q}$ in $[-\frac{q}{2}, \frac{q}{2})\cap \mathbb{Z}$ but not $[0,q-1]$ such as "lattice signatures without trapdoors" and "lattice based blind ...
• 321
1k views

### How to find the inverse of a polynomial in NTRU-PKCS

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...
1 vote
In Section 6.3 from MP12 we have that $encode(m) = Sm$, for $S$ any basis of $\Lambda(G^t)$. Then I have: \$S = \begin{pmatrix} 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\...